On the other hand, if you want to compute the area of a polygon that have vertices at lattice points, you can count the number of interior points I, the number of boundary points B. Then the area A is
one of my favorite results. It does not generalize as nicely to higher dimensions unfortunately.
If like the post you want the volume of a polyhedron you can use the three dimensional analogue of the shoelace formula (essentially equivalent).
Let Va, Vb and Vc be the vertices of a triangle ∆ of a triangulation of the surface. You need to name the vertices in a consistent order/orientation wrt the origin.
Then the volume V is the sum over all such triangles of the signed volumes
V_∆ = 1/6 Va ^ Vb ^ Vc.
That's the beauty of signed areas and volumes, determinants and exterior algebra.
To understand why this is so there's this beautiful short video
One of my off by one errors is a stupid hacky Monte Carlo intution for Picks theorem.
I count the number of points inside. Now about the boundary points I must assign some fractional weight because they are not fully inside. What's a stupid fraction I can use? Well, half seems about right. Voila,
Comments
On the other hand, if you want to compute the area of a polygon that have vertices at lattice points, you can count the number of interior points I, the number of boundary points B. Then the area A is
This is Pick's theoremhttps://en.wikipedia.org/wiki/Pick's_theorem
one of my favorite results. It does not generalize as nicely to higher dimensions unfortunately.
If like the post you want the volume of a polyhedron you can use the three dimensional analogue of the shoelace formula (essentially equivalent).
Let Va, Vb and Vc be the vertices of a triangle ∆ of a triangulation of the surface. You need to name the vertices in a consistent order/orientation wrt the origin.
Then the volume V is the sum over all such triangles of the signed volumes
That's the beauty of signed areas and volumes, determinants and exterior algebra.To understand why this is so there's this beautiful short video
https://youtu.be/Sv7VseMsOQc
From a computational standpoint, Pick's theorem seems more useful to find the number of interior points via
Where area would be calculated using the sum of signed areas of triangles.Indeed.
One of my off by one errors is a stupid hacky Monte Carlo intution for Picks theorem.
I count the number of points inside. Now about the boundary points I must assign some fractional weight because they are not fully inside. What's a stupid fraction I can use? Well, half seems about right. Voila,