Jump to content
  • Advertisement

Archived

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

Pexi

Point in polygon

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

Once I had a pice of code that checked if the given point 2d was inside an polygon(4 verts).... I lost it.... Could somebody give me an fast and easy pointinpoly function....

Share this post


Link to post
Share on other sites
Advertisement
take the point in question, and project a ray from it (any direction will do)

check to see if that ray crosses each of the lines in the poly. if you get an even number of crossings (0,2,etc), its not in the poly.

Share this post


Link to post
Share on other sites
You can get the equation of the 4 lines bounding the poly by solving the standard y=mx+b equation of a line. Now plug in the value of your point. If you get a value that either below or above an opposite pair of lines, then the point is out side the poly. If it is between the lines (above one, below the other), then check the other pair. A point is in the poly if and only if it is between both pairs of oppsite sides.

See crude Diagram:

O1

-----y1------

I

------y2-----

O2

y1,y2 are lines on opposite side of poly.
I, O1, and O2 are points.

O1 is outside the poly because y1(O1.x) and y2 (O1.x) are both positive
O2 is outside the poly because y1(O2.x) and y2 (O2.x) are both negative

I is between the lines because y1(I.x) is negative, but y2(I.x) is positive

Share this post


Link to post
Share on other sites
Invective: TANSTAAFL''s method is the standard inside test by counting intersections. It''ll run circles around solving for four given lines (and it works better for arbitrarily oriented lines, where the point in question may be a vertex - intersecting both lines exactly).

Share this post


Link to post
Share on other sites
Just some clarification on tans'' method. There is at least one special case that I can see that must be taken into account. Assuming your polygon is limited to 4 verts than this works great however, there is a case where extending a line in one direction might run through a single vertex giving you the result of being inside the poly when in fact its not. Also dont forget the case where your point is ON a poly''s vertex

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!