OpenEuphoria

Re: finding if point is inside irregular rectangle

• Posted by David Cuny <dcuny at LANSET.COM> Feb 26, 2002
• 438 views

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