<p>Have you considered <a href="http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html" rel="nofollow">Martin Held's "FIST" project</a>?  (See also <a href="http://www.springerlink.com/content/ermlr10j8pj48tl2/" rel="nofollow">Martin's paper</a>.)</p>

CC BY-SA 2.5
2011-01-09T05:54:28.723Z
2011-01-11T22:06:16.083Z
2011-01-11T22:06:16.083Z
Jeffε
<p>Have you considered <a href="http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/A%20Simple%20and%20fast.pdf" rel="nofollow">Seidel's algorithm</a> ? </p>

CC BY-SA 3.0
2017-04-12T13:30:32.910Z
Seidel's algorithm, though very fast,  needs modification to handle self-intersections. It's not impossible, but not immediately obvious.
Simon F
CC BY-SA 2.5
2011-01-06T18:13:59.300Z
2011-01-06T18:13:59.300Z
Suresh Venkat
<p>I think you can look at <a href="http://sigbjorn.vik.name/projects/Triangulation.pdf" rel="nofollow">http://sigbjorn.vik.name/projects/Triangulation.pdf</a> which was first google result for "self intersecting Polygon triangulation algorithm" first it will discuss about Seidel's algorithm and it's implementation and then it will generalize it in "5.2 Intersections" talks about self intersect polygons.</p>

CC BY-SA 3.0
2011-01-09T14:03:44.333Z
2012-02-11T08:10:49.607Z
2012-02-11T08:10:49.607Z
Saeed
<p>I had hard time finding algorithm or published papers on Self intersecting polygon(also polygon with hole structure) triangulation.</p>

<p>Can any one guide me to find published paper/algorithm, please?</p>

<p>PS: someone tag this question appropriately please, I do not have enough reputation points to do it.</p>

CC BY-SA 2.5
2011-01-07T01:00:32.037Z
Perhaps your emphasis is on the self-intersecting aspect of your polygons?  Most algorithms (such as that Suresh suggests) assume a simple polygon.  First you will have to compute the intersection points at the self-crossings, via, e.g., a plane sweep.  Then you can apply Seidel's algorithm.
Joseph O'Rourke
<ds.algorithms><reference-request><cg.comp-geom>
Algorithms for Polygon triangulation
Prashant Cholachagudda
# Algorithms for Polygon triangulation

(Asked by: username_0 on 2011-01-06)

I had hard time finding algorithm or published papers on Self intersecting polygon(also polygon with hole structure) triangulation.

Can any one guide me to find published paper/algorithm, please?

PS: someone tag this question appropriately please, I do not have enough reputation points to do it.

**Tags:** ds.algorithms, reference-request, cg.comp-geom

> **Comments:**
> **username_1**: Perhaps your emphasis is on the self-intersecting aspect of your polygons?  Most algorithms (such as that Suresh suggests) assume a simple polygon.  First you will have to compute the intersection points at the self-crossings, via, e.g., a plane sweep.  Then you can apply Seidel's algorithm.  

---

## 3 answers

### Answer by username_2 on 2011-01-09. Score: 4 | Accepted answer

Have you considered [Martin Held's "FIST" project](http://www.cosy.sbg.ac.at/~held/projects/triang/triang.html)? (See also [Martin's paper](http://www.springerlink.com/content/ermlr10j8pj48tl2/).)


---

### Answer by username_3 on 2011-01-06. Score: 7

Have you considered [Seidel's algorithm](http://www.cs.princeton.edu/courses/archive/fall05/cos528/handouts/A%20Simple%20and%20fast.pdf) ?

> **Comments:**
> **username_4**: Seidel's algorithm, though very fast,  needs modification to handle self-intersections. It's not impossible, but not immediately obvious.  

---

### Answer by username_5 on 2011-01-09. Score: 1

I think you can look at <http://sigbjorn.vik.name/projects/Triangulation.pdf> which was first google result for "self intersecting Polygon triangulation algorithm" first it will discuss about Seidel's algorithm and it's implementation and then it will generalize it in "5.2 Intersections" talks about self intersect polygons.


---

