<p>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:</p>

<p><a href="https://people.eecs.berkeley.edu/~jrs/papers/2dj.pdf" rel="nofollow noreferrer">https://people.eecs.berkeley.edu/~jrs/papers/2dj.pdf</a></p>

CC BY-SA 4.0
2020-06-11T04:10:40.183Z
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 :(
Jeremy Friesner
CC BY-SA 4.0
2020-06-11T04:41:11.933Z
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)...
Sariel Har-Peled
CC BY-SA 4.0
2020-06-11T04:08:56.823Z
2020-06-11T04:08:56.823Z
Sariel Har-Peled
<p>I have an implementation of the <a href="https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm" rel="nofollow noreferrer">Bowyer-Watson</a> 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.</p>

<p>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).</p>

<p>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? </p>

<delaunay-triangulation>
Delaunay triangulation when some triangles have been pre-specified?
Jeremy Friesner
# Delaunay triangulation when some triangles have been pre-specified?

(Asked by: username_0 on 2020-06-05)

I have an implementation of the [Bowyer-Watson](https://en.wikipedia.org/wiki/Bowyer%E2%80%93Watson_algorithm) 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?

**Tags:** delaunay-triangulation

---

## 1 answers

### Answer by username_1 on 2020-06-11. Score: 1

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>

> **Comments:**
> **username_0**: 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 :(  
> **username_1**: 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)...  

---

