Support overlapping boundaries

[ghorwin]

I don't know how to specify the correct input to CDT for below's examples:

The left problem is a box with a hole aligned to the left side of the box (no shared points).
The right problem is a box with a hole inside that occupies the left half of the box.

The expected result in the right case is just 2 triangles, but I get 4 (the hole is kept as well):

0, 1, 4
2, 3, 4
4, 3, 5
4, 5, 0

For the left part the hole is also not detected:

What am I doing wrong?

Below is my test code. Mind the rotated x,y coordinate system when looking at the test coordinates below!

Test code:

#include "CDT/CDT.h"
#include <iostream>

int main() {

	std::vector<CDT::V2d<double> > points;
	std::vector<CDT::Edge> edges;

	// a box with a hole aligned to the left side
#if 1
	points.push_back( CDT::V2d<double>::make(0,0));
	points.push_back( CDT::V2d<double>::make(2,0));
	points.push_back( CDT::V2d<double>::make(2,3));
	points.push_back( CDT::V2d<double>::make(0,3));
	points.push_back( CDT::V2d<double>::make(0.5,0));
	points.push_back( CDT::V2d<double>::make(1.5,0));
	points.push_back( CDT::V2d<double>::make(1.5,1));
	points.push_back( CDT::V2d<double>::make(0.5,1));

	edges.push_back(CDT::Edge(0, 1));
	edges.push_back(CDT::Edge(1, 2));
	edges.push_back(CDT::Edge(2, 3));
	edges.push_back(CDT::Edge(3, 0));
	edges.push_back(CDT::Edge(4, 5));
	edges.push_back(CDT::Edge(5, 6));
	edges.push_back(CDT::Edge(6, 7));
	edges.push_back(CDT::Edge(7, 4));
#endif

	// a box with a hole that covers the left part of the box
#if 0
	points.push_back( CDT::V2d<double>::make(0,0));
	points.push_back( CDT::V2d<double>::make(2,0));
	points.push_back( CDT::V2d<double>::make(2,3));
	points.push_back( CDT::V2d<double>::make(0,3));
	points.push_back( CDT::V2d<double>::make(2,1));
	points.push_back( CDT::V2d<double>::make(0,1));

	edges.push_back(CDT::Edge(0, 1));
	edges.push_back(CDT::Edge(1, 2));
	edges.push_back(CDT::Edge(2, 3));
	edges.push_back(CDT::Edge(3, 0));
	edges.push_back(CDT::Edge(0, 1));
	edges.push_back(CDT::Edge(1, 4));
	edges.push_back(CDT::Edge(4, 5));
	edges.push_back(CDT::Edge(5, 0));
#endif

	CDT::Triangulation<double> cdt(CDT::FindingClosestPoint::ClosestRandom); // Note: we don't want to use boost

	cdt.insertVertices(points);
	cdt.insertEdges(edges);
	cdt.eraseOuterTrianglesAndHoles();

	for (auto tri : cdt.triangles)
		std::cout << tri.vertices[0] << ", " << tri.vertices[1] << ", " << tri.vertices[2] << std::endl;
}

[ghorwin]

It seems, I have the problem of "intersecting outer boundaries". In the first example, when I split the overlapping edge (0,1) into:

(0,4) (4,5) (5,1)

triangulation works fine.

Question: would it make sense to write a function in the CDT::Triangulation class that does this "segment" splitting automatically? The algorithm would have at least O(n2) complexity (since each edge has to be checked against each other edge, hereby storing intersection point + intersecting edge numbers, and afterwards applying the split opertion to all recorded intersecting lines.

Should I try to come up with an algorithm myself, or does anyone have this ready-made?

[artem-ogre]

Thank you for a good detailed issue, @ghorwin

Configurations with boundary edges shared by hole and non-hole polygons are not supported by the hole-detection algorithm.
This corner-case definitely needs to be mentioned in in readme/comments.

I will later take a closer look at the hole-detection algorithm implementation and maybe propose ways to fix this in a more detailed reply.
If there is a good fix it makes sense to include it into CDT. Otherwise you could pre-process your input to detect edges constrained twice (or any even number of times) and don't add them as constraints. But detecting overlapping edges and splitting them into segments may be challenging to implement properly.

[ghorwin]

Since I have the bounding polygon available, I just need to process each line of said polygon, check against intersections with all other constraint edges and insert vertexes as needed. That seems to be a workable problem (I hope).

[artem-ogre]

After thinking more about handling overlapping boundaries I think it would be nice to have it in CDT so that removing holes always 'just works'. I started to prototype this functionality and hope to have a branch with the change this week (or next).

[ghorwin]

That would be awesome. I'm ready for testing :-)

[artem-ogre]

I've done some proof-of-concept in the branch feature/42-handle-overlapping-boundaries. It is rather quick and dirty but I tested it on a couple of test files containing overlapping boundaries (added to the commit). If you are eager to start testing, welcome :)

I will add a detailed explanation of how overlapping boundaries are handled and what to expect from it when there is time. So maybe it worth to wait for it.

[artem-ogre]

Hole-removal algorithm

Each triangle is assigned 'layer depth' using iterative depth-peeling algorithm.
Layer boundaries are defined by fixed edges (triangulation constraints).
Outermost triangles adjacent to super-triangle vertices have depth 0. Next layer has depth 1 and so on.
To remove holes and outer triangles: triangles with even layer depths (0, 2 , etc.) are removed.

Basic idea is that every time a fixed edge is crossed depth is incremented by 1.

This approach does not work when boundaries overlap. As sometimes a fixed edge can separate non-subsequent layers (e.g., 1 and 3). Wrong triangle depths will be calculated.

Idea behind the fix

Record how many times each edge was constrained.
When crossing a fixed edge instead of incrementing depth by 1 increment it by the number of times the edge was constrained.

Notes

• This supports even cases when boundaries overlap entirely (see test file issue-42-full-boundary-overlap.txt);
• Now care are needs to be taken not to insert the edge twice by accident. Before it was just a no-op, but after this fix this can impact hole-removal;
• Opens a way for an interesting hack: having constraint polygons in triangulation that are not boundaries or holes. By just constraining the edge twice it will be present in triangulation but will not affect hole-removal.

[artem-ogre]

@ghorwin
I've cleaned up the code and opened a PR. Any news on testing, does this work with your use cases now?

[ghorwin]

Super, works fine for my test cases. I'll put it into my app and will check, how well this works with potential rounding errors (i.e. when example geometry above is rotated with floating-point accuracy).

Thanks!

[artem-ogre]

@ghorwin
Inputs are handled exactly. E.g., if the point is exactly on the edge: the edge will be split automatically. If the point is even slightly off then no tolerances are used and the point is treated as not lying on the edge.
In such cases it is needed to pre-process the input data if necessary.

[ghorwin]

Thought, so. I'm currently working on such a pre-processing, but it turns out that a fuzzy intersection routine isn't easy that easy to write (efficiently). Once I have it ready, I'll post it here for reference.

[artem-ogre]

Fix is merged to master. #43