3
$\begingroup$

I am trying to find a resource which explains how to compute the constrained Delaunay triangulation of a set of points and edge constraints, I found these slides by Jonathan Shewchuck, but without the presenter it's hard to follow.

Ideally I am looking for a strategy that only involves edge flipping, without the need for deletion and reinsertion.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

You can find Johnathan Shewchuck's UC Berkely website here, which contains:

  • Excellent lecture notes on Delaunay Mesh Generation
  • sample chapters from the book "Delaunay Mesh Generation" (which might well be worth buying)
  • Many other excellent papers and references

Ages ago, I have used his lecture notes to implement Constrained Delaunay Triangulations in Scala. If You're interested, you can find the source code on GitHub.

I am not sure what you mean by flipping instead of deletion. Technically, edge flipping is the removal of two triangles followed by an insertion of two other triangles.

Improve this answer
$\endgroup$
1
$\begingroup$

Page 7 of "FAST ALGORITHM FOR GENERATING CONSTRAINED DELAUNAY TRIANGULATIONS" (a publication on a CDT algorithm) explains the process very clearly and the figures are extremely useful.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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