# efficient convex polygon test? [solved]

This topic is 3581 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## 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]

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633300
• Total Posts
3011267
• ### Who's Online (See full list)

There are no registered users currently online

×