OpenEuphoria

RE: finding if point is inside irregular rectangle

• Posted by bensler at mail.com Feb 26, 2002
• 448 views

I thought the raytracing method was a form of the crossings count 
algorithm?
Shoot a ray in a random direction from point, count the polygon edge 
crossings. If crossing count is ODD, point is in polygon.

Check out this link that Al Gonzalez posted earlier. It describes quite 
a few different methods, with benchmarks and C code.

http://www.acm.org/tog/resources/RTNews/html/rtnv5n3.html#art3


The 'sum of angles' method was discussed and deemed to be slower than 
any of the crossings count algorithms. The argument is that the vector 
math needed to get the sum of angles is much slower than any of the math 
in the crossings count methods. But it IS an alternative.

I believe all the algorithms are presented if someone wants to translate 
one. I'm not familiar enough with C syntax.


Chris


David Cuny wrote:
> Tone Skoda wrote:
> 
> > I read somewhere that you could sum all angles between all polygon 
> > vertices
> > and point. You would take two vertices from polygon and tested point and
> > make triangle from it. That sum should be 360 if point lies inside 
> > polygon.
> > That should also work.
> 
> Yes, this is a solution used in raytracing. I ran across it at:
> 
>    http://64.33.37.114/math_rot3.html
> 
> Basically, you create a series of vectors by going clockwise (or 
> counterclockwise) from the point P to each of the vertices (V1..V3). For 
> a 
> triangle, that would be:
>   
>   L1 = P->V1
>   L2 = P->V2
>   L3 = P->V3
> 
> You then normalize the vectors (so they have a length 1) and take the 
> dotproduct for each one:
> 
>   D1 = dotProduct( L1, L2 )
>   D2 = dotProduct( L2, L3 )
>   D3 = dotProduct( L3, L1 )
> 
> You then get convert this to an angle using acos:
> 
>    sum = acos( D1 ) + acos( D2 ) + acos( D3 )
> 
> and if they equal 360 degrees (2*PI radians) then it's inside. I have a 
> feeling acos( D1 + D2 + D3)  would also work, but I'm too tired to 
> check.
> 
> Anyway, it's all explained in the paper, with nice diagrams.
> 
> -- David Cuny
> 
>