Sign in to follow this  
Dhaos

Testing bounds of a polygon (wether or not a mouse-click is inside or not)

Recommended Posts

Dhaos    122
How does one test if a point is within a polygon? I believe I understand the basics: Take two vertices/points and calculate the slope. Split said slope into two ratios 1x:?y and 1y:?x. Take the cursor and test x vs y or y vs x. Decide if the opposing x or y (ie the mouse/cursor) needs to be above/below/left/right of said slope line this is where I am having problems The quirk here is when you rotate the vertices round and abot, they get out of position so figuring out wether or not you need to be above the slope, below the slope, to the left or right of the slope. (If I'm looking at the actual image I can tell but getting the code/computer to understand is the issue) Maybe I need a to develop a sorting algorithm? I'm really lost and perhaps a psudo code example would help or a link to the math behind this issue. For all I know there is a stupidly simple way of doing this or its absurdly complicated.

Share this post


Link to post
Share on other sites
jyk    2094
Don't use the slope/intercept form for this. Instead, convert the polygon edges to hyperplane form and perform a series of half-space tests on the point. (Post back if you need more details - it's really less complicated than it sounds :)

Share this post


Link to post
Share on other sites
Dhaos    122
Yeah that wording is confusing me please elaborate in more detail what you mean. (I am unfamiliar with that method)

Share this post


Link to post
Share on other sites
jyk    2094
Basically, what you want to do is test the point against the infinite lines running through each of the polygon edges (I'm assuming here that the polygon is convex). If the point is on the 'same side' of each of these lines, it's inside the polygon.

To facilitate performing these tests, we convert the polygon edges into hyperplane form - basically, the 'infinite lines' I mentioned, represented using a unit-length normal and a distance from the origin along that normal. (The normals don't actually need to be unit length, but we'll go ahead and normalize them anyway.)
// p1 and p2 are the endpoints of the edge
vector2 normal = p2 - p1;
normal = normal.perp(); // perp(x, y) = -y, x
normal.normalize();
float distance = dot(p1, normal);

// We now have the edge in hyperplane form. To test a point against the edge:

float d = dot(point, normal);
if (d < distance) {
// Point is 'behind' edge
} else if (d >= distance) {
// Point is on or 'in front of' edge
}

// You perform the above test for each of the edges, and if the point is on
// the same side for each edge, it's in the polygon. (Whether 'same side'
// means in front of or behind depends on how you set up the edge normals.)
Does that help?

Share this post


Link to post
Share on other sites
Dhaos    122
First let me see if I'm following that method conceptually:
--------------------------------------------------------------

vector2 normal = p2 - p1;
normal = normal.perp(); // perp(x, y) = -y, x
normal.normalize();

get the direction of the line
--------------------------------------------------------------

float distance = dot(p1, normal);

get the length of the line
--------------------------------------------------------------

float d = dot(point, normal);
if (d < distance){//Point is 'behind' edge}
else if (d >= distance){//Point is on or 'in front of' edge}

a bit lost here on what this is doing, sorry its just sometimes it takes me a bit to understand even the most simplest of things.
--------------------------------------------------------------

"Basically, what you want to do is test the point against the infinite lines running through each of the polygon edges (I'm assuming here that the polygon is convex). If the point is on the 'same side' of each of these lines, it's inside the polygon.

To facilitate performing these tests, we convert the polygon edges into hyperplane form - basically, the 'infinite lines' I mentioned, represented using a unit-length normal and a distance from the origin along that normal. (The normals don't actually need to be unit length, but we'll go ahead and normalize them anyway.)"
--------------------------------------------------------------

The bold areas still confuse me a bit. I suppose when I look at this, I'm not understanding *why* it will work. (I'm just not picturing it). Do you know of any images that you know that visually demonstrate what this is doing exactly? And in this method, what *is* the origin? The first vertice used or?

*I understand the basics of the math used, vectors, normals, cross/dot products etc, its just I have a difficult time understanding why they are being used in this example, sorry for needing so much explanation.

Thank you for your help thus far, this is becoming very educational

Share this post


Link to post
Share on other sites
jyk    2094
The 'perp' part of the code doesn't get the direction of the line, but rather the direction of a vector perpendicular to the line (called the 'normal'). As for the 'distance' part, it is not the length of the line, but rather a measure of where the line falls in 2-d space (the 'origin' I mentioned is the origin of the coordinate system, that is, 0,0).

A diagram would probably help, but I don't have time at the moment to put one together, so...

If you've got a piece of paper handy, draw a convex polygon with 5 sides or so. Each edge is a line segment. Now, take a ruler and line it up with an edge of the polygon, and draw a (lighter) line that is as long as possible given the size of the paper (that is, it should hit the edges of the paper). Do this for each edge.

Now, for each edge, draw a little arrow starting at the middle of the edge, and perpendicular to the edge. It doesn't matter whether they point into the polygon or out of it, as long it's consistent (that is, they all point in or they all point out).

Now, draw a few points, some inside the polygon, and some outside. You will find that for the points that are inside the polygon, the point is on the 'same side' of each of the lines passing through the polygon edges. For points that are outside the polygon, this will not be the case.

That's the best way I can think of to explain it, so I hope that'll be helpful. Once you understand the process visually, I imagine that converting it to code will become less daunting.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this