Is there a library that can split a concave polygon into convex ones

help
1

Hi, I am trying to triangulate the polygon. I found the two triangulation libraries: delaunator and spade. However, I realized that these two libraries can only support solving convex polygons after trying them.So I want to split the concave polygon into into convex ones and then triangulate them. But I am not familiar with this field. Are there any recommended libraries?

1 Like
2

I recently did a search for such libraries myself. I have not actually made use any of them yet for the purpose I had in mind, so I can’t say which ones are actually good, but I did glance through their docs and code; here's a copy of my notes from the search, which I was going to use as a list of ones to try out.

All of these should support non-convex polygons and holes.

If you try any of them, let me know how it goes!

3 Likes
3

Thanks! Just tried earcutr and earcut, but the API design of both libraries is kinda unreasonable to me.

For example, there is an argument dimensions which must be 2, but we still need to input this value manually every time we call this function in crates/earcutr. And in crates/earcut, we need to pass the triangles as a mutable variable to the earcut function, instead of getting the calculated triangles as a return value from the earcut function, which is not quite intuitive.

But anyway, crates/earcut seems enough for my needs.

4

That’s probably a part of the "designed with attention to perf" part. Returning a new vector of triangles would be super inefficient compared to reusing a buffer when you’re calling the function a lot; writing the result to an out parameter instead is pretty standard practice in high-performance APIs.

1 Like
5

I don't think Spade requires a convex polygon as its input. What happens if you try to create a triangulation using Triangulation in spade - Rust?

We use both earcutr and spade in crates.io: Rust Package Registry

6

For example, in the code below, I constructed a polygon like 凹, but the triangles from the result would be like 口. (Or maybe is it that I am using it incorrectly?)

fn main() {
    let mut triangulation: DelaunayTriangulation<Point2<f64>> = DelaunayTriangulation::new();

    triangulation.insert(Point2::new(0.0, 0.0)).unwrap();
    triangulation.insert(Point2::new(0.0, 3.0)).unwrap();
    triangulation.insert(Point2::new(1.0, 3.0)).unwrap();
    triangulation.insert(Point2::new(1.0, 2.0)).unwrap();
    triangulation.insert(Point2::new(2.0, 2.0)).unwrap();
    triangulation.insert(Point2::new(2.0, 3.0)).unwrap();
    triangulation.insert(Point2::new(3.0, 3.0)).unwrap();
    triangulation.insert(Point2::new(3.0, 0.0)).unwrap();

    for face in triangulation.inner_faces() {
        let edges = face.adjacent_edges();
        for edge in edges {
            let from = edge.from();
            let to = edge.to();
            println!("found an edge: {:?} -> {:?}", from, to);
        }
        println!("------")
    }
}

Output:

found an edge: VertexHandle(2) -> VertexHandle(1)
found an edge: VertexHandle(1) -> VertexHandle(3)
found an edge: VertexHandle(3) -> VertexHandle(2)
------
found an edge: VertexHandle(0) -> VertexHandle(3)
found an edge: VertexHandle(3) -> VertexHandle(1)
found an edge: VertexHandle(1) -> VertexHandle(0)
------
found an edge: VertexHandle(4) -> VertexHandle(2)
found an edge: VertexHandle(2) -> VertexHandle(3)
found an edge: VertexHandle(3) -> VertexHandle(4)
------
found an edge: VertexHandle(3) -> VertexHandle(0)
found an edge: VertexHandle(0) -> VertexHandle(4)
found an edge: VertexHandle(4) -> VertexHandle(3)
------
found an edge: VertexHandle(5) -> VertexHandle(2)
found an edge: VertexHandle(2) -> VertexHandle(4)
found an edge: VertexHandle(4) -> VertexHandle(5)
------
found an edge: VertexHandle(6) -> VertexHandle(5)
found an edge: VertexHandle(5) -> VertexHandle(4)
found an edge: VertexHandle(4) -> VertexHandle(6)
------
found an edge: VertexHandle(7) -> VertexHandle(4)
found an edge: VertexHandle(4) -> VertexHandle(0)
found an edge: VertexHandle(0) -> VertexHandle(7)
------
found an edge: VertexHandle(4) -> VertexHandle(7)
found an edge: VertexHandle(7) -> VertexHandle(6)
found an edge: VertexHandle(6) -> VertexHandle(4)
------
7

FWIW I tried a bunch when trying to triangulate some really crappy edge list input with missing edges, overlaps, T-junctions and holes. Didn't have much luck, but that isn't too surprising.

8

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.