earcutting vs delaunay?

[mpadge]

@mdsumner a stupid Q from me here, coz i really know SFA about triangulation, but why do the following give such different results?

xy <- silicate::sc_coord (minimal_mesh) %>%
    dplyr::distinct (x_, y_) %>%
    dplyr::rename (x = x_, y = y_) # convert to pure table, so no holes, no nothing
nbs <- tripack::tri.mesh (xy) %>%
    tripack::neighbours ()
tri <- decido::earcut (xy) %>%
    matrix (nrow = 3) %>%
    t () %>%
    as.tibble ()

par (mfrow = c(1, 2))
plot (xy, pch = 1, main = "delaunay")
text (xy, labels = seq (nrow (xy)), pos = 3, adj = 0.5)
xyn <- as.matrix (xy)
for (i in seq (nbs))
    for (j in nbs [[i]])
        segments (xyn [i, 1], xyn [i, 2], xyn [j, 1], xyn [j, 2])

plot (xy, pch = 1, main = "earclipping")
text (xy, labels = seq (nrow (xy)), pos = 3, adj = 0.5)
for (i in seq (nrow (tri)))
{
    ti <- as.integer (tri [i, ])
    segments (xyn [ti [1], 1], xyn [ti [1], 2],
              xyn [ti [2], 1], xyn [ti [2], 2])
    segments (xyn [ti [1], 1], xyn [ti [1], 2],
              xyn [ti [3], 1], xyn [ti [3], 2])
    segments (xyn [ti [2], 1], xyn [ti [2], 2],
              xyn [ti [3], 1], xyn [ti [3], 2])
}

earcut really does cut 1-13-14, and 1-12-13, but how can that make sense?

[mdsumner]

The Delaunay is pure Delaunay on points (no input edges) and so it's the convex hull, no concavity (no reflection of the fact that 5-4 is part of the shape.)

The earclipping is flawed, because you have three rings and they are dutifully followed but only by tracing around each vertex in turn. There's two problems, you can't have two islands, and you haven't specified the hole. (earcut.hpp is written to be very robust to crazy inputs

I can see why it's so confusing, I've only had a head-start :) I think this is explained ok in the decido docs, but it does need a deeper comparison to the edge-constrained Delaunay method. It's not discussed in depth really anywhere afaik except the mesh texts. You just can't preserve the original shape in a whole-vertex-pool triangulation like tripack without a fully specified set of indexed edge inputs (only RTriangle can do it).

It just can't work that way, you have to do it per POLYGON (earcut can't handle multiple islands in one call):

xy <- sc_coord(minimal_mesh)  ## no deduping
tri1 <- decido::earcut (xy[1:14, ], holes = 9)
decido::plot_ears(xy[1:14, ], tri1)
tri2 <- decido::earcut (xy[15:19, ], holes = 0)  ## no holes in island #2
decido::plot_ears(xy[15:19, ], tri2)

[mdsumner]

This does say it concisely: https://en.wikipedia.org/wiki/Constrained_Delaunay_triangulation

This is out of date (no holes!?) and doesn't say enough https://en.wikipedia.org/wiki/Polygon_triangulation#Ear_clipping_method

CDt is edge-based, ear-clipping is path based

[mpadge]

ah, that makes a lot more sense - thanks for the clarification. Now i get the diff between edge- and path-based, and see the huge relevance of decido. Not for my present needs, alas, but for silicate in general.