Jump to content
  • Advertisement
Sign in to follow this  
cmac

Optimal triangulation algorithm for 2D concave hull

This topic is 415 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 was avoiding posting here because there's plenty of information on triangulation out there, but I'm beginning to find it more of a curse than a blessing due to how specified my case is and how many triangulation algorithms there are.

I have 2D potentially-concave polygons that are defined as an ordered list of vertices in clockwise order. These vertices define the hull or outline of the shape - no vertices are inside the polygon. I was looking at ear-clipping, but the order of complexity seems like it could be improved with a better algorithm.

Anyone have any good resources or personal knowledge specific to my case?

Share this post


Link to post
Share on other sites
Advertisement

Thanks for the input. I was thinking partitioning into convex would be faster, so maybe I'll give that a shot.

My assumptions come from this paper: https://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf

Particularly, in the first section:

Quote

The simplest algorithm, called ear clipping, is the algorithm described in this document. The order is O(n 2 ). Algorithms with better asymptotic order exist, but are more difficult to implement. Horizontal decomposition into trapezoids followed by identification of monotone polygons that are themselves triangulated is an O(n log n) algorithm [1, 3]. An improvement using an incremental randomized algorithm produces an O(n log∗ n) where log∗ n is the iterated logarithm function [5]. This function is effectively a constant for very large n that you would see in practice, so for all practical purposes the randomized method is linear time. An O(n) algorithm exists in theory [2], but is quite complicated. It appears that no implementation is publicly available

To provide a bit of context, I need this for a simple Unity plugin. Originally I was making it to aid with development of one of my game projects, but after seeing there weren't any good, simple and cheap 2D polygon tools in the asset store, I figured I'd try to optimize it and put it up for sale for a low price. For that reason, I'd like usage of the tool to be as seamless as possible. Ideally the polygons would re-triangulate their meshes every update if a vertex was moved, but if it causes any lag at all I'd rather avoid it. Additionally, I'm personally going for a 2D Sonic-esque physics simulation using polygons/edges rather than heightmaps (old school optimization for the 16-bit games), so some ramps and curves would involve a lot of vertices. Considering that, O(n^2) complexity seems a bit risky for constant triangulation updates. I was curious if anyone had any leads on the O(n) theoretical algorithm, but it sounds like a Unicorn so I'll leave it at that.

I'll go ahead with convex-partitioning, but if anyone has anything new to add please feel free to do so.

Share this post


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

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!