I am working on the polygon triangulation algorithms from "Computational Geometry - Algorithms and applications 3rd ed", chapter 4.

I've managed to turn polygons into y-monotone polygons using the sweep line technique. For this, diagonals are added to the DCEL which ignoring any face values (which are then corrected later). This is to avoid the O(n) complexity that comes with splitting a face (i.e correctly adding a diagonal).

Now that I am proceeding to triangulating these monotone polygons I am running into issues trying to add the diagonals in O(1) time. There are cases where diagonals are being added in between two vertices but there is not enough information from just the incident edges on each vertex to make the proper connection. Now, it would be possible to walk up and down the vertices until the correct edges are identified, but that would ruin the running time of the algorithm.

The way I am adding diagonals currently is to just look at the incident edge of each vertex and assume that these will be the correct "next/previous" edges for my new half edges.

Any help would be greatly appreciated, thank you.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.