efficient convex polygon test? [solved]
I want to do the following:
If a point P can be added to a convex polygon without breaking convexity, then add it.
I do not care if the polygon points are ordered or not. I want it to be efficient for polygons with large numbers of edges.
It seems that any of the following tests could be used to facilitate the solution:
a) A test to see if a point is within an ordered convex polygon
b) A test to see if a point is within an unordered convex polygon
c) A test to see if a point is within an ordered simple polygon
d) A test to see if a point is within an unordered simple polygon
e) A test to see if a point is within an ordered polygon
f) A test to see if a point is within an unordered polygon
g) A test to see if an ordered simple polygon is convex
h) A test to see if an unordered simple polygon is convex
i) A test to see if an ordered polygon is convex
j) A test to see if an unordered polygon is convex
However, there are multiple ways to do each of those tests! And moreover, I am not interested in which test is individually fastest, but which test can be used to complete the entire procedure the fastest.
Some of the test I'm aware of are:
a) An ordered simple polygon is convex if the perp dot product between all consecutive vectors has the same sign.
b) According to [http://mathworld.wolfram.com/ConvexPolygon.html ], a more efficient test than (a) exists which works for arbitrary polygons, but I do not know what it is.
c) An efficient test to see if a point is within a convex polygon is presented here: http://demonstrations.wolfram.com/AnEfficientTestForAPointToBeInAConvexPolygon/
d) There's a method with the cross product too...
Ok, there are obviously a lot more methods. Surely someone has tested these things out and can give me some pointers?
Edit: I'm marking this as solved although I'm not going to go into a detailed explanation of the best method.
[Edited by - yahastu on January 24, 2009 9:14:13 PM]
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement