logoalt Hacker News

sreantoday at 12:12 PM1 replyview on HN

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

    A = I + B/2 - 1
This is Pick's theorem

https://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

   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

https://youtu.be/Sv7VseMsOQc


Replies

sebastianmestretoday at 12:30 PM

From a computational standpoint, Pick's theorem seems more useful to find the number of interior points via

    I = 2 (A - B + 1)
Where area would be calculated using the sum of signed areas of triangles.
show 1 reply