Fun with convex polygons (opens in new tab)

(wildbunny.co.uk)

39 pointswildbunny14y ago12 comments

12 comments

11 comments · 5 top-level

dmlorenzetti14y ago· 3 in thread

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.

corysama14y ago

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...

pm9014y ago

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

dmlorenzetti14y ago

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)?

1 more reply

jeffool14y ago· 3 in thread

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.

eru14y ago

> 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!

jeffool14y ago

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

wildbunnyOP14y ago

Thanks very much :)

samlittlewood14y ago

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.

HardyLeung14y ago

"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.

eru14y ago

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.

j / k navigate · click thread line to collapse

12 comments

11 comments · 5 top-level

dmlorenzetti14y ago· 3 in thread

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

corysama14y ago

pm9014y ago

dmlorenzetti14y ago

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)?

1 more reply

jeffool14y ago· 3 in thread

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.

eru14y ago

> 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!

jeffool14y ago

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

wildbunnyOP14y ago

Thanks very much :)

samlittlewood14y ago

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.

HardyLeung14y ago

"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."

That said, it certainly is a very nice algorithm.

eru14y ago

j / k navigate · click thread line to collapse