At the moment I'm implementing an algorithm to construct a Delaunay triangulation for a set of points. I'm using the algorithm described in Computational Geometry: Algorithms and Applications. The chapter on Delaunay triangulations is available from this link: http://www.cs.uu.nl/geobook/

See also this question: Position points and line

I'm probably misunderstanding something in the algorithm, since I came across this problem:

I have four points $p_0(4,4)$, $p_1(0,0)$, $p_2(1,0)$ and $p_3(0,1)$. So I start the algorithm with the triangle $p_{-1}p_{-2}p_0$ and first add the point $p_1$.

For this step all the edges that need to be verified are legal, so we end up with the following triangles after this step: $p_{-1}p_{-2}p_1$, $p_{-1}p_1p_0$ and $p_1p_{-2}p_0$.

The next step is to add the point $p_2$ which is contained in $p_{-1}p_1p_0$. Again all edges are legal and we get the triangles: $p_{-1}p_{-2}p_1$, $p_1p_{-2}p_0$, $p_{-1}p_1p_2$, $p_{-1}p_2p_0$ and $p_2p_1p_0$.

Finally we add the point $p_3$ which is contained in $p_1p_{-2}p_0$. In the new triangle $p_1p_{-2}p_3$ the edge $p_1p_{-2}$ is illegal, and we should flip it with $p_3p_{-1}$. This edge however intersects $p_1p_0$.

Is there something wrong in my interpretation of illegal? Could someone give the different steps for this specific case, so I can see where I'm going wrong?

edit: here is an image illustrating things after $p_3$ is added, but before any of the edges have been legalized for that step.

enter image description here


Why is $p_1p_{-2}$ in the picture illegal? Triangle $p_{-2}p_1p_3$ looks like a valid Delaunay triangle to me (circle through these points is empty). You should flip $p_0p_1$ to $p_2p_3$ though.

  • $\begingroup$ The edge $p_1p_{-2}$ is illegal, because in the cited source it says: if $\min(i,j,k,l)<0$ and $p_ip_j$ is not an edge of $p0p_{-1}p_{-2}$, then $p_ip_j$ is legal if and only if $\min(k, l) < \min(i, j)$. It is not the case that $-1 < -2$, so the edge $p_1p_{-2}$ is not legal. I can see that the other edge should be flipped, but I'm implementing the algorithm, so I need to find what is wrong in my interpretation. $\endgroup$ – bart_m8 Nov 26 '13 at 13:23
  • $\begingroup$ I've checked my old copy of the book (2nd edition) I wrote some notes that the result can be non-planar; this is fixed if you remove the 'extra' points. In your case you could flip $p_1p_{-2}$. If you remove $p_{-2}$ and $p_{-1}$ at the end you still have a valid Delaunay triangulation. $\endgroup$ – Simon Nov 26 '13 at 20:52
  • $\begingroup$ OK, thanks. I will have to look further then. The end result is incorrect, and this was just the first step that something strange happened. There will probably be another question. ;-) $\endgroup$ – bart_m8 Nov 27 '13 at 8:44
  • $\begingroup$ After insertion of $p_3$ you should also check $p_0p_1$ which is illegal. If you flip $p_0p_1$ also and you remove $p_{-1}$ and $p_{-2}$ at the end you've got the correct triangulation $\endgroup$ – Simon Nov 27 '13 at 9:55
  • $\begingroup$ I had a < sign that was the wrong way around. I have fixed this, and now the program works for this case, but if I slightly shift one of the vertices, it breaks, so I will have to check the code that verifies the legality of an edge. $\endgroup$ – bart_m8 Nov 27 '13 at 17:03

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.