Page 2 of 2   << first < 1 2
Bookmark this page: Add Point in Polygon Algorithm to Yahoo MyWeb Add Point in Polygon Algorithm to Google Bookmarks Add Point in Polygon Algorithm to Windows Live Add Point in Polygon Algorithm to Del.icio.us Digg Point in Polygon Algorithm! Add Point in Polygon Algorithm to Netscape
  •  
  • Subject
  • Author
  • Date
If you were  Registered and logged in, you could reply and use other advanced thread options
Posted by Roland Spielhofer on August 30, 2006, 3:04 am
rgc wrote:
>
>
>>Uffe Kousgaard wrote:
>>>What are the longest distances between your points?
>>>>Hi folks,
>>>>I'm looking for an algorithm determining if a point is within a given
>>>>polygon or not. I found some for plane geometry, but I need one in
>>>>shperical geometry - i.e. working with GPS points.
>>>>Any links or pointers appreciated!
>>I know there is not much failure if I do the calculation planar. But
>>then it's not "clean".
>>Regards,
>>Roland
>
>
> Hi Roland,
>
> Would you mind posting what you come up with? (If you'd rather, you
> could just email me. :-)
>
> If you were content to use a planar algorithm, you could use the
> algorithm for ccw(p0,p1,p2) from Robert Sedgewick's book _Algorithms in
> C_. This algorithm returns +1 if point p2 is to the left of or in front
> of the line segment from p0 to p1, 0 if it is on the line segment, and
> -1 if it is to the right of or behind the line segment. If the polygon
> is described in a counterclockwise direction, then p2 is inside it if p2
> returns a +1 when p0-p1 describes each of the line segments in the
> polygon. If the polygon is described in a clockwise direction, you need
> -1's. If the polygon is a collection of unordered sides, either find
> another algorithm or preprocess all your polygons.

Hi!
I have Sedgewick's book (not the "C" book, but the "algorithm" book, and
it was my starting point. What I found out in the meantime is that
PostGIS has a "within"-function, using GEOS. A quick look in the
GEOS-docu didn't get me very far, but I am confident that the aloorithm
is hidden somewhere in the GEOS docu/source.
So far
Roland

Posted by Jim Mortoza on September 30, 2006, 6:03 pm
'-Polygon() is the array of points that make up the polygon

'--point is the point in question. This function will return a 0 if

'--point is outside the polygon, a -1 if it is inside





Dim i As Integer

Dim j As Integer

Dim c As Integer = 0

'-npol is the number of points in the polygon, which also happens

'--to be the number of sides

Dim npol As Int32 = UBound(polygon) + 1

i = 0

j = npol - 1



Do While i < npol

If (((polygon(i).Y <= point.Y) AndAlso (point.Y < polygon(j).Y)) OrElse
((polygon(j).Y <= point.Y) AndAlso (point.Y < polygon(i).Y))) AndAlso
(point.X < (polygon(j).X - polygon(i).X) * (point.Y - polygon(i).Y) /
(polygon(j).Y - polygon(i).Y) + polygon(i).X) Then

c = Not c

End If

j = i

i += 1

Loop

'-1=inside

'0=outside

Return c

> > Uffe Kousgaard wrote:
> > > What are the longest distances between your points?
> > >>Hi folks,
> > >>I'm looking for an algorithm determining if a point is within a given
> > >>polygon or not. I found some for plane geometry, but I need one in
> > >>shperical geometry - i.e. working with GPS points.
> > >>Any links or pointers appreciated!
> > I know there is not much failure if I do the calculation planar. But
> > then it's not "clean".
> > Regards,
> > Roland
> Hi Roland,
> Would you mind posting what you come up with? (If you'd rather, you
> could just email me. :-)
> If you were content to use a planar algorithm, you could use the
> algorithm for ccw(p0,p1,p2) from Robert Sedgewick's book _Algorithms in
> C_. This algorithm returns +1 if point p2 is to the left of or in front
> of the line segment from p0 to p1, 0 if it is on the line segment, and
> -1 if it is to the right of or behind the line segment. If the polygon
> is described in a counterclockwise direction, then p2 is inside it if p2
> returns a +1 when p0-p1 describes each of the line segments in the
> polygon. If the polygon is described in a clockwise direction, you need
> -1's. If the polygon is a collection of unordered sides, either find
> another algorithm or preprocess all your polygons.
> I do not guarantee this is the fastest way to answer the question,
> but the ccw function is very simple and fast. If the algorithms you have
> found are better, I'd be interested in hearing about them.
> You could probably revise the ccw function for spherical trig, but I
> suspect it would lose its simplicity. On the other hand, when the
> problem is stated this way, it becomes an issue of topology, so the
> spherical version might be simple too. A good source for spherical trig
> formulas is <http://williams.best.vwh.net/avform.htm> .
> For what it's worth, here is the ccw(p0,p1,p2) function, as described
> in my notes. I don't have a copy of Sedgewick's book an hand at the
> moment, so this version might be a little different than his. The x and
> y components of point pn (where n = 0, 1, 2) are pxn and pyn,
> respectively:
> ccw( p0, p1, p2 )
> dx1 = px1 - px0
> dy1 = py1 - py0
> dx2 = px2 - px0
> dy2 = py2 - py0
> if dx1 * dy2 > dx1 * dx2 return with +1
> elseif dx1 * dy2 < dx1 * dx2 return with -1
> elseif dx1 * dx2 < 0 or dy1 * dy2 < 0 return with -1
> elseif dx1^2 + dy1^2 < dx2^2 + dy2^2 return with 0
> endif
> end
> Disclaimer: Test the algorithm before you use it! I may have made a
> typo, something may have gotten garbled in transmission, you may have
> misunderstood my pseudocode, or a gremlin may have made _you_ make a
> typo.
> Bob
> Bob (Robert G.) Chamberlain | I have yet to see any problem, however
> rgc@jpl.nasa.gov | complicated, which, when looked at in
> Opinions & quips are mine | the right way, did not become still more
> - or public - not JPL's | complicated. - Poul Anderson



Posted by rgc on August 30, 2006, 7:32 pm
Hi,

Im just getting started with Mapserver.

I have Mapserver binaries installed (v 4.6) on Windows (XP Pro) running
apache (2.0.53) and PHP (4.4).

When I try and run the Itasca demo IE crashes and I get the following
error:

**********************
Internal Server Error
The server encountered an internal error or misconfiguration and was
unable to complete your request.

Please contact the server administrator, someone@somewhere.com and
inform them of the time the error occurred, and anything you might have
done that may have caused the error.

More information about this error may be available in the server error
log.
**********************

When I check the server log I have the following error:

Premature end of script headers: mapserv.exe

Anyone knopw why this might be happening? I have seen a few posts in
the past that loosely mention moving dll's from a php directory to the
mapserver directory, but there is never any reason behind doing this
and moving dll's around makes me nervous!

Any idea would be much appreciated. To the best of my knowledge all
the individual components seem to work fine, php ok, mapserver ok (I
can get it generating images from shapefiles) but I get a nasty error
when i try and 'initialise' the itasca demo.

All help appreciated.

Pete


Posted by rgc on August 31, 2006, 12:45 pm
In article

>
> > Uffe Kousgaard wrote:
> >
> > > What are the longest distances between your points?
> > >
> > >
> > >
> > >>Hi folks,
> > >>I'm looking for an algorithm determining if a point is within a given
> > >>polygon or not. I found some for plane geometry, but I need one in
> > >>shperical geometry - i.e. working with GPS points.
> > >>Any links or pointers appreciated!
> >
> > I know there is not much failure if I do the calculation planar. But
> > then it's not "clean".
> >
> > Regards,
> > Roland
>
> Hi Roland,
>
> In <http://geospatialmethods.org/spheres/MiscAlgorithms.html> , Ross
> Swick makes the interesting point that spherical polygons have a
> significant difference from planar ones: "there is no obvious way to
> define the 'inside' of a spherical polygon." Of course, that is a
> theoretical issue that is probably easy to avoid in your real
> application - unless some of your GPS-based polygons are larger than
> Asia!
>
> You might find his discussion of the issue interesting.
>
> I got 640 hits in Google for the search:
>
> algorithm "point in polygon" sphere OR spherical
>
> Go to it! :-)
>
> Bob

I'm continuing to look into this question too. It seems likely that the
best algorithm will be based on the ray-extension idea, dealing with the
cases where the ray goes through one or more vertices or coincides with
one or edges by careful use of inequalities.

Here are a couple of other thoughts:
€ A point at the antipodes from any point in the polygon might serve as
a point known to be outside the polygon for all polygons that are
smaller (in some sense) than a hemisphere.
€ At first blush, it might seem reasonable to insist that all polygons
on a sphere be smaller than a hemisphere by definition. But what if
"inside" implied a land surface and "outside" implied water? "Inside"
and "outside" would be neither ambiguous nor arbitrary.
€ A point known to be inside the polygon would work as well as a point
known to be outside as the other end of the test line - but an even
number of intersections would mean that the test point is inside the
polygon, rather than outside.

This is work in progress.....

Bob

Bob (Robert G.) Chamberlain | I asked the Oracle at Delphi:
rgc@jpl.nasa.gov | "What is the best question to ask?"
Opinions & quips are mine | ...
- or public - not JPL's | Was the reply merely an echo?

Posted by Christer Ericson on August 30, 2006, 1:22 am
> I'm looking for an algorithm determining if a point is within a given
> polygon or not. I found some for plane geometry, but I need one in
> shperical geometry - i.e. working with GPS points.
> Any links or pointers appreciated!

Is your polygon convex or concave?

For plane geometry these are the stereotypical approaches
(but there are many many others):

For a (counterclockwise) convex polygon, a point lies inside
the polygon if the point lies to the left of each (directed)
edge of the polygon.

For a concave polygon, a point lies inside the polygon if a
ray fired from the point in whichever direction (usually
along +x) intersects the polygon boundary an odd number of
times.

Either of these should translate to spherical geometry in
a straightforward fashion. The second test is probably
easier to implement, as it only involves detecting if two
circular arcs intersect.

--
Christer Ericson
http://realtimecollisiondetection.net/

Page 2 of 2   << first < 1 2
Related Posts
  • Subject
  • Posted In
  • Date