bool positive = false;
for (int i = 0; i < points.size(); ++i)
{
vector3 A = points.at((i+1) % points.size()) - points.at(i);
vector3 B = points.at((i+2) % points.size()) - points.at((i+1) % points.size());
float dot_product;
float temp_ax = A.x;
A.x = -A.z;
A.z = temp_ax;
A.y = 0;
B.y = 0;
dot_product = A * B;
if (i == 0 && dot_product > 0)
{
positive = true;
}
if (i == 0 && dot_product <= 0)
{
positive = false;
}
if (dot_product > 0 && !positive) return false;
if (dot_product <= 0 && positive) return false;
}
return true;
Polygon convexity test: can't get it right
Author
I looked at this topic and implemented a few ideas, but nothing ever covers every special case I get. I have a list of vertices in clockwise or anti clockwise order and need to know if they are convex. There are no duplicate vertices. I will post my own take on it, maybe it's just a simple error I can't find. Appreciate any help!
http://www.gamedev.net/community/forums/topic.asp?topic_id=467104
I need this to work in 3d space, but I check beforehand in a different function if all the vertices lie in the same plane. This means my vertex list is essentially 2d. Now I still need to know which axis I can drop, so I loop for all axis values, calculate the difference and sum the difference up. The two axis which have the biggest sum, get taken for consideration.
e.g:
Vertex 1: x = 5; z = -5; y = 5;
Vertex 2: x = 6; z = -5; y = 10;
x-axis sum = abs(5-6) = 1
z-axis sum = abs(-5--5) = 0
y-axis sum = abs(5-10) = 5
I determine that x and y must be the dominant axis to form the polygon.
This is how I try at the moment: (i left the parts out, where I determine the dominant axis, because the code would be too long. Here I always drop the y values.
I essentially check if the sign of the dotproduct between two vectors pointing outwards from one vertex ever changes.
The next thing I'm gonna try, is this:
http://demonstrations.wolfram.com/AnEfficientTestForAPointToBeInAConvexPolygon/
I was a bit reluctant to use this method, because I usually make mistakes implementing mathematical texts, since I'm not a native english speaker.
You should probably be using crossproduct in 2d instead.
Assume polygone is checked in x-y plane and p is circular array of size N:
Assume polygone is checked in x-y plane and p is circular array of size N:
for n in 1..N if sign(cross(p[n].xy, p[n+1].xy).z) != sign(cross(p[n].xy, p[n+2].xy).z) return falsereturn true;
Alright, took me a while to do, first time I did something in illustrator; but the following picture shows some things you can use to determine convexity:
So, you'd iterate over all vertices, and determine the direction (length not necessary, so just the sign is enough) of the cross-product between the 2 line-segments from the next and previous vertices to your current vertex. These signs should be equal for all vertices (either positive or negative).
Then the special case is when all angles ARE inward, but the total angles added are N * 360 degree, with N > 1 (ie. is goes 'round' twice or more, and thus overlap itself). Where ultimately the angle in total, as described in the picture, is (round-a-bout, take care with float in-precision) 360 degree.
I'm not aware if this is the most efficient method.
So, you'd iterate over all vertices, and determine the direction (length not necessary, so just the sign is enough) of the cross-product between the 2 line-segments from the next and previous vertices to your current vertex. These signs should be equal for all vertices (either positive or negative).
Then the special case is when all angles ARE inward, but the total angles added are N * 360 degree, with N > 1 (ie. is goes 'round' twice or more, and thus overlap itself). Where ultimately the angle in total, as described in the picture, is (round-a-bout, take care with float in-precision) 360 degree.
I'm not aware if this is the most efficient method.
Author
Do you mean, that just the neighbouring line segments have to have the same sign in z, or do they all have to have the same. Because mzeo77 describes it so, that only neighbouring z signs have to be equal. But overall, there could be any number of change in signs.
This doesn't work either:
@Decrius:
This means, even though the cross product test fails, I have to test further everytime and add up all angles? If they are exactly 360 or a multiple of it, then the test succeeds anyway, correct?
This doesn't work either:
vector3 signs(0,0,0); for (int i = 0; i < points.size(); ++i) { vector3 A = points.at((i+1) % points.size()) - points.at(i); vector3 B = points.at((i+2) % points.size()) - points.at((i+1) % points.size()); vector3 tempsigns = Navigation::CrossProduct(A,B).normalize(); if (i == 0) { signs = Navigation::CrossProduct(A,B); signs = signs.normalize(); } if (signs.x != tempsigns.x || signs.y != tempsigns.y || signs.z != tempsigns.z) { return false; } } return true;@Decrius:
This means, even though the cross product test fails, I have to test further everytime and add up all angles? If they are exactly 360 or a multiple of it, then the test succeeds anyway, correct?
Quote:Original post by Meai
This means, even though the cross product test fails, I have to test further everytime and add up all angles? If they are exactly 360 or a multiple of it, then the test succeeds anyway, correct?
Almost. All cross-products must have the same sign! If one has a positive cross-product, it means that the angle as in the picture is to the left (or right, but lets say left) from the "current" line segment. It "turns" a number of degree's to the left.
If it is negative, it turns to the other side. So the next line-segment would not turn some degree to the left, but to the right when viewed from the "current" line-segment.
If you have 2 different cross-products, this means it is not convex! Get some paper and draw some cases. What if one segment points to the left after the previous, and the next to the right? Can it ever be convex?
So, first test if all cross-products have the same sign. If not, break out (this can be an early breakout) and return false for not being convex. if all cross-products have equal signs, you can iterate again (or have done this in the cross-product-calculating loop) and make sure the angles added are not larger then 2*PI (or larger then 3*PI, since radians added will only ever yield N*2*PI, and you have to be aware of floating point in-precision).
By angles I mean the angles shown in my picture, not the angles _within_ the polygon.
When I came up with such a function myself, I came up with a simple method. You don't need to discard one axis for it either.
All I do is that for every line segment, detect if all other points in the polygon lie on the same side of that segment. If there is any line segment with points from the polygon that lie on either side, then it's concave.
To determine if points are on the same side or not, you can use dot products to calcluate the perpendicular component of the vector of each vertex from one of the points in the line segment, and then take the dot product of two of these. If it's negative, then they are on opposite sides.
This method also detects self-intersecting polygons where the total angles add up to 720 etc as not being convex. With a careful selection of points to use for sided-ness testing, this method can be O(n).
All I do is that for every line segment, detect if all other points in the polygon lie on the same side of that segment. If there is any line segment with points from the polygon that lie on either side, then it's concave.
To determine if points are on the same side or not, you can use dot products to calcluate the perpendicular component of the vector of each vertex from one of the points in the line segment, and then take the dot product of two of these. If it's negative, then they are on opposite sides.
This method also detects self-intersecting polygons where the total angles add up to 720 etc as not being convex. With a careful selection of points to use for sided-ness testing, this method can be O(n).
Quote:Original post by iMalc
With a careful selection of points to use for sided-ness testing, this method can be O(n).
How do you want to make a careful selection? If done the naive way this is O(n^2).
The method I described is neither optimal I guess, but it does only 1 dot and 1 cross product per vertex, so it is O(n) without any careful selection.
Author
@Decrius:
In your picture, you divided the dot product by "c" and "a", shouldn't that read that "c" and "b"?
What is an inward angle? Angles < 90?
So if the angle is larger than 2*PI, the polygon is not convex? I'm not following why we would need the whole thing with the angles.
A cross product between 2 vectors only ever returns a positive number, if the angle between the vectors forming the cross product is < 180, right?
Well I'll keep trying, but currently I don't have any success. Here is my take on iMalc's idea:
@iMalc: I didn't understand this part fully:
but I took the idea, and implemented it a way I could think of:
But that isn't working in all cases either! If this code is correct, maybe my vertices just arent always in the same order. Very unlikely, but heck, I'd believe in anything right now.
In your picture, you divided the dot product by "c" and "a", shouldn't that read that "c" and "b"?
Quote:Then the special case is when all angles ARE inward
What is an inward angle? Angles < 90?
Quote:
and make sure the angles added are not larger then 2*PI (or larger then 3*PI, since radians added will only ever yield N*2*PI
So if the angle is larger than 2*PI, the polygon is not convex? I'm not following why we would need the whole thing with the angles.
A cross product between 2 vectors only ever returns a positive number, if the angle between the vectors forming the cross product is < 180, right?
Well I'll keep trying, but currently I don't have any success. Here is my take on iMalc's idea:
@iMalc: I didn't understand this part fully:
Quote:
To determine if points are on the same side or not, you can use dot products to calcluate the perpendicular component of the vector of each vertex from one of the points in the line segment, and then take the dot product of two of these. If it's negative, then they are on opposite sides.
but I took the idea, and implemented it a way I could think of:
for (int i = 0; i < points.size(); ++i) { vector3 lineSegment = points.at((i+1)%points.size()) - points.at(i); for (int j = 0; j < points.size(); ++j) { // finding the normal to the line segment float distanceToClosest = lineSegment * (points.at(j) - points.at(i)); vector3 closestPoint = points.at(i) + (distanceToClosest * lineSegment.normalize()); vector3 lineSegmentNormal = points.at(j) - closestPoint; // the line segment normal * the vector from one of the line segment points (=closestPoint) to the point we currently test must be > 0 float result = lineSegmentNormal * (points.at(j) - closestPoint); if (result < 0.0f) { return false; } } } return true;But that isn't working in all cases either! If this code is correct, maybe my vertices just arent always in the same order. Very unlikely, but heck, I'd believe in anything right now.
Quote:Original post by Meai
In your picture, you divided the dot product by "c" and "a", shouldn't that read that "c" and "b"?
No, c and a. In the picture A-C means a to the right pointing vector of length |c| starting in C (|c| = |A - C| = sqrt((A.x - C.x)^2 + (A.y - C.y)^2 + (A.z - C.z)^2)). B-A is a to the top-left pointing vector starting in A. So, around vertex A we have a vector pointing from the previous vertex (C) to the current vertex (A), and a vector pointing from the current vertex (A) to the next vertex (B).
Quote:Original post by Meai
What is an inward angle? Angles < 90?
Sorry, that was vague. With inward I meant an angle that makes the next line-segment turn to the same direction as all other line-segments seen from the previous line-segment.
Imagine we traverse the contour of the polygon with a car in positive (counter-clockwise) direction. We start at vertex A, we go to B. At B we need to turn an angle 'beta' to the left. Riding on we come to C, then again we need to turn left, with angle 'gamma', at A with angle 'alpha' and we're back at the begin position.
We keep going left. If we'd go right at one vertex, it means the polygon is concave aka. not convex! With the car, we keep going "inward", sorry somehow that word feels natural... ;)
Quote:Original post by Meai
So if the angle is larger than 2*PI, the polygon is not convex? I'm not following why we would need the whole thing with the angles.
A cross product between 2 vectors only ever returns a positive number, if the angle between the vectors forming the cross product is < 180, right?
No, the cross-product can also give negative numbers. Namely: (I x J) = -(J x I) (think about this!). It doesn't matter thus what order we apply the cross-product, as long as we're consistent throughout the algorithm. We only need to know if they are equal in sign.
If the angle between 2 vectors is 0 or 180 degree, the cross-product is zero.
In the car example above, the car turned exactly 360 degree (to the left). However, if we only check, we can allow contours like below, because all cross-products have the same sign!
In this case, the angles added are 720 degree = 4 * PI; so the polygon is not convex!
Author
Thank you Decrius, it's pretty clear now. Tomorrow I have to study for an unrelated test, but then I'll implement it...and probably find something to ask you again :)
btw: fancy graphics!
btw: fancy graphics!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
