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.

$\endgroup$
  • 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.)

$\endgroup$
7
$\begingroup$

Have you considered Seidel's algorithm ?

$\endgroup$
  • $\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.

$\endgroup$

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.