 # Anyone good with math? (geometry)

hey. if i have a shape stored as a list of x,y coordinates (first and last point in list are connected), how would i see if a given point (x,y) is inside the shape?

You could create an inequalitie for each line that makes up the shape and see if the point satisfies each.

Er, no. That doesn’t work for concave shapes.

Since you are only dealing with X and Y life is much simpler because it is only 2D.

Plot a line that travels from somewhere outside the shape (+X infinity, say) to your point. If the line intersects any of the lines composing the shape:

1. an even number of times, then the point is outside your shape
2. an odd number of times, then the point is inside your shape.

This method presupposes that the lines of the shape never cross each other.

Does this help?

what Duoas said is the correct approach,
here is the theory:
http://tog.acm.org/editors/erich/ptinpoly/

cheers

thanks Douas. (and thanks for the link garphik)
I understand now. (actually, it seems obvious now that i know…)

That’s the wonderful thing about math. Once you figure something out you feel stupid for not having figured it out before… 