[gameprogrammer] Re: 2D math question

[Sami Näätänen <sn.ml@bayminer.com>]

On Friday 27 April 2007, Edilson Vasconcelos de Melo Junior wrote:
> Is there any generic math expression I could use to know if a given
> point Po (xo, yo) belongs to/is inside of convex polygon with 'n'
> vertex (where n > 2)? Maybe if I have have a function for n==3, I
> could split my polygon in several triangles, right?

Yes, but you would add the amount of needed tests.

I assume clockwise polygon vertex order.
If not then negate the conditions.


If an angle between the vectors ap and bp is not negative,
then the point p is in the inside side of the edge ab.
If any point p is in the inside side of all the edges of
convex polygon then the point must be inside the polygon.


This is quite good algorithm, because one can bail out when ever the 
angle gets positive. Of course if most of the cases are the inside 
polygon ones then there will be no early bails.

I think that calculating if the point is inside or outside side of the 
edge will be a litle more efficient to calculate with a variation of 
the points distance from line formula, but without doing so I can't be 
certain :).

---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html