mourner / delaunator-rs

Fast 2D Delaunay triangulation in Rust. A port of Delaunator.
https://docs.rs/delaunator
ISC License
207 stars 28 forks source link

Triangulation.hull clock-wise instead of counter-clockwise? #12

Closed andreesteve closed 3 years ago

andreesteve commented 3 years ago

Thanks for the port!

The docs indicate that the indices returned by Triangulation.hull are counter-clockwise.

hull: Vec<usize>
[−]
A vector of indices that reference points on the convex hull of the triangulation, counter-clockwise.

However I see them being returned clockwise. Which one is the right expectation?

Sample test:

use delaunator::*;

fn main() {
    let p = vec![
        Point { x: 0.0, y: 0.0 },
        Point { x: 1.0, y: 1.0 },
        Point { x: -1.0, y: 1.0 },
    ];
    triangulate(&p)
        .unwrap().hull.iter()
        .for_each(|s| println!("Hull {}: {:?}", *s, p[*s]));
}

for which I get:

Hull 0: [0, 0]
Hull 2: [-1, 1]
Hull 1: [1, 1]
mourner commented 3 years ago

It should be counter-clockwise (as a convention and to match delaunator in JS), so it might be a bug.

andreesteve commented 3 years ago

This was my mistake. I assumed the Y axis upright, in such orientation the triangle is oriented clockwise. image

However, the library expects Y to be pointing downwards, in which case the orientation is correct.

image