Fun with convex polygons | Hacker News Reader

Fun with convex polygons

wildbunny.co.uk

39 pointswildbunny12 comments

That works for just fine for concave non self intersecting polys as well - all the signed areas (albeit overlapping) cancel appropriately.

(scribble scribble) ... Edit: and for self intersecting, it gives the area of the poly where winding is odd.

Without looking at it very closely, it seems as though the wedge-product approach (to finding the area of convex polygons) is just asking for numerical errors. It's a classic case of finding small differences between large numbers. Most of the positive and negative contributions are supposed to cancel, but with finite-precision arithmetic, surely there'll be problems eventually-- for example, for small polygons far from the origin.

I suppose for application domains like games, you just want ballpark estimates quickly, and numerical errors aren't very important.

Often in games, numeric error is OK as long as the error is completely consistent. It's OK for your character to float half a cm off the ground as long as it's difficult to see. However, if you check edge AB using "A + x(B-A)" then later edge BA using "B + x(A-B)" the floating point non-associativity will cause tiny gaps between polygons even though they reference the same vertices! This can cause your character to intermittently fall through a perfectly water-tight floor mesh --leading to heated arguments between your testers, level artists and AI programmers...

I'm not sure if this is actually done, but you can shift the vertices to be centered at the origin (e.g by subtracting the mean of coordinates from each coordinate for a polygon). The numbers are now close to 0 and will have better precision

Yeah, I thought something similar-- translating to put one vertex at the origin. But at that point, aren't you pretty close to just using the triangles, anyway (since it's a convex polygon)?

Yes, I think you are right.

"I’ve seen a lot of people go through and calculate the area of a polygon by breaking it up into separate triangles, carefully calculating the area of each, then sum and halve."

I doubt anyone do that. What was described seems a lot more work compared to searching the web for the right formula/algorithm/source-code -- at least in the modern days. A very minimal amount of research will reveal this algorithm mentioned by the author.

That said, it certainly is a very nice algorithm.

I have to say, if I'd known this years ago when I was in school trying to become a game programmer... Well, I would have gotten more sleep! But yeah, nice stuff sir.

> Well, I would have gotten more sleep!

Do you really think so? You'd probably just put the same amount of time in, but would have gotten farther!

hah, very true; I may have graduated and still have been programming today.

Thanks very much :)

By the way, if you like convex polyhedra, but don't feel like being bound to 2 or 3 dimensions, you should have a look into mathematical optimization. Most of it centres around finding, in effect, the southern-most point of high dimensional convex polyhedra.

Reply on news.ycombinator.com