1
$\begingroup$

I have an implementation of the Bowyer-Watson algorithm for Delaunay triangulation which works well -- given a set of 2D points, it computes a set of triangles to fill the areas between the points.

Recently I was requested to fulfill a new requirement -- the ability for the user to explicitly specify one or more triangles in advance, and have the result of the algorithm include those triangles (as well as "filling out" the rest of the graph around those triangles, as usual).

AFAICT the Bowyer-Watson algorithm doesn't lend itself to handling this well -- is there some trick by which I could make it work? Or if not, is there some other triangulation algorithm or approach that would be appropriate here?

Improve this question
$\endgroup$
1
$\begingroup$

Just insert sufficient number of points along the edges of the triangle you want - if you insert enough points, the edges of the triangle you want would be the union of edges of the triangulation. It is not pretty but it would work. This the basic idea behind many of the constrained triangulation meshing algorithms. Here is a nice paper on the topic, which contains more information:

https://people.eecs.berkeley.edu/~jrs/papers/2dj.pdf

Improve this answer
$\endgroup$
2
  • $\begingroup$ In my use-case, the points are all explicitly user-specified (they represent loudspeaker-positions within a room), so I'm not allowed to insert or remove any :( $\endgroup$
    – Jeremy Friesner
    Jun 11 '20 at 4:10
  • 1
    $\begingroup$ A. Don't show the fake points/edges. this is what all these mesh refinement algorithms do. B. There are power diagrams, which give you more control on what appears in the diagram (or its dual to be more precise)... $\endgroup$
    – Sariel Har-Peled
    Jun 11 '20 at 4:41

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.