CODEWITHSUNDEEP
algorithmmatlabpolygonpoint
Simon Hanks
Simon Hanks

Reputation: 65

Point in polygon algorithm explanation

Hi I came across this algorithm from Mathhelpforum which determines whether a point is inside or outside a polygon. The code works perfectly so far but I don't fully understand the logic. Kindly provide an explanation if you do, especially on the method...whether ray casting, or winding number, etc. Thanks.

function [ inside ] = inpoly(polygon,xt,yt)

rows = size(polygon);
npoints = rows(1);
disp (npoints);
inside = 0;

xold = polygon(npoints,1);
yold = polygon(npoints,2);

for i = 1:1:npoints

   xnew = polygon(i,1);
   ynew = polygon(i,2);

      if (xnew > xold) 
         x1=xold;
         x2=xnew;
         y1=yold;
         y2=ynew;
      else 
         x1=xnew;
         x2=xold;
         y1=ynew;
         y2=yold;
      end

      if ((xnew < xt) == (xt <= xold) & (yt-y1)*(x2-x1) < (y2-y1)*(xt-x1) ) 
               inside=~inside;
      end

      xold=xnew;
      yold=ynew;

end

endfunction

To test the function e.g. :

inpoly([p,q],x,y)

Where p and q are vertices of the polygon and x, y coordinates of the point.

Upvotes: 2

Views: 1259

Answers (1)

CiaPan
CiaPan

Reputation: 9571

Seems a ray casting to me. Varaibles x1, y1, x2, y2 are the polygon side's endpoints sorted with respect to X. The condition (xnew < xt) == (xt <= xold) tests whether the Y-parallel line from the point xt,yt meets the side. The other part of the condition tests if xt,yt is at the proper side of the polygon's side.

Condition

(yt-y1)*(x2-x1) < (y2-y1)*(xt-x1)

is equivalent to

(yt-y1)*(x2-x1) - (y2-y1)*(xt-x1) < 0

which is a matrix determinant

| yt-y1  xt-x1 |
|              | < 0
| y2-y1  x2-x1 |

and the matrix is a vector cross product

(pointT - point1) times (point2 - point1)

Upvotes: 1

Related Questions