[Mapserver-users] point in polygon

[woodbri at swoodbridge.com]

Joe,

The typical way this is done is run a horizontal or vertical line 
from the point to another point beyond the extents of the polygon. 
Then to count the number of intersection of the line with the edges 
of the polygon and if the count is even then the point is outside the 
polygon and even is inside the polygon.

You don't need to compute the actual intersection point you just need 
to determine if it does intersect. You also need to deal with some 
degenerate cases, like the line intersect a vertex of the polygon or 
the line intersects an edge of the polygon, or the point in question 
lies on the polygon edge.

In the code you see status = !status; this is counting the 
even/oddness of the intersection. Much of if is determining if the 
polygon edge is outside the extents of the line then you can skip it 
and the final part is checking for an intersection.

Hope that makes more sense,
  -Steve W.

On 14 Nov 2003 at 16:39, Joe Bussell wrote:

> Greetings listers,
>    Could someone please explain to me the theory behind the pointInPolygon routine used in Mapserver?
> The code is reproduced here to facilitate discussion:
> 
>    I am specifically attempting to understand how I can determine if a point lies inside an irregular polygon which straddles the international date line.  
> 
> from mapsearch.c:
> 
> int msPointInPolygon(pointObj *p, lineObj *c)
> {
>   int i, j, status = MS_FALSE;
> 
>   for (i = 0, j = c->numpoints-1; i < c->numpoints; j = i++) 
>   {
>     if (  (     ( ( c->point[i].y <= p->y ) && ( p->y < c->point[j].y ) ) 
>              || ( ( c->point[j].y <= p->y ) && (p->y < c->point[i].y ) )     ) 
>       && ( p->x < ( c->point[j].x - c->point[i].x ) * ( p->y - c->point[i].y ) / 
>                             ( c->point[j].y - c->point[i].y ) + c->point[i].x ) )
>       status = !status;
>   }
>   return status;
> }
> 
> 
> This is distincly different from other published PointInPolygon routines which require that you draw a ray from an internal point to the point being tested.  The number of crossing being even suggests that you are inside, where an odd number of crossings indicates that you are outside.  My 
current algorithm  ( based on "Computational Geometry in C" by Joseph O'Rourke http://cs.smith.edu/~orourke/books/ftp.html) is breaking down at the date line .  My fear is that when it gets to testing a given vertex that crosses the -180,180 transition that it is assuming the segment that wraps 
around the entire globe instead.
> 
> btw, Mapserver still will not properly render polygons which straddle the dateline.  This seems to be a common source of errors.
> 
> Cordially,
> 
> Joe Bussell
> 
> _______________________________________________
> Mapserver-users mailing list
> Mapserver-users at lists.gis.umn.edu
> http://lists.gis.umn.edu/mailman/listinfo/mapserver-users
>