Omnimaga

General Discussion => Other Discussions => Math and Science => Topic started by: Jim Bauwens on April 05, 2012, 05:46:32 am

Title: Polygon algorithm
Post by: Jim Bauwens on April 05, 2012, 05:46:32 am

Does anyone here have a good algorithm to split a concave polygon in multiple convex ones?
I've looked a bit, but can't find an easy solution. In the worst case I just could use triangulation, but that's overkill in my opinion :P

TIA :)

Title: Re: Polygon algorithm
Post by: Xeda112358 on April 05, 2012, 07:22:03 am

My first thought was splitting it up into triangles, but it looks like you don't want that? What you can do is look for angles >180 degrees and connect pairs of these points. If you have an odd number of these points, connect it to an angle further away. (you might need to test the angle the new line forms).

EDIT: Also, maybe this is for the math section?

Title: Re: Polygon algorithm
Post by: TIfanx1999 on April 05, 2012, 07:52:26 am

This should probably be moved. What is this for Jim, a computer programming project?

Title: Re: Polygon algorithm
Post by: Jim Bauwens on April 05, 2012, 08:13:16 am

Well, it's for multiple stuff.
I would have put it in the math section if I knew we had one :P (I never really browse the forum using the boards)

Xeda, triangulation is fine but I rather would have bigger polygons as it will use lower resources in some of my stuff.
I'll see if I can use your method, thanks :)

Title: Re: Polygon algorithm
Post by: ZippyDee on April 15, 2012, 11:14:45 pm

Triangulate, then remove unnecessary vertices. That's honestly the best way to do it with any simplicity. Anything more and you'll be shooting yourself in the head.

Title: Re: Polygon algorithm
Post by: DJ Omnimaga on April 16, 2012, 03:24:01 am

@Jimbauwens new Nspire project (3D) on the way? :P (Actually Calc84maniac had one, which is in Omnimaga's banner, but he quit working on it 2 years ago :'( )