Gamestudio Links
Zorro Links
Newest Posts
Help with Data import to T1
by AndrewAMD
45 minutes 48 seconds ago
Using ":L" & ":S" causes 2 possible bug(s) or is it bad coding?
by AndrewAMD
Today at 03:54
Correlation -1.#IND00
by AndrewAMD
01/21/19 17:37
Basic thread safety question
by Superku
01/20/19 18:15
Blog Post: Get Historical Data from Darwinex REST API w/ Zorro
by AndrewAMD
01/19/19 22:19
Reseting a static variable - the next day
by OptimusPrime
01/19/19 19:48
Train algorithms separatery
by 3dgamelight
01/18/19 10:37
AUM Magazine
Latest Screens
Worst Case Z
AckCon'18 - Lotter vs the World 2 - Preview Release
Evonet Beta v1.0 : Online Project Development Template
Lake scene
Who's Online
12 registered (Iglarion, AndrewAMD, Michael_Schwarz, ags, chsmac85, kvm, ibne, alibaba, 3 invisible), 431 Guests and 6 Spiders online.
Key: Admin, Global Mod, Mod
Newest Members
laz, ramonne, SibJac, Evael, NRW
18156 Registered Users
Topic Options
Rate This Topic
#464687 - 03/06/17 11:13 ear clipping triangulation of simple polygons
txesmi Online
Serious User

Registered: 06/13/07
Posts: 1201
Loc: Hiporope and its pain
Hi!
A simple polygon has no shared vertex, crossing edges or holes and it is sorted counter-clockwise on right handed coordinates. The algorithm takes three contiguos points, checks the angle between segments and checks if any other point is not contained by the triangle in order to set it as a valid triangle. This method is far from been the fastest but it is pretty easy to follow.


DOWNLOAD
Draw a polygon by mouse left button and triangulate it by mouse right button. You can watch the process by uncommenting SHOW_BUILT definition on 'simple_polygon.h'

Enjoy!

Top
#464689 - 03/06/17 11:27 Re: ear clipping triangulation of simple polygons [Re: txesmi]
Superku Offline
Senior Expert

Registered: 09/13/03
Posts: 6795
Loc: Kiel (Germany)
Very interesting, thanks for sharing!
_________________________
"Falls das Resultat nicht einfach nur dermassen gut aussieht, sollten Sie nochmal von vorn anfangen..." - Manual

Superku The Game

Severely outdated footage: http://store.steampowered.com/app/407570

Top
#464696 - 03/06/17 13:17 Re: ear clipping triangulation of simple polygons [Re: Superku]
Kartoffel Offline
Expert

Registered: 06/11/09
Posts: 2210
Loc: Bavaria, Germany
cool stuff. can be pretty helpful when filling shapes... I might even need this laugh
_________________________
POTATO-MAN saves the day! - Random

Top
#464698 - 03/06/17 14:17 Re: ear clipping triangulation of simple polygons [Re: Kartoffel]
20BN Offline
Member

Registered: 02/08/03
Posts: 118
Loc: RP China
thanks for sharing!

it's very useful for pathfinding!!!!!!!!!

Top
#464713 - 03/07/17 06:27 Re: ear clipping triangulation of simple polygons [Re: 20BN]
txesmi Online
Serious User

Registered: 06/13/07
Posts: 1201
Loc: Hiporope and its pain
glad of been helpfull wink

Top
#464921 - 03/17/17 00:31 Re: ear clipping triangulation of simple polygons [Re: txesmi]
PadMalcom Offline
Serious User

Registered: 03/08/06
Posts: 1993
Loc: Karlsruhe
Cool, how difficult would it be to extend it to handle holes?

Top
#464941 - 03/18/17 08:20 Re: ear clipping triangulation of simple polygons [Re: PadMalcom]
txesmi Online
Serious User

Registered: 06/13/07
Posts: 1201
Loc: Hiporope and its pain
Originally Posted By: PadMalcom
Cool, how difficult would it be to extend it to handle holes?
As far as I read it is not hard to achieve. It is planned wink

Top
#464943 - 03/18/17 15:08 Re: ear clipping triangulation of simple polygons [Re: txesmi]
Kartoffel Offline
Expert

Registered: 06/11/09
Posts: 2210
Loc: Bavaria, Germany
Another useful feature would be selecting clockwise/counter-clockwise triangle creation automatically. This should work by adding the relative angles between all lines (of the outline) and checking if the result is greater or less than 0. (theoretically only +360 or -360 are possible).
_________________________
POTATO-MAN saves the day! - Random

Top
#472916 - 05/29/18 17:46 Re: ear clipping triangulation of simple polygons [Re: Kartoffel]
3run Offline
Senior Expert

Registered: 05/05/09
Posts: 5104
Loc: Caucasus
txesmi@ man, you are awesome, just as always! thank you very much for this contribution!
_________________________
Looking for free stuff?? Take a look here: http://badcom.at.ua

Top
#472925 - 05/30/18 10:41 Re: ear clipping triangulation of simple polygons [Re: 3run]
txesmi Online
Serious User

Registered: 06/13/07
Posts: 1201
Loc: Hiporope and its pain
thanks laugh enjoy!

Top


Moderator:  HeelX, Lukas, Rei_Ayanami, VeT 

Gamestudio download | chip programmers | Zorro platform | shop | Data Protection Policy

oP group Germany GmbH | Birkenstr. 25-27 | 63549 Ronneburg / Germany | info (at) opgroup.de