Jump to content
  • Advertisement

Archived

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

eis_os

Determine Point in Polygon 2D

This topic is 6391 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
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

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!