[Mapserver-users] point in polygon

[Steve Lime]

Joe: The code comes comes from the comp.graphics.algotrithms FAQ. It's
basically the ray intersection test you mention.

Steve

BTW Frank and Gerald Evden (Proj.4 author) were working on the problem
you mention in terms of rendering features. That was a few months ago
and I'm not sure where they got to. I know progress was made though.

>>> Joe Bussell <joe at otsys.com> 11/14/2003 6:39:56 PM >>>
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