Add support for CDTs with interior and exterior faces.

[kristoiv]

Hi!

I needed to do CDT where I define the outer contour as a constraint (as well as zero or more inner cutouts). Adding constraints along the outer vertices didn't help with this though, as the CDT implementation in spade will find convex-hull triangles outside my outer contour if they exist.

My solution thus far has been to check all triangle-centers using a vector_inside_polygon_test(..), and throwing away any triangle which is outside my outer contour.

Is there a better way of doing this using the library?

[Stoeoef]

My suggestion would be to make the CDT edges "direction aware": let edges store which side refers to the inside and which side refers to the outside:

type PolygonCdt<T> = ConstrainedDelaunayTriangulation<T, bool, (), (), LastUsedVertexHintGenerator>;

The bool refers to the directed edge type.

Now, adding a constraint would look like this:

let from = self.edges.insert(from)?;
let to = self.edges.insert(to)?;
self.edges.add_constraint(from, to);
let edge = self
    .edges
    .get_edge_from_neighbors(from, to)
    .expect("Multiple edges created by adding a constraint")
    .fix();
// Mark one edge as inner, the rev() is marked as outer already
*self.edges.directed_edge_data_mut(edge) = true;

Admittedly, the API around this is really ugly - spade currently doesn't have a good method to insert new vertices and create edges with pre-filled data. It uses Default instead. It's important to make sure that the winding order is consistent - all closed loops must be consistently inserted in clockwise or counter-clockwise order.

Now, assuming that your triangulation only contains vertices next to constraint edges, faces can be checked for their "insideness" by looking at their surrounding:

fn is_inside(triangulation: &impl Triangulation<DirectedEdge = bool>>, face: FixedFaceHandle<InnerTag>) -> bool {
    let face = triangulation.face(face);
    let mut current_edge = face.adjacent_edge();
    loop {
        if current_edge.data() != current_edge.rev().data() {
            return *current_edge.data(); // You may need to invert this depending on the windedness
    }
    current_edge = current_edge.cw();
};

While I've left out some details in the above code, I use this procedure with success in a private project - it works and should be much more efficient than a vector_inside_polygon_test.

I think designing an API around this might be a good addition to Spade. I'll refine this issue for this purpose.