• Advertisement

Archived

This topic is now archived and is closed to further replies.

Determine Point in Polygon 2D

This topic is 6210 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi I am seraching a function to determine if a point is in a 2D polygon and which point of polygon is next to the point Thank you

Share this post


Link to post
Share on other sites
Advertisement
I''m fairly sure there''s a Windows API function - PointInPolygon - yep, you can do it in one API call, without writing the code yourself

Share this post


Link to post
Share on other sites
Think about the polygon as a number of lines connected togheter
step to the first line , use dotproduc to determine if the point ( x,y ) is on the positive or negative side of the line , if its in the positive , set a flag counter and add to this 1 , continue with the next line , and do the same thing , once finished if the flag counter has the same value of the lines that build up the polygon , the point is in , i hope its clear
for you though ,good programming...


Share this post


Link to post
Share on other sites
This was recently part of a USACO (high-school programming contest) problem. My solution worked, but I have recently been informed of the easiest way to do it. Take a horizontal ray from negative infinity tothe point, and count the intersections with the polygon. As long as the number is odd, the point is inside.

-SerDagger

Share this post


Link to post
Share on other sites
Yep

I am using PtInPoly and tried this:

Public Function InsidePolygon(polygon() As Point, N As Long, p As Point)
Dim counter As Long
Dim i As Long
Dim xinters As Double
Dim p1 As Point, p2 As Point
p1 = polygon(0)
For i = 1 To N Step 1
p2 = polygon(i Mod N)
If (p.y > MIN(p1.y, p2.y)) Then
If (p.y <= MAX(p1.y, p2.y)) Then
If (p.x <= MAX(p1.x, p2.x)) Then
If (p1.y <> p2.y) Then
xinters = (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x
If ((p1.x = p2.x) Or (p.x <= xinters)) Then
counter = counter + 1
End If
End If
End If
End If
End If
p1 = p2
Next
If (counter Mod 2 = 0) Then
InsidePolygon = OUTSIDE
Else
InsidePolygon = INSIDE
End If
End Function

But I don''t know how I get this:
---1
--++++
-2+++++3
--+P++
---4

P is next to Point 4 of the Poly
How can I do this ?


Share this post


Link to post
Share on other sites
Yes, after my API call I know the point is in Poly,
but I don't know where the point is.

I am searching a Function like this:
Is the Point in the Poly ? Yes
Which PolyPoint is next to the Point ? 1,2,3 or 4


The first question is done by Api,
but how can I handle the second ?

The Dot Product doesn't help me !


Edited by - eis_os on February 19, 2001 11:25:53 AM

Edited by - eis_os on February 19, 2001 12:27:05 PM

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Yep, I want to know which corner is nearest.

Is there any source code for this to make it fast:
dj = |x1-x2|+|y2-y2|

Because this would produce a big IF structure,
to search the nearest point.

Share this post


Link to post
Share on other sites
Yep, I want to know which corner is nearest.

Is there any source code for this to make it fast:
dj = |x1-x2|+|y2-y2|

Because this would produce a big IF structure,
to search the nearest point.

Share this post


Link to post
Share on other sites
How are the corners of the polygon stored in your program?

If it''s just a list in counter-clockwise order, tehn I would think you could only really loop through the list of points and use the pathagorean theorem.

If you have them sorted somehow, then perhaps you can cut down the search a little that way...

Perhaps instead of using the PntInPoly method you could create a new one which returns -1 if the point is not in the poly, and the # of the poly otherwise, that way you can use the other algorithim that v71 suggeested and cut down a little of the work - this at least might save going through the list of points 2 times?

Just a suggestion..

Share this post


Link to post
Share on other sites
I know very fast that a point is in a polygon.

But how I can solve the problem ''which corner is nearest?''

Flanders: I am not exactly what you mean by use the pathagorean theorem for this Problem.

I know the distance between two points with
dj(i) = |x-p(i).x|+|y-p(i).y|

Dj(i) is the Distance of i, then
I have to look on n distances which is the shortest.

How I can do that very fast ?
The method below is two slow and not for n Polygons:

FORi1 = 1 To 4
IF dj(i) < dj(1) AND dj(i) < dj(2) AND dj(i) < dj(3) AND dj(i) < dj(4) = TRUE THEN PointInPoly = n
NEXT

My Polys are stored in counter-clockwise order.

Share this post


Link to post
Share on other sites

  • Advertisement