Talk:Bowyer–Watson algorithm
 | This article is rated Start-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
Incorrect Result?
[edit]The Voronoi tessellation of the vertices in the example is not dual to the result shown. Correspondingly, the result shown is not a correct Delaunay triangulation: The circumcircle of the middle triangle (of the final three) contains the rightmost vertex. The correct triangulation would not connect the topmost with the bottom right vertex, but the bottom left with the rightmost. That would also be dual to the correct Voronoi tessellation. I think the problem lies with the incremental process. The Delaunay triangulation in the step before inserting the rightmost vertex is correct. Then, inserting that vertex, the correct triangle is split up, but in combination with its neighbouring triangles, we generate this wrong triangulation. Perhaps there is a check needed after the insert, and in case of violation, a flip of the edge within a combination of four vertices? As far as I can tell from a glance at the papers, this is also not addressed in there? — Preceding unsigned comment added by 132.180.194.68 (talk) 15:01, 5 February 2020 (UTC)
Extra Requirements for Super Triangle
[edit]While coding up an implementation of this algorithm, I (well, a coworker and I) discovered that the super triangle described here is insufficient in some cases. It is not enough for the super triangle to contain all points. An example is discussed in this StackExchange post: https://math.stackexchange.com/questions/4001660/bowyer-watson-algorithm-for-delaunay-triangulation-fails-when-three-vertices-ap.
I am not yet sure what the necessary condition is for the super triangle. Containing all circumcircles should do the trick, but calculating these is annoying. I'd like to dig through the original literature and see what the authors say about this.