Either the algorithm does not generate valid triangles, or I am missing something

[notgull]

I'd like to use this algorithm in my breadx project, as a way of breaking shapes into triangles before sending them to the X11 server. As a test, I ran the algorithm on this shape:

    // create an arbitrary polygon and convert it to triangles
    let t: Vec<_> = tesselate_shape(&vec![
        Pointfix {
            x: double_to_fixed(100.0),
            y: double_to_fixed(100.0),
        },
        Pointfix {
            x: double_to_fixed(100.0),
            y: double_to_fixed(150.0),
        },
        Pointfix {
            x: double_to_fixed(150.0),
            y: double_to_fixed(250.0),
        },
        Pointfix {
            x: double_to_fixed(200.0),
            y: double_to_fixed(250.0),
        },
        Pointfix {
            x: double_to_fixed(200.0),
            y: double_to_fixed(150.0),
        },
        Pointfix {
            x: double_to_fixed(250.0),
            y: double_to_fixed(100.0),
        },
        Pointfix {
            x: double_to_fixed(300.0),
            y: double_to_fixed(150.0),
        },
        Pointfix {
            x: double_to_fixed(300.0),
            y: double_to_fixed(300.0),
        },
        Pointfix {
            x: double_to_fixed(150.0),
            y: double_to_fixed(450.0),
        },
        Pointfix {
            x: double_to_fixed(50.0),
            y: double_to_fixed(250.0),
        },
        Pointfix {
            x: double_to_fixed(50.0),
            y: double_to_fixed(150.0),
        },
    ])
    .collect();

I implemented tesselate_shape using the following:

/// From the given set of points, return an iterator over the triangles.
#[inline]
pub fn tesselate_shape<'a>(points: &'a [Pointfix]) -> impl Iterator<Item = Triangle> + 'a {
    let floating_points: Vec<Point> = points
        .iter()
        .copied()
        .map(|Pointfix { x, y }| Point {
            x: fixed_to_double(x),
            y: fixed_to_double(y),
        })
        .collect();

    let vector = match triangulate(&floating_points) {
        Some(t) => t.triangles ,
        None => vec![],
    };

    vector
        .into_iter()
        .map(move |index| &points[index])
        .copied()
        .scan(ArrayVec::<[Pointfix; 3]>::new(), |av, point| {
            av.push(point);
            if av.len() == 3 {
                let [p1, p2, p3] = mem::take(av).into_inner();
                Some(Some(Triangle { p1, p2, p3 }))
            } else {
                Some(None)
            }
        })
        .flatten()
}

Note: XRender does things in fixed-point 32-bit numbers by default, so I have to convert them to and from floating point notation.

When I run this, it produces radically different results than expected. Here's what I should see; this is what I get when I manually triangulated the shape:

However, this happens when I use delaunator:

I feel like this is probably a result of me misunderstanding how the crate is supposed to work; is there something I'm missing?

[mourner]

What you're looking for is polygon triangulation library. This one is specifically for Delaunay triangulation of point sets. See https://en.wikipedia.org/wiki/Delaunay_triangulation

See also: mapbox/delaunator#9