#### Archived

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

# Determine Point in Polygon 2D

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

## 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 on other sites
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 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 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 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 on other sites
What''s wrong with the API? Are you not developing for Windows, or was I just wrong?

##### 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 on other sites
Do you mean ''which corner is nearest?'', in which case, it''s just the nearest corner (measure using pythagorous).

##### 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 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.

1. 1
Rutin
42
2. 2
3. 3
4. 4
5. 5

• 18
• 20
• 14
• 14
• 9
• ### Forum Statistics

• Total Topics
633368
• Total Posts
3011538
• ### Who's Online (See full list)

There are no registered users currently online

×