Author Topic: Polygon algorithm  (Read 4752 times)

0 Members and 1 Guest are viewing this topic.

Offline Jim Bauwens

  • Lua! Nspire! Linux!
  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1881
  • Rating: +206/-7
  • Linux!
    • View Profile
    • nothing...
Polygon algorithm
« 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 :)

Offline Xeda112358

  • they/them
  • Moderator
  • LV12 Extreme Poster (Next: 5000)
  • ************
  • Posts: 4704
  • Rating: +719/-6
  • Calc-u-lator, do doo doo do do do.
    • View Profile
Re: Polygon algorithm
« Reply #1 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?

Offline TIfanx1999

  • ಠ_ಠ ( ͡° ͜ʖ ͡°)
  • CoT Emeritus
  • LV13 Extreme Addict (Next: 9001)
  • *
  • Posts: 6173
  • Rating: +191/-9
    • View Profile
Re: Polygon algorithm
« Reply #2 on: April 05, 2012, 07:52:26 am »
This should probably be moved. What is this for Jim, a computer programming project?

Offline Jim Bauwens

  • Lua! Nspire! Linux!
  • Editor
  • LV10 31337 u53r (Next: 2000)
  • **********
  • Posts: 1881
  • Rating: +206/-7
  • Linux!
    • View Profile
    • nothing...
Re: Polygon algorithm
« Reply #3 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 :)

Offline ZippyDee

  • LV8 Addict (Next: 1000)
  • ********
  • Posts: 729
  • Rating: +83/-8
  • Why not zoidberg?
    • View Profile
Re: Polygon algorithm
« Reply #4 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.
There's something about Tuesday...


Pushpins 'n' stuff...


Offline DJ Omnimaga

  • Clacualters are teh gr33t
  • CoT Emeritus
  • LV15 Omnimagician (Next: --)
  • *
  • Posts: 55941
  • Rating: +3154/-232
  • CodeWalrus founder & retired Omnimaga founder
    • View Profile
    • Dream of Omnimaga Music
Re: Polygon algorithm
« Reply #5 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 :'( )