Jump to content
  • Advertisement
Sign in to follow this  
yahastu

efficient convex polygon test? [solved]

This topic is 3406 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
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!