[Mapserver-users] point in polygon

[Joe Bussell]

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