• Advertisement
Sign in to follow this  

efficient convex polygon test? [solved]

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

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]

Share this post


Link to post
Share on other sites
Advertisement
Sign in to follow this  

  • Advertisement