Jump to content
  • Advertisement
sevenfold1

Non-triangulated earcutting?

Recommended Posts

Hello,
I'm looking for 2D polygon earcutting routine that creates a non-triangulated output.  All of the earcutting examples I've seen so far output to triangles only.  However, I would like to earcut a concave 2D shape, but keep the convex pieces as large as possible.  Thanks.
 

Share this post


Link to post
Share on other sites
Advertisement
30 minutes ago, sevenfold1 said:

Hello,
I'm looking for 2D polygon earcutting routine that creates a non-triangulated output.  All of the earcutting examples I've seen so far output to triangles only.  However, I would like to earcut a concave 2D shape, but keep the convex pieces as large as possible.  Thanks.
 

AFAIK, earcutting (aka earclipping) explicitly describes a method of triangulation so, yeah, it's always going to produce triangles. You probably want to try looking for polygon decomposition, or something akin to that? A quick search revealed this algorithm that has some drawbacks but appears to meet your basic requirement, the same page has a second algorithm (Kiel's) that is slower but produces an optimal partition.

What do you need it for?

Share this post


Link to post
Share on other sites

Yes, 2D polygon decomposition is what I'm looking for.  I was hoping earclipping could be converted to output polygons instead of triangles. It doesn't have to be optimal.

I'm trying to speed up 2D polygon intersection, so I would rather have pieces as large as possible, instead of looping through thousands of triangles.

Thanks for the links.  I will check it out.

Share this post


Link to post
Share on other sites
Posted (edited)

I was able to compile both demos, and it seems the keil demo works, for the most part.  But the program hangs on some simple shapes, so I'not sure about its robustness.  The bayazit demo runs too, but it crashes on all shapes.  Couldn't get it to work at all.  Well, it's a good start.

Edited by sevenfold1

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

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

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!