spade

chore: Release spade version 2.15.1

Fixed

• Prevents undesired splitting of inner constraint edges when RefinementParameters::keep_constraint_edges was used (#134)
• Prevents potential endless loop during refinement (#134)

chore: Release spade version 2.15.0

Added

• Implements ConstrainedDelaunayTriangulation::try_bulk_load_cdt for loading CDTs without panicking if any constraints intersect (#137)

Changed

• ConstrainedDelaunayTriangulation::bulk_load_cdt does load all vertices in order by default ("stable").
• ConstrainedDelaunayTriangulation::bulk_load_cdt_stable is deprecated. Use ...::bulk_load_cdt instead which behaves exactly the same.
• Optimized implementation of now stable ConstrainedDelaunayTriangulation::bulk_load_cdt. It is nearly as fast as its unstable alternative, Triangulation::bulk_load.
• Bulk loading a triangulation with a HierarchyHintGenerator does not load the hierarchy sequentially but uses bulk loading. This should speed up creating such triangulations.

chore: Release spade version 2.14.0

Fix

• Fixes #116 and #130
• Increases MSRV to 1.82.0

(cargo-release) spade version 2.13.0

Fix

• Fixes #124
• Increases MSRV to 1.56.1

Fix

• Fixes #113. This could lead to rare crashes when calling ConstrainedDelaunayTriangulation::add_constraint_and_split

(cargo-release) spade version 2.12.0

Fix

• Fixes potential crash of ConstrainedDelaunayTriangulation::add_constraint_and_split. This could only happen in rare situations if a newly inserted split point would lie very close to other vertices or edges of the triangulation. See #111
• Potentially breaking: Triangulation::locate, Triangulation::locate_with_hint, Triangulation::locate_vertex and Triangulation::locate_and_remove will all panic if called with a position with a NAN coordinate. The previous behavior was inconsistent - the methods would either crash or return a nonsensical result.

Added

• Added ConstrainedDelaunayTriangulation::remove_constraint_edge(edge)

Fix

• Fixes potential crash when using ConstrainedDelaunayTriangulation::add_constraint_and_split. See #109

Added

• Added basic mint support via the mint feature
• Implements Triangulation::get_vertex(FixedVertexHandle) (See #106)

Fix

• Fixes potential crash when inserting / locating vertices (See #107)

Added

• Added ConstrainedDelaunayTriangulation::try_add_constraint
• Added ConstrainedDelaunayTriangulation::add_constraint_and_split

Added

• Added LineIntersectionIterator and Intersection
• Added Cdt::get_conflicting_edges_between_vertices and Cdt::get_conflicting_edges_between_points

Added

• Implements ConstrainedDelaunayTriangulation::bulk_load_cdt
• Implements ConstrainedDelaunayTriangulation::bulk_load_cdt_stable

(cargo-release) spade version 2.6.0

Added

• Implements DelaunayTriangulation::bulk_load_stable (See #77)
• Implements FixedVertexHandle::from_index(usize)

(cargo-release) spade version 2.5.1

Fix

• Locating or inserting vertices into a CDT could sometimes end up in an infinite loop. See #98.

(cargo-release) spade version 2.5.0

Added

• Implements natural neighbor interpolation. See type NaturalNeighbor for more on this!

Fix

• Fixes PointProjection::reversed() - the method would return a projection that gives sometimes incorrect results.

(cargo-release) spade version 2.4.1

Fix

• Fixes panic during refinement due to rounding errors (see #96)
• Inserting a vertex onto a constraint edge of a degenerate CDT would not create a new constraint edge.

(cargo-release) spade version 2.4.0

Added

• Implements Delaunay refinement: Adds ConstrainedDelaunayTriangulation::refine, along with RefinementParameters to modify the refinement behavior.
• Added method ConstrainedDelaunayTriangulation::add_constraint_edges for simpler creation of strips and loops of connected constraint edges.
• Adds impl From<DelaunayTriangulation<...>> for ConstrainedDelaunayTriangulation<...> for converting regular triangulations into CDTs.

Fix

• Fixes compilation issues when using serde together with --no-default-features (#95)

Added

• Adds no_std support (when using default-features = false, #92)

Changed

• Specializes nth and nth_back for any vertex, face and edge iterator
• Removed optional dependency (#91)
• Updated robust crate to 1.1.0 (#90)

Added

• Added DirectedEdgeHandle::center and UndirectedEdgeHandle::center
• Added UndirectedEdgeHandle::nearest_point
• Adds UndirectedEdgeHandle::is_constraint_edge and DirectedEdgeHandle::is_constraint_edge (only implemented for edge handles of a CDT)

Fix

• Fix nearest_neighbor hinting

Added

• Added crate::FloatTriangulations for additional methods of triangulations over f32 or f64
• Added FloatTriangulation::get_edges_in_rectangle
• Added FloatTriangulation::get_edges_in_circle
• Added FloatTriangulation::get_vertices_in_rectangle
• Added FloatTriangulation::get_vertices_in_circle
• Added index function for any fixed and dynamic handle, returning the internal index of the element.
• Added missing DelaunayTriangulation::Clone implementation
• Added DirectedEdgeHandle::positions
• Added Triangulation::clear

Bugfixes

• (breaking fix) ConstrainedDelaunayTriangulation::can_add_constraint_edge accidentally returned the wrong result (true when it should have returned false and vice versa) #75
• Fixes a crash that could occur when inserting an element into a CDT (#78)

This release is focussed on API refinement, performance improvements and usability improvements.

General API refinement

Many features of Spade 1 showed too little benefit to legitimize keeping them. Spade 2.0 attempts to slim down the API surface to a few important functions and types and leaves out the more complicated bits to make it more simple to use.

Removed features (planned to be re-introduced in an upcoming release)

• Removed interpolation functions

Removed features (not planned to re-introduced)

• Removed support for integer coordinates. Only f64 and f32 can be used as scalar types.
• Removed support for cgmath and nalgebra crate to slim down the crate dependencies.
• Removed PointN. Using Spade now requires to convert any position into Spade::Point2.
• Removed r-tree data structure (it has been moved into the rstar crate)
• Removed geometric primitives (SimpleCircle, SimpleEdge, SimpleTriangle)
• Removed support for custom calculation kernels. Spade now uses the precise calculation kernel by default (previously called FloatKernel).
• Removed support for Delaunay triangulations backed by r-trees. Use the newly introduced HierarchyHintGenerator instead.

Added features

• Added basic support for Voronoi diagrams (refer to the documentation of struct DelaunayTriangulation)
• Added struct HierarchyHintGenerator, a hint generator with small performance and memory overhead which is optimized for uniformly distributed data.
• Improved conciseness of handle types (refer to the handles module for more information):
  • Introduced UndirectedEdgeHandle to refer to undirected edges of the triangulation
  • FaceHandle is now parameterized to denote if it refers to an inner face or to the single outer face
  • Added some methods on the individual handle types
  • Added iterators for all handle types (see handles module)
  • Fixed directed edge handles can now be reversed
• Both DelaunayTriangulation and CDT now allow to also annotate undirected edges with arbitrary data
• Added Triangulation::convex_hull which allows to directly iterate over the triangulation's convex hull
• Added Triangulation::bulk_load for efficient bulk creation of triangulations.

Changed

• Performance improvements
• The newly introduced HierarchyHintGenerator should outperform the r-tree based hint generator consistently for uniformly distributed data sets (2x - 3x times faster)
• LastUsedVertexHintGenerator and its predecessor DelaunayWalkLocate are still comparable.
• The new Triangulation::bulk_load will be more efficient for creating triangulations from a given set of vertices compared to inserting them incrementally.
• Cleaned up crate dependencies: Spade 2.0 depends only on 4 other crates without any transitive dependencies. This should make it more viable to include Spade into other projects.
• Renamed any o_next / o_prev function to next / prev.
• Renamed sym to rev
• Many other smaller changes - they are omitted from this changelog.

Migration notes

Keep in mind that not all features have been preserved before attempting to upgrade. Other than that, upgrading should be mostly consist of renaming:

• FloatDelaunayTriangulation and FloatCdt have been replaced by DelaunayTriangulation and ConstrainedDelaunayTriangulation
• IntDelaunayTriangulation is not supported anymore. Use f64 or f32 as scalar type instead if possible.
• DelaunayWalkLocate has been renamed to LastUsedVertexHintGenerator
• DelaunayTreeLocate has been replaced by HierarchyHintGenerator

Bugfixes

• Removing elements from an rtree could leave the tree in an inconsistent state (#55). This made some nearest neighbor queries return incorrect results.

Changed

• Bumped compatible nalgebra version to 0.18
• Updated edition to 2018
• Fixed all clippy findings
• Cargo fmt'ed source code

Bugfixes

• SimpleTriangle now overwrites both Hash and PartialEq

Changed

• Updated README.md
• Merge #41: Use smallvec in barycentric interpolation
• Bumped compatible cgmath version to 0.17.*
• Bumped compatible nalgebra version to 0.17.*

• SimpleEdge, SimpleCircle, BoundingRect now derive Clone, Copy, PartialEq, Eq, PartialOrd, Ord and Hash
• CdtEdge is now public - the type cannot be used, but may be necessary for method signatures containing CDTs.
• Added some standard derives for various other types that are applicable.

Changed

• Bumped compatible nalgebra version to 0.16.*
• Bumped compatible num version to >=0.1, <=0.2.*. This may be a breaking change due to the way cargo resolves dependencies. An upgrade to num 0.2 is recommended.

Bugfixes

• nearest_neighbor sometimes incorrectly returned None

Added

• Added RTree::nearest_neighbor_iterator

Changed

• Improved performance of single nearest neighbor queries
• Bumped compatible nalgebra version to 0.15.*
• Bumped compatible cgmath version to 0.16.*

Added

• Added cargo feature 'serde_serialize', rtrees, triangulations and primitives now support serialization with serde!
• RTrees implement Debug
• New constructor: BoundingRect::from_points

Changed

• Bumped compatible nalgebra version to 0.14.*

Bugfixes

• BoundingRect now implements SpatialObject

Deprecated

• spade::delaunay::DelaunayTriangulation::lookup is deprecated, use locate_vertex instead
• spade::delaunay::DelaunayTriangulation::lookup_and_remove is deprecated, use locate_and_remove instead

Changed

• Bumped compatible cgmath and nalgebra versions.
• Spade's various kernels are not instantiable anymore and implement Clone.

Added

• Spade now implements constrained delaunay triangulations!
• locate and nearest_neighbor now also work with degenerate triangulations
• Added constrained triangulation example
• Added bulk loading for r-trees
• DelaunayTriangulation now implements Clone
• New method for triangulations: get_edge_from_neighbors to get an existing edge from its two adjacent points.

Bugfixes

• Fixed SimpleCircle distance calculation for more than 2 dimensions.

Changed

• Bumped compatible cgmath and nalgebra versions. Unfortunately, due to the way Cargo handles "external dependencies" (thus, dependencies whose types are part of spade's public API like cgmath and nalgebra Points), this must be considered a breaking change.
• FloatKernel now works happily with f32 coordinates. They will be cast to double precision before the kernel evaluates any query, thus, no performance gain results from this. Only the space requirements will differ.

Deprecated

• spade::delaunay::RTreeDelaunayLocate<T> is deprecated, use spade::delaunay::DelaunayTreeLocate<T> instead
• spade::delaunay::TriangulationWalkLocate<T> is deprecated, use spade::delaunay::DelaunayWalkLocate instead ( without any type argument)

Changed

• Insertion into a delaunay triangulation now uses SmallVec from the smallvec crate for better performance.
• Improved interpolation performance - natural neighbor interpolation methods will be significantly faster now.

Added

• Added struct spade::delaunay::DelaunayWalkLocate. The struct will now keep track of the last query made and use it for the next query. A query can be an interpolation, lookup, locate or nearest neighbor query, insertion will also update the hint to the inserted vertex. This means: Subsequent queries that are close to each other will run in O(1) without the need of giving an explicit hint. This behaviour was only implemented for insertion until now.
• Added method spade::delaunay::DelaunayTriangulation::nearest_neighbor
• Added method spade::delaunay::DelaunayTriangulation::locate_vertex
• Added method spade::primitives::SimpleEdge::length2
• Added an interpolation benchmark

A lot has changed for the 1.0. release, only larger changes are shown.

Changed

• Changed project license from Apache 2.0 to dual MIT / Apache 2.0
• VectorN renamed to PointN
• Bumped supported nalgebra version to 0.11.*
• Point2, Point3 ... from cgmath and nalgebra crates do implement VectorN
• Vector2, Vector3 ... from cgmath and nalgebra crates do not implement VectorN
• Moved all kernels from the root to spade::kernels
• Moved delaunay triangulation and handle types to spade::delaunay
• Moved the rtree to spade::rtree::RTree
• Renamed DelaunayTriangulation::lookup_in_triangulation to locate
• Renamed DelaunayTriangulation::handle(..) to vertex(..)

Added

• Added support for vertex removal in delaunay triangulations!
• Added DelaunayTriangulation::barycentric_interpolation(..)
• Added support for different lookup methods for delaunay triangulation (see DelaunayLookupStructure)
• Added a user guide! Check it out here
• locate and lookup can now be used with a hint (see {insert|locate}_with_hint)
• Added type shorthands spade::delaunay::{Float|Int}Triangulation and quick creation methods with_tree_lookup and with_walk_lookup
• Added struct EdgeHandle and type FixedEdgeHandle.
• Added struct FaceHandle and type FixedFaceHandle.
• Added methods DelaunayTriangulation::edge(..) and ::face(..)
• Added DelaunayTriangulation::infinite_face()
• Added DelaunayTriangulation::is_degenerate()
• Added DelaunayTriangulation::num_{edges|triangles|faces}()
• CCWIterator and ONextIterator now both implement DoubleEndedIterator

Removed

• Removed support for pointer like types (e.g. inserting Box<Point2<_>>) to simplify type signatures.
• Removed DelaunayTriangulation::lookup_in_circle(..) and lookup_in_rect(..). These methods will likely be added again in a later release.

Changed

• VectorN trait trimmed down, now contains only a small set of functions.

Added

• [S; 2], [S; 3] and [S; 4] now implement VectorN and TwoDimensional or ThreeDimensional when appropriate. This change allows to insert fixed size arrays that encode positions directly into RTree or DelaunayInterpolation.

Removed

• Removed dependencies on crate rand and crate noise

Changed

• Function signatures of nn_interpolation_c1_* slightly modified.
• Sibson's c1 interpolant now comes with a flatness factor

Fixes

• Wrong documentation link in crate description
• Fixed signatures of estimate_normal and estimate_gradient

Added

• DelaunayTriangulation: estimate_normal, estimate_normals, estimate_gradient, estimate_gradients
• Added Sibson's c1 interpolant, DelaunayTriangulation::nn_interpolation_c1_sibson
• Added Farin's c1 interpolant, DelaunayTriangulation::nn_interpolation_c1_farin
• trait ThreeDimensional

Changed

• Type signatures of RTree and DelaunayTriangulation have now an additional parameter, B. This allows to insert pointer like objects (that is, an object B: Borrow<T>) into the tree.

Added

• Documentaion to all functions and types intended for public use
• RTree::lookup_mut(..)
• RTree::contains(..)
• DelaunayTriangulation::handle_mut(..)
• DelaunayTriangulation::lookup_mut(..)
• DelaunayKernel::point_on_edge(..)
• SimpleTriangle::nearest_point_on_edge(..)
• types TwoDimensional, HasPosition2D

Removed

• SimpleEdge::point_on_edge(..)
• SimpleTriangle::is_ordered_ccw(..)

Fixed

• Potential crashes when inserting points into a DelaunayTriangulation, even though FloatKernel was used.

Changed

• cgmath dependency bumped to 0.12.*
• DelaunayTriangulations and some primitives now will only work with two-dimensional coordinates. Using higher dimensions actually yielded unspecified results.

Initial commit