9
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • 5
    $\begingroup$ 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. $\endgroup$ – Joseph O'Rourke Jan 7 '11 at 1:00
4
$\begingroup$

Have you considered Martin Held's "FIST" project? (See also Martin's paper.)

Improve this answer
$\endgroup$
7
$\begingroup$

Have you considered Seidel's algorithm ?

Improve this answer
$\endgroup$
1
  • $\begingroup$ Seidel's algorithm, though very fast, needs modification to handle self-intersections. It's not impossible, but not immediately obvious. $\endgroup$ – Simon F Apr 12 '17 at 13:30
1
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.