Is there a safe way to generate physics polygons?

[The Burrito]

I started adding a polygon drawing tool to my map editor today, and I realized I can't think of an efficient way to ensure that the polygon is convex, or that the points are in counter-clockwise order. I figure there must be a fairly easy way to do this, but I haven't been able to come up with anything that doesn't under some configuration allow an invalid shape through, creating that dreaded blue screen.

Anyone have any ideas?

[MarekkPie]

Calculus, baby. Calculus.

http://www.mathresource.iitb.ac.in/appl ... index.html

Actually, this might be easier.

http://en.wikipedia.org/wiki/Convex_and ... e_polygons

[The Burrito]

Oh yeah, that makes sense, just compare each coord with the 2 adjacent and make sure none of the angles are > 180.

The easiest way I can think of to determine the polygon winding is averaging all the coords and comparing the angles to that center point, so I guess I'll give that a try.

Thanks

[MarekkPie]

Whoops, didn't see the second part of your question. There's actually a simpler way. Find the interior angle between the first vertex and the last vertex, and always in that order. If the angle is greater than 180, then it was built clockwise. If the angle is less than 180, then it was built counter-clockwise. If it is equal to 180, then you have a line, so you won't have to worry about it.

JKGYt.png (2.3 KiB) Viewed 173 times

[The Burrito]

Cool, thanks. Somewhat ironically I don't remember any geometry from school because I spent the entire class programming games on a ti-83.

[MarekkPie]

Just looked at your website. Those mechanics are pretty clever. Brought a smile to my face.

[The Burrito]

Thanks! hopefully I'll be able to finish In The Dark soon, I've been working on it in some capacity for a long time (my first rough proof of concept for it was just over 2 years ago ) but only seriously for the last few months.

Trying out these angle based checks and they seem to work, now level design should be much easier.

[vrld]

Even easier test for winding:

• Get the leftmost vertex q, and the two adjacent ones p and r.
• if pqr make a counter clockwise turn, the polygon is left-winded

To test if three points are in counterclockwise order use the cross product, i.e.:

Code: Select all

function ccw(p,q,r)
    return (q - p) x (r - p) >= 0
end

To test wether a polygon is convex, check if all edges are ccw (or not ccw, depending on the orientation).

[MarekkPie]

God. I'm a former math teacher and I still hate linear algebra. I know, I know, I'm gonna need it when I actually get into the bigger stuff in gaming, but ugh.

[kikito]

I'm horrible at math in general - I used to be good though. Then work-life destroyed everything.

When I have a math question, I ask in mathoverflow. If it's an algorithmic question, I ask in stackoverflow.

Sure enough, this question has already been answered in SO:

http://stackoverflow.com/questions/4719 ... -nonconvex

My favourite answer is the second one. I think it says the same vrl is saying, but it's already transformed into code - no vector math involved.