stoeoef/spade

Delaunay Triangulations for the Rust Ecosystem

spade

Delaunay triangulations for the rust ecosystem.

• 2D Delaunay triangulation, optionally backed by a hierarchy structure for improved nearest neighbor and insertion performance.
• Allows both incremental and bulk loading creation of triangulations
• Support for vertex removal
• 2D constrained Delaunay triangulation (CDT)
• Delaunay refinement
• Uses precise geometric predicates to prevent incorrect geometries due to rounding issues
• Supports extracting the Voronoi diagram
• Natural neighbor interpolation

---

---

Project goals

Project goals, in the order of their importance:

1. Robustness - all data structures should behave correctly. An incorrect result, even if triggered only under rare circumstances, is not acceptable. This is why Spade uses a precise calculation kernel by default.
2. Easy to use - favor an easy to use API over an API that exposes all bells and whistles.
3. Performance - Delaunay triangulations are often a low level component of an application. Optimization in this area pays off greatly.
4. Small footprint - Spade should be a sensible library to include in your project that doesn't require too many dependencies. Bigger dependencies will be feature gated when possible.

Roadmap

For Spade 3:

• Possibly API simplification by un-supporting non-f64 outputs.

Performance and comparison to other crates

Refer to the delaunay_compare readme for some benchmarks and a comparison with other crates.

License

Licensed under either of

• Apache License, Version 2.0, (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
• MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)

at your option.

spade's Issues

IntDelaunayTriangulation overflow

#[test]
fn overflows() {
    use spade::delaunay::*;
    let mut tris = IntDelaunayTriangulation::with_walk_locate();
    for &p in &[
        [-100, -100],
        [0, 0],
        [-200, -100],
        [200, -100],
    ] {
        tris.insert(p);
    }
}

thread 'main' panicked at 'attempt to multiply with overflow', /rustc/73528e339aae0f17a15ffa49a8ac608f50c6cf14/src/libcore/ops/arith.rs:318:45
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/libunwind.rs:88
   1: backtrace::backtrace::trace_unsynchronized
             at /cargo/registry/src/github.com-1ecc6299db9ec823/backtrace-0.3.40/src/backtrace/mod.rs:66
   2: std::sys_common::backtrace::_print_fmt
             at src/libstd/sys_common/backtrace.rs:77
   3: <std::sys_common::backtrace::_print::DisplayBacktrace as core::fmt::Display>::fmt
             at src/libstd/sys_common/backtrace.rs:61
   4: core::fmt::write
             at src/libcore/fmt/mod.rs:1028
   5: std::io::Write::write_fmt
             at src/libstd/io/mod.rs:1412
   6: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:65
   7: std::sys_common::backtrace::print
             at src/libstd/sys_common/backtrace.rs:50
   8: std::panicking::default_hook::{{closure}}
             at src/libstd/panicking.rs:188
   9: std::panicking::default_hook
             at src/libstd/panicking.rs:205
  10: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:464
  11: std::panicking::continue_panic_fmt
             at src/libstd/panicking.rs:373
  12: rust_begin_unwind
             at src/libstd/panicking.rs:302
  13: core::panicking::panic_fmt
             at src/libcore/panicking.rs:139
  14: core::panicking::panic
             at src/libcore/panicking.rs:70
  15: <i32 as core::ops::arith::Mul>::mul
             at /rustc/73528e339aae0f17a15ffa49a8ac608f50c6cf14/src/libcore/ops/arith.rs:318
  16: spade::kernels::DelaunayKernel::contained_in_circumference
             at /home/poseidon/.cargo/registry/src/github.com-1ecc6299db9ec823/spade-1.8.1/src/kernels.rs:60
  17: spade::delaunay::delaunay_basic::BasicDelaunaySubdivision::legalize_edges
             at /home/poseidon/.cargo/registry/src/github.com-1ecc6299db9ec823/spade-1.8.1/src/delaunay/delaunay_basic.rs:573
  18: spade::delaunay::delaunay_basic::BasicDelaunaySubdivision::insert_outside_convex_hull
             at /home/poseidon/.cargo/registry/src/github.com-1ecc6299db9ec823/spade-1.8.1/src/delaunay/delaunay_basic.rs:427
  19: spade::delaunay::delaunay_basic::BasicDelaunaySubdivision::insert_with_hint_option
             at /home/poseidon/.cargo/registry/src/github.com-1ecc6299db9ec823/spade-1.8.1/src/delaunay/delaunay_basic.rs:272
  20: spade::delaunay::delaunay2d::DelaunayTriangulation<V,K,L>::insert
             at /home/poseidon/.cargo/registry/src/github.com-1ecc6299db9ec823/spade-1.8.1/src/delaunay/delaunay2d.rs:449
  21: playground::main
             at src/main.rs:88

Check if handle functions are defined in the public interface

Functions like face(FixedFaceHandle), edge(FixedEdgeHandle) ...

Wrong links

Hi,

In the user manual, chapter Introduction, section Further Resources, the link for the doc points to "https://stoeoef.gitbooks.io/spade-user-manual/content/docs.rs/spade/"
I think this should be https://docs.rs/spade/

On the crates.io page, the link "Using Spade" points to https://crates.io/crates/spade#using-spade, that section doesn't appear to exits.

Vertex handle usage after vertex removal

Hello,

first of all thank you for sharing this library!

For my usecase I need to remove vertices often. But I also need to store some vertex handles for later. Like written in your documentation the removal function will invalidate all Handles.
Do you have a workaround for this like should i store points instead of the vertex handles.

If I were to try try alter the implementation, so that removal doesn't invalidate all handles, where should I start to look at. Do you have any hints for me?

Thanks

Quality of your RTree and CDT compared to Boost and CGAL implementations?

Can you tell us something about the quality of your CDT algorithm (speed and robustness) compared to CGAL lib, and maybe which papers you use to implement it?

Origin for my question is, that I would need a CDT for Nim language, and I would prefer a native implementation to restricted CGAL bindings (I made some CGAL bindings for Ruby some years ago.) Of course coding a robust and fast incremental constrained delaunay triangulation from scratch using research papers is a big task, so I am considering converting an existing implementation. Maybe from C++ or Rust. I have not yet found a nice standalone C++ implementation -- of course CGAL has one, but I guess extracting CDT code from lib is not easy. Your code is MIT licensed, same as Nim libs generally are, so it may a good candidate. I would have to learn some Rust before, but that is already on my todo list. (Funny fact is, that some weeks before I saw your spade package, I did a Nim RTree implementation myself from scratch following the original papers, see https://github.com/StefanSalewski/RTree.)

What about non-Cartesian coordinates?

I want to perform interpolation on a sphere, with (theta, phi) coordinates.

I find that if I implement PointN for a SphPoint{theta:f64, phi:f64} then the SpatialObject is automatically implemented, then the distance2 is determined. However the distance of two points on a sphere is not calculated as theta^2+phi^2, but need to first convert into (x,y,z), then calculate the inner products.

How can I properly represent a point on a sphere?

Steiner points

Is the implementation of „steiner points“ / insertion of additional points to reduce the triangle size to a certain maximum area planned for this library?

Change licensing

to both MIT / Apache

split SpatialObject into two traits?

I implemented SpatialObject (see code bellow), because of I used
only lookup_in_rectangle:

#[derive(Debug, Clone)]
struct PolyObject {
    points: Vec<[f32; 2]>,
    idx: i64,
}

impl SpatialObject for PolyObject {
    type Point = [f32; 2];
    fn mbr(&self) -> BoundingRect<Self::Point> {
        let mut ret = BoundingRect::from_point(self.points[0].clone());
        for p in self.points.iter().skip(1) {
            ret.add_point(p.clone());
        }
        ret
    }
    fn distance2(&self, _point: &Self::Point) -> <Self::Point as PointN>::Scalar {
        unreachable!();
    }
}

May be split SpatialObject to two traits with mbr and distance2 and require
one or another trait in special functions:

    fn lookup_in_rectangle(&self) -> Vec<T>
    where
        T: Foo,
    {
        unimplemented!();
    }
    fn nearest_neighbors(&self) -> Vec<T>
    where
        T: Boo,
    {
        unimplemented!();
    }

?

Improve nearest_neighbor query performance

nearest_neighbor is poorly optimized at the moment, optimize it. Making it non-recursive would be a first step.

`RTree` should implement `Debug`

Rename VectorN to PointN

Spade's vectors are (in most cases) points, to be in accordance with other libraries and "good practices" they should be renamed.

intersects_constraint return type

A lot of the time, when you call intersects_constraint, you're interested in which constraint you're intersecting, e.g. so you can get rid of it, or alter it, etc.

Do you think it would make sense for intersects_constraint to return Option<DirectedEdgeHandle> or something?

Can write a patch if you are interested.

incircle predicate produces results that differ from original C code

While verifying the exact predicates implementation in Rust, I found that your
incircle code produces results that differ from the original predicates code in
C.

The problem lies in the following lines in exactpred.rs (lines 337-343):

        let mut aytcc = [0f64; 8];
        let aytcclen = scale_expansion_zeroelim(&cc, adytail, &mut aytcc);
        let temp16blen = scale_expansion_zeroelim(&aytcc[..aytcclen], cdx, &mut temp16b);

        let mut aytbb = [0f64; 8];
        let aytbblen = scale_expansion_zeroelim(&bb, adytail, &mut aytbb);
        let temp16clen = scale_expansion_zeroelim(&aytbb[..aytbblen], -bdx, &mut temp16c);

These lines should be changed as follows (variables named 'cc' have been swapped with 'bb' and vice versa):

        let mut aytbb = [0f64; 8];
        let aytbblen = scale_expansion_zeroelim(&bb, adytail, &mut aytbb);
        let temp16blen = scale_expansion_zeroelim(&aytbb[..aytbblen], cdx, &mut temp16b);

        let mut aytcc = [0f64; 8];
        let aytcclen = scale_expansion_zeroelim(&cc, adytail, &mut aytcc);
        let temp16clen = scale_expansion_zeroelim(&aytcc[..aytcclen], -bdx, &mut temp16c);

Note, the following are the original lines in predicates.c (lines 2839-2843):

    aytbblen = scale_expansion_zeroelim(4, bb, adytail, aytbb);
    temp16blen = scale_expansion_zeroelim(aytbblen, aytbb, cdx, temp16b);

    aytcclen = scale_expansion_zeroelim(4, cc, adytail, aytcc);
    temp16clen = scale_expansion_zeroelim(aytcclen, aytcc, -bdx, temp16c);

After this change, the Rust incircle code produces identical results to the
original C code.

BoundingRect does not implement SpatialObject

When i'm trying to create a vector of BoundingRect and insert each of them to RTree i have to do like this:

pub type DPoint2 = cgmath::Point2<f64>;

#[derive(Debug)]
struct Rectangle {
    rect: BoundingRect<DPoint2>,
    id: i32,
}

impl SpatialObject for Rectangle {
    type Point = DPoint2;

    fn mbr(&self) -> BoundingRect<DPoint2> {
        self.rect.clone()
    }

    fn distance2(&self, _point: &Self::Point) -> DScalar {
        0.0
    }
}

BoundingRect from points

I think it will be good to have a method for creating BoundingRect from n-points. For now i'm doing this with geo crate BoundingBox and convert its to spade BoundingRect for future use in RTree.

R* Tree insertion performance

I'm wondering whether you've benchmarked insertion performance when populating the R* Tree; We're currently using Spade in a couple of places in rust-geo (it's working perfectly, thank you!), and our primary applications involve one-time bulk-inserting line segments into the tree. It's hard to know without comparing to other libraries, but performance seems slower than expected; I see times around 90 ms for inserting segments built from ~9k points. If you have any ideas for improving this, or ideas for improving insertion performance in the library, I'd be interested in helping out with development.

Support for constrained Delaunay triangulation with holes

Hello and thank you for all the hard work on Spade. It is a very useful library and I've had great success using it.

Context

I am using Spade to generate navigation meshes in a 2D video game. The inputs I give to Spade are the four corners of the playable space, and constraint edges representing all the polygonal obstacles within it. The resulting triangulation is a usable navigation mesh, PLUS unwanted faces within the obstacles.

My current approach to get rid of these unwanted faces is to inspect every face in the triangulation, and store which ones happen to be within obstacles. Whenever I make use the triangulation to compute paths, I simply ignore all these unwanted faces.

This image shows a playable space with red polygonal obstacles and the corresponding triangulation in cyan. Notice the many triangles overlapping the red obstacles:

This image shows the same triangulation, excluding the unwanted faces:

Sidenote: you may have noticed that the vertices in the triangulation are slightly offset from the obstacle vertices - that is intentional and not important for this discussion

Problem

The limitation of this approach is that calls to locate(), which are very useful to rein in stray game characters, have no way to ignore the extra faces.

I did manage to work around this by first projecting my arbitrary point onto the playable space without using Spade, and then calling locate() using that point. However, this is a fairly finicky and error-prone process.

Suggestion

In the past, I used Triangle to generate these navigation meshes. A very convenient feature of Triangle is that it supports the concept of 'holes', which can be used to eliminate unwanted faces from the output. The first example on this page illustrates the idea, with the inside of the CMU letters not being filled with faces:

An important subtlety is that holes can have holes themselves. In Triangle, this is implemented by specifying the triangulation input in three parts:

• Vertices (same as Spade)
• Segments (same as constraint edges in Spade)
• Holes (one point per hole)

Here is how they describe the implementation of the holes:

The third section lists holes (and concavities, if -c is selected) in the triangulation. Holes are specified by identifying a point inside each hole. After the triangulation is formed, Triangle creates holes by eating triangles, spreading out from each hole point until its progress is blocked by PSLG segments; you must be careful to enclose each hole in segments, or your whole triangulation might be eaten away. If the two triangles abutting a segment are eaten, the segment itself is also eaten. Do not place a hole directly on a segment; if you do, Triangle will choose one side of the segment arbitrarily.

Many thanks in advance!

Update nn interpolation to accomodate the new dcel structure.

The nn interpolation algorithms work with tuples of fixed vertices instead of fixed edges. changing this will make them a bit faster.

RTree::bulk_load does not work for dimensions other than 2

As per the documentation:

Note: The current implementation only works for two dimensional data. If other dimensions are needed, please create an issue.

In particular, I'd like to be able to bulk load 4-dimensional coördinates.

Clean up nninterpolation example

• Handle interpolation methods uniformly
• Add some comments

Add Voronoi Computation

I'm currently building on Spade to compute Voronoi diagrams for some research code, and I'm wondering if you'd be interested in getting a pull request to add this as a module. I understand that (c.f. #45) you want to avoid feature bloat, but this seems like it should be a fairly common use case of a Delaunay triangulation library (and small enough of an addition not to merit another crate).

PartialEq trait bound for SimpleEdge

I'm getting an error when trying to remove SimpleEdge entries from an RTree:

the method `remove` exists but the following trait bounds were not satisfied:
        spade::primitives::SimpleEdge<types::Point<T>> : std::cmp::PartialEq

T in this case is constrained to num_traits::Float + SpadeNum, and I've implemented PointN for my Point type (which derives PartialEq itself) here – adding SimpleEdges and querying works perfectly, but I'm confused about how to add the PartialEq bound so I can remove them again.

BoundingRect does not implement spatial object

That should be easily fixable.

Split off R-Tree implementation

I'm currently working on splitting off the r-tree into its own package. One of Rusts strengths has always been Cargo, which allows to have many, small packages with a single use. R-Trees would actually be perfect in such a scenario.

I would also be looking to improve performance and to implement some more advanced algorithms - I still have some ideas for this in my mind!

I'm still looking for a good name, just in case anyone has a good idea.

Various iterators (e.g FacesIterator) absent from documentation

When looking at some iterator-returning functions, there is no corresponding documentation for the iterators. For instance, take FacesIterator:

(Link)

This makes it difficult to know which exact type it iterates over, etc.

Kernel definition

I've been trying to test the extensibility of spade by implementing a kernel for points on the unit sphere. The major issue I've hit is that pub trait DelaunayKernel<D: SpadeNum> is defined in terms of D rather than V: TwoDimensional<Scalar = D>, which (I think) means that the functions have to be implemented for all types V and can only use functions defined for trait TwoDimensional. Could it not be defined as pub trait DelaunayKernel<V: TwoDimensional<Scalar = D>>` instead?

Also, would a better default fn contained_in_circumference() not just be based on side_query()? Or is that inefficient?

(I think this relates to #28 but I'm not having the same issue that reporter was.)

use simple iterator, not IntoIterator for BoundingRect::from_points

To create BoundingRect from Vec<[f32; 2]> with BoundingRect::from_points
I have to use Vec::clone, because of BoundingRect::from_points requires IntoIterator.
Why not use Iterator and just clone [f32; 2] instead? Vec::clone is expensive - heap allocation,
while [f32; 2] clone is cheap.

Nearest neighbors result mismatch

As per the docs, my assumption is that RTree::nearest_neighbors should behave exactly like RTree:nearest_neighbor whenever there is a single nearest neighbor for a given point.

However I found a mismatch that's breaking my program:

        // `prev` is some arbitrary point that used
        // to belong to `rtree` but now it doesn't.
        let mut nns = rtree.nearest_neighbors(&prev);
        nns.sort();
        let nn1 = nns.iter().nth(0).unwrap();

        let nn = rtree.nearest_neighbor(&prev).unwrap();

        println!("query_point={:?}", prev);
        println!("nns={:?}", nns);
        println!("nn={:?}", nn);

        assert_eq!(*nn1, nn);

The assertion usually succeeds (which is expected), but sometimes it doesn't. Here's an example output of when it fails:

query_point=PointVertex { point: [486.5296335632694, 3987.037159235611], id: 1545 }
nns=[PointVertex { point: [484.4154017435969, 3914.9206580969], id: 1563 }]
nn=PointVertex { point: [449.87221229993327, 3986.728686301482], id: 2981 }
thread 'solution_is_computed_correctly_tsp_heuristic' panicked at 'assertion failed: `(left == right)`
  left: `PointVertex { point: [484.4154017435969, 3914.9206580969], id: 1563 }`,
 right: `PointVertex { point: [449.87221229993327, 3986.728686301482], id: 2981 }`', src/week3/solution.rs:24:9

As mentioned before, the assertion usually succeeds, e.g.:

query_point=PointVertex { point: [555.0393744191871, 3883.5123282564214], id: 567 }
nns=[PointVertex { point: [537.4013213059632, 3945.0350382362126], id: 3543 }]
nn=PointVertex { point: [537.4013213059632, 3945.0350382362126], id: 3543 }
query_point=PointVertex { point: [537.4013213059632, 3945.0350382362126], id: 3543 }
nns=[PointVertex { point: [518.5897669888586, 3953.4962614450205], id: 3200 }]
nn=PointVertex { point: [518.5897669888586, 3953.4962614450205], id: 3200 }
query_point=PointVertex { point: [518.5897669888586, 3953.4962614450205], id: 3200 }
nns=[PointVertex { point: [486.5296335632694, 3987.037159235611], id: 1545 }]
nn=PointVertex { point: [486.5296335632694, 3987.037159235611], id: 1545 }

Is this a misunderstanding on my part? Or is there a bug to be fixed?

Spade 1.5.0 is failing on nearest_neighbour queries

Spade 1.4.0 works correctly, but I'm seeing test failures on nearest-neighbour queries as of Spade 1.5.0: I'm getting a None value when querying. The worrying thing is that I can't reproduce them using Spade's native types.

This fails for our types:
https://github.com/urschrei/rust-geo/blob/5d888080885f52dc656ebf7af3ae4d423bea5aed/geo/src/algorithm/euclidean_distance.rs#L945-L966

Source for edges which are bulk-loaded into the tree (edges built using windows(2))
Source for points which are used to retrieve the nearest-neighbour edge from the tree

The test fails when querying using the tree using the point (6.0001320971764285, -6.483226510722902)

The Spade trait impls are as follows:

For Point (same as the Point2 type):

https://github.com/georust/rust-geo/blob/b8354152381f735ab765847b656e12afc5117869/geo-types/src/point.rs#L297-L336

For Line (same as the SimpleEdge type):

https://github.com/georust/rust-geo/blob/b8354152381f735ab765847b656e12afc5117869/geo-types/src/line.rs#L145-L167]

Things I've checked:

• That the point values making up the Lines in the RTree are the same as those which make up the SimpleEdges when running the test using Spade types ✅
• That the mbr values are the same for our types and for Spade Types ✅
• That the distance2 types are the same for our types and for Spade types (in some cases, they vary in the least significant digit, so I don't think that's the problem)

Correct (using Spade Types):

95.29292557779627
100.53487738887094
105.67537257174098
110.66490534771486
115.4554237886039
120.00079258305857
124.25723734483688
128.1837661840736
131.74256448158783
134.8993590643375
137.6237482748112
64.54457621139609
69.33509465228511
74.324627428259
79.46512261112903
84.70707442220369
89.99999999999997
139.88949475560952
141.6747781295393
142.96240514177447
143.73997524029863
143.73997524029866
45.100640935662554
48.257435518412194
51.81623381592642
55.74276265516312
59.999207416941445
142.96240514177447
141.6747781295393
139.88949475560952
137.62374827481125
134.89935906433752
131.74256448158786
42.37625172518882
40.110505244390524
38.32522187046073
37.03759485822556
36.26002475970139
36.00000000000001
110.66490534771505
115.45542378860407
120.00079258305868
124.257237344837
128.18376618407368
36.00000000000001
36.26002475970138
37.03759485822556
38.32522187046073
40.11050524439051
79.46512261112939
84.70707442220402
90.00000000000028
95.29292557779655
100.53487738887117
105.67537257174118
42.376251725188816
45.10064093566255
48.257435518412194
51.81623381592641
55.742762655163105
59.99920741694144
59.999207416941815
64.54457621139646
69.33509465228548
74.32462742825936

Using our types:

95.29292557779625
100.53487738887094
105.67537257174098
110.66490534771485
115.45542378860391
120.00079258305858
124.2572373448369
128.1837661840736
131.74256448158786
134.8993590643375
137.6237482748112
64.5445762113961
69.3350946522851
74.324627428259
79.46512261112905
84.70707442220369
89.99999999999997
139.88949475560952
141.6747781295393
142.96240514177447
143.7399752402986
143.73997524029866
45.100640935662554
48.25743551841219
51.81623381592642
55.74276265516311
59.999207416941445
142.96240514177447
141.6747781295393
139.88949475560952
137.62374827481125
134.89935906433752
131.74256448158786
42.37625172518882
40.110505244390524
38.32522187046073
37.03759485822555
36.260024759701395
36.000000000000014
110.66490534771503
115.45542378860405
120.0007925830587
124.25723734483701
128.18376618407368
36.000000000000014
36.26002475970138
37.03759485822555
38.32522187046073
40.11050524439051
79.46512261112939
84.70707442220402
90.00000000000027
95.29292557779657
100.53487738887115
105.67537257174116
42.37625172518881
45.100640935662554
48.25743551841219
51.8162338159264
55.742762655163105
59.99920741694143
59.999207416941815
64.54457621139647
69.33509465228549
74.32462742825935

Has something in the nearest_neighbour implementation changed that could cause this?

Low degree optimization for vertex removal in delaunay triangulations

Removal could be sped up immensely with the technique described in this paper:

http://www.sciencedirect.com/science/article/pii/S0925772110000799

CDT with intersecting constraints

Hi, I noticed your 2.0 post and was wondering whether you have any plans or ideas to add support for intersecting constraints for the CDT.

DelauneyTriangulation should be Sync and Send

The main datastructure for triangulation: DelauneyTriangulation is !Sync, and !Send. This prevents a fairly common use-case of computing a single triangulation and then using (read-only) references from multiple threads to say interpolate values to many different points.

The issue is with the usage of PhantomData for storing the kernel type. It is defined (in delauney2d.rs and cdt.rs) as:

    __kernel: PhantomData<*const K>,

The issue seems to be that *const K is neither Sync nor Send and that propogates to the whole structure. To the best of my understanding of the code here, we only need K and probably want it to be variant in K. In this case, a simple PhantomData<K> should suffice as it should also be variant in K.

Would be great if you would change those two uses, so that the overall structure may be used in multi-threaded scenarios. Nevertheless, thank you very much for this elegant implementation!

Add Constrained Delaunay Triangulation

Any plans on adding CDT support to this library?

Can I assume that the `FixedVertexHandle` returned by `DelaunayTriangulation::insert()` are in increasing order, and `FaceHandle::as_triangle()` retuns vertex in clockwise order?

I have written a POC to convert a convex hull into a set of triangle that cover the inside of the shape. To do so, I add all the vertex of the hull in counter-clockwise order with DelaunayTriangulation::insert() , then triangulate them, and keep triangles that have decreasing FixedVertexHandle.

This means that I'm using two assumptions:

• calling DelaunayTriangulation::insert() will returns FixedVertexHandle in increasing order.
• FaceHandle::as_triangle() returns vertex in clockwise order.

Can I rely on those assumptions?

vertex indices

You sometimes represent a mesh with an array of vertices, and an array of triangle indices. I would construct such an array with something like:

let verts = triangulation.vertices().map(|pt| pt.data).collect();
let tris = triangulation.inner_faces().map(|f| f.vertices()).flat_map(|v| v.index());

Except, in spade 2.0, the index method is private. Is there another way?

Spade 2.0

Even though the project is set to passively maintained, I'm currently working on a large refactoring in the background. Here's an issue to discuss what Spade's current shortcomings are and how I plan to overcome them. Please, do feel free to start a discussion!
That said, if you are interested in using spade, please don't be dismissed by this issue as it deliberately focuses only on the negative parts of Spade: It is still a feature rich and easy to use computational geometry library (let me know if you disagree!) that has proven itself in my personal projects. My experiences culminated in the ideas discussed here.

Current problems

Too many features

These features should probably be split into their own crates if required or be removed entirely

• Integer coordinates (along with the adaptive int kernel)
• f32 support (it is still possible to use f32 for storage, but it will be casted to f64 for calculation purposes)
• locate strategies. Those can probably be implemented on top of the triangulation.
• integration into cgmath and nalgebra, if the integration is kept, only feature gated and as a re-export
• farin interpolation
• Calculation Kernels should probably become an implementation detail, I don't see much sense for supporting the TrivialKernel at the moment.
• rtrees (These have already been extracted into the rstar crate)

Some missing features

• Bulk loading for triangulations
• Custom edge and face types
• Performance. Spade was not really focused on performance so far, I want to make this more of a priority.

Design changes

I believe that spade should be designed to be a "backend" for Delaunay related algorithms.
Interpolation is a good example: Even today, interpolation algorithms can be implemented efficiently by using the current public API. Interpolation should probably be moved to a separate module or even its own crate.
It may (I'm investigating that one) even be possible to implement the CDT based on the public Delaunay API.
Finding the right design would allow to create custom tailored algorithms fitting many niches (e.g., alpha shapes).

Also, I plan to change an algorithmic technicality (although an influential one): The introduction of the "infinite point". This is an imaginary point "infinitely far away" from any other point, it is connected to every point of the convex hull. The main motivation is simplicity, I hope that the introduction will simplify the handling of the convex hull significantly and improving performance. However, I'm still unsure how and if this point should be part of the public API.

Open questions

• I'm not 100% sure if a 2.0 release or a split off as a new package is more apt, but I'm in favour of creating a new package (similar to the rstar outsourcing)
• Should the infinite point become an implementation detail or be part of the public API?
• If it becomes part of the public API, how should it be handled? Is it a regular vertex whose position is never evaluated? Can VertexHandle point to the infinite point?

Current Status

This reflects the status of my local prototype, I plan to upload it onto a branch once the dust settles a bit. The steps are roughly ordered according to when I want to work on them:

• Removal of most of the above "unwanted features"
• Locate in triangulation queries
• Insertion
• Infinite point
• Vertex removal
• CDT
• Performance benchmarks
• Documentation updates
• Bulk loading

Final notes

Please, do feel free to open a discussion - there are many moving parts that need to be settled. If you even want to dive deeper, I'll happily answer questions or will mentor any kind of contribution.

Delaunay Triangulation: Removal of Vertices

Hi, do you see a possibility of adding removal operations to the Delaunay implementation? It looks like the incremental one, so I guess it should be possible.

I would be willing to help because I would like to have a Delaunay implementation for Rust that can cope with CGAL for C++.

Implement CDT vertex removal

Feature request: face handle of point contained in delaunay triangulation face

I am currently missing the functionality to get a FixedFaceHandle or FaceHandle<V> from a specific point.

Maybe i am overlooking something, otherwise this would be a useful additional feature.

///
/// Containing face of certain point. Returns None if face is incomplete.
///
fn containing_face(&self, point: &V::Point) -> Option<FaceHandle<V>>

Create benchmark for interpolations

I'd be interested in comparing the different interpolation strategies, as well as optimizing them.
Rusts integrated benchmark suite should be fine for this purpose, some fancy graphs would be nice.

Release new Spade version

Hi, looks liike upgrading num = 0.2 was significant as it gets rid of rustc-serialize which is deprecated. I'm using rust-geo, and was trying to compile it to wasm. I forked the repo and updated spade to the commit which updates num, and that allowed compiling to wasm.

May you please kindly release an update to spade (I assume it could be 1.5.2?). rust-geo already uses serde and the num-* = 0.2 family, so the update wouldn't be a breaking change to the library.

Thanks

This is related to georust/geo#245

Implementing bulk insertion for rtrees

The approach in this paper might be interesting:
https://www2.cs.arizona.edu/%7Ebkmoon/papers/dke06-bulk.pdf
However, there seem to be some simpler solutions (with certain drawbacks regarding quality), which could be implemented first.
The paper mentions some of these methods in its "previous work" chapter.

Serialization/Deserialization

Hey,
I'd be interested in serialization / deserialization to disk - any suggestions on where I should start to add this functionality?

Thanks,
Ben

Please update num to 0.2

I have to use nightly because of rocket. And I also need to use geo 0.10 which depends on spade 1.5.1. But spade fails to compile:

   Compiling spade v1.5.1
error[E0277]: the trait bound `num::BigInt: num::Signed` is not satisfied
  --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\traits.rs:39:6
   |
39 | impl SpadeNum for BigInt { }
   |      ^^^^^^^^ the trait `num::Signed` is not implemented for `num::BigInt`

error[E0277]: the trait bound `num::rational::Ratio<num::BigInt>: num::Signed` is not satisfied
  --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\traits.rs:40:6
   |
40 | impl SpadeNum for BigRational { }
   |      ^^^^^^^^ the trait `num::Signed` is not implemented for `num::rational::Ratio<num::BigInt>`

error[E0277]: the trait bound `num::rational::Ratio<bigvec::AdaptiveInt>: num::Signed` is not satisfied
  --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\traits.rs:42:6
   |
42 | impl SpadeNum for Ratio<AdaptiveInt> { }
   |      ^^^^^^^^ the trait `num::Signed` is not implemented for `num::rational::Ratio<bigvec::AdaptiveInt>`

error[E0277]: the trait bound `num::BigInt: num::Num` is not satisfied
  --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\bigvec.rs:99:10
   |
99 | impl <I> From<cg::Point2<I>> for BigVec2<BigInt> where I: cg::BaseNum + ToBigInt {
   |          ^^^^^^^^^^^^^^^^^^^ the trait `num::Num` is not implemented for `num::BigInt`
   |
note: required by `bigvec::BigVec2`
  --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\bigvec.rs:22:1
   |
22 | pub struct BigVec2<N: Num> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0277]: the trait bound `num::BigInt: num::Num` is not satisfied
   --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\bigvec.rs:105:10
    |
105 | impl <I> From<na::Point2<I>> for BigVec2<BigInt> where I: ToBigInt + na::Scalar {
    |          ^^^^^^^^^^^^^^^^^^^ the trait `num::Num` is not implemented for `num::BigInt`

    |
note: required by `bigvec::BigVec2`
   --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\bigvec.rs:22:1
    |
22  | pub struct BigVec2<N: Num> {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0277]: the trait bound `bigvec::AdaptiveInt: num_traits::Num` is not satisfied
   --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\bigvec.rs:149:6
    |
149 | impl Integer for AdaptiveInt {
    |      ^^^^^^^ the trait `num_traits::Num` is not implemented for `bigvec::AdaptiveInt`

error[E0277]: the trait bound `num::BigInt: num::Num` is not satisfied
   --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\bigvec.rs:100:5
    |
100 | /     fn from(v: cg::Point2<I>) -> Self {
101 | |         BigVec2::new(v[0].to_bigint().unwrap(), v[1].to_bigint().unwrap())
102 | |     }
    | |_____^ the trait `num::Num` is not implemented for `num::BigInt`
    |
note: required by `bigvec::BigVec2`
   --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\bigvec.rs:22:1
    |
22  | pub struct BigVec2<N: Num> {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^

error[E0277]: the trait bound `num::BigInt: num::Num` is not satisfied
   --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\bigvec.rs:106:5
    |
106 | /     fn from(v: na::Point2<I>) -> Self {
107 | |         BigVec2::new(v[0].to_bigint().unwrap(), v[1].to_bigint().unwrap())
108 | |     }
    | |_____^ the trait `num::Num` is not implemented for `num::BigInt`
    |
note: required by `bigvec::BigVec2`
   --> C:\Users\me\.cargo\registry\src\github.com-1ecc6299db9ec823\spade-1.5.1\src\bigvec.rs:22:1
    |
22  | pub struct BigVec2<N: Num> {
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^

error: aborting due to 8 previous errors

For more information about this error, try `rustc --explain E0277`.
error: Could not compile `spade`.

rustc 1.30.0-nightly (90d36fb59 2018-09-13)

At first I got compilation errors in num-bigint and num-rational but i cargo updated those, but I can't update num to 0.2 because spade requires 0.1.

Clean up rtreevis example

• Add points more consistently
• Maybe move GUI stuff into the example application module
• Add more options to change visibility of rtree / triangulation
• Add description of the right mouse button

nearest_n_neighbors_iter?

Would it be practical to have an iterator for nearest neighbors? I have a use case where I need to get the 10 closest items to a point that pass an additional check. Best case, I need to look at 10 items, worst case, I need 25,000.

_{P.s. your docs are easy for a newbie to follow, thanks!}

Re-introduce interpolation methods

Spade 2.0 removed interpolation support (e.g. natural neighbor interpolation) to get into a releasable state. This ticket aims to re-introduce them!

For the most part, it should be possible to copy the old methods and fix any compilation error - their basic workings remain the same.

Update documentation

Optional implementation of `HasPosition2D` for `glam::Vec2` and `glam::DVec2`

I use the glam crate in a project where I need to compute a delaunay triangulation. It would be nice to have a HasPosition2D implementation for the glam 2D vector types. Could this be added as an optional feature?