CODEWITHSUNDEEP
triangulationdelaunay
javaEntu
javaEntu

Reputation: 160

Extra edges in Delaunay Triangles

Please see the attached pictures below. There are few extra edges, and they seem to satisfy "point not inside the circumcircle" property at the time of adding each point. I have already removed the Super Triangle from both the screenshots.

Do I need to rerun the loop to eliminate Bad Triangles? But that's not what the Bowyer-Watson algorithm says. Could someone please help to understand what could be wrong here?

Edit: These are the vertices in the processing order for the 1st screenshot.
(1500, 1500)
(3300, 1500)
(2800, 2800)
(1750, 2600)
(2350, 2900)

Update 1:
While repopulating the polygon, I am connecting new point with all the edges. That's why the additional edge is coming up, but I have no idea yet, how to select and ignore individual point of edge.

(Sorry, I can't post my code here. Any suggestions would be really helpful.)

Annotated Coordinates

Erroneous Delaunay Triangulation

Another example

Upvotes: 0

Views: 846

Answers (2)

Gary Lucas
Gary Lucas

Reputation: 478

Using the coordinates you supplied, I get the Delaunay triangulation shown below. Based on my experience with the Bowyer-Watson algorithm, I'd guess that your problem is that you are not removing edges during the "cavity digging" phase of the process (and by "experience" I mean "the mistakes that I've made in the past"). Though, of course, there are plenty of other things that can go wrong.

Delaunay Triangulation

I've made some notes about my own efforts to implement Bowyer-Watson starting at about page 20 in the document Tinfour Algorithms and Data Elements. Perhaps they will give you some ideas you can use.

Good luck on your project. I wish you the best of success.

Gary

Upvotes: 2

peabrainiac
peabrainiac

Reputation: 1078

The wikipedia article about the Bowyer-Watson-Algorithm states:

The Bowyer–Watson algorithm is an incremental algorithm. It works by adding points, one at a time, to a valid Delaunay triangulation of a subset of the desired points. After every insertion, any triangles whose circumcircles contain the new point are deleted, leaving a star-shaped polygonal hole which is then re-triangulated using the new point.

In other words, after adding a new point and removing all problematic sides, you need to connect it only to the corners of hole that those removed triangles form, not every point in the graph. That way edges will never intersect, unlike in your three examples.

The article also has a pretty good pseudo-code implementation of the algorithm, maybe taking a closer look at that will also help you further.

Upvotes: 1

Related Questions