Minor bugfix for a corner-case

What's Changed

• Fix super-triangle calculation for tiny bounding boxes by @artem-ogre in #175

Full Changelog: 1.4.0...1.4.1

1.4.0

What's Changed

• Improvements by @artem-ogre in #158
• Polish intersecting constraints error by @artem-ogre in #159
• Fix bug in handling hanging edges when triangulating pseudo-polygons by @artem-ogre in #160
• Small fixes and improvements by @artem-ogre in #161

Full Changelog: 1.3.6...1.4.0

1.3.6

What's Changed

• Fix bugs found with fuzzing by @artem-ogre in #156

Full Changelog: 1.3.5...1.3.6

[1.3.5] Bugfixes

What's Changed

• Fix potentially uninitialized variable warning on Visual Studio by @here-abarany in #128
• Mention availability in the spack package manager by @jcortial-safran in #135
• Add standard defines to PREDICATES_FAST_FMA check by @here-abarany in #136
• Bugfix hanging edge by @artem-ogre in #140
• Fix multiple hanging edges and zero overlaps by @artem-ogre in #143
• #148 Fix bug when resolving intersections by @artem-ogre in #149

New Contributors

• @here-abarany made their first contribution in #128
• @jcortial-safran made their first contribution in #135

Full Changelog: 1.3.0...1.3.5

1.3.4

What's Changed

• Fix potentially uninitialized variable warning on Visual Studio by @here-abarany in #128
• Mention availability in the spack package manager by @jcortial-safran in #135
• Add standard defines to PREDICATES_FAST_FMA check by @here-abarany in #136
• Bugfix hanging edge by @artem-ogre in #140
• Fix multiple hanging edges and zero overlaps by @artem-ogre in #143
• #148 Fix bug when resolving intersections by @artem-ogre in #149

New Contributors

• @here-abarany made their first contribution in #128
• @jcortial-safran made their first contribution in #135

Full Changelog: 1.3.0...1.3.4

1.3.0

What's Changed

• Fixes for #116 #110 by @artem-ogre in #117
• New insertion sequence by @artem-ogre in #124
• Update how boost is used for c++98 by @artem-ogre in #125
• #123 Make it possible to add non-boundary edges by inserting such edges twice into the triangulation by @artem-ogre in #126

Full Changelog: 1.2...1.3.0

[1.2.0][Use `master` instead of releases] Conforming triangulation, bug fixes, and more.

If possible please use latest master instead of releases.

Releases can be outdated and can lag significantly behind the main branch.

What's Changed

• #54 Add function to API that extracts all edges of given triangles by @artem-ogre in #55
• #57 Make Delaunay triangulation example obvious by @artem-ogre in #58
• Add missing CDT_INLINE_IF_HEADER_ONLY to CalculateTriangleDepths by @kalleakerblom in #60
• Replace use of std::random_shuffle with std::shuffle by @kalleakerblom in #59
• Fix isFlipNeeded by @Islam0mar in #67
• Ensure deterministic random by @artem-ogre in #61
• Fix/export definitions by @egladil86 in #72
• fix cdt_export.h location on install by @egladil86 in #71
• #79 Fix KDTree to handle zero-size bounding box by @artem-ogre in #80
• #78 Fix includes for extras by @artem-ogre in #81
• Feature/conform to edges by @artem-ogre in #87
• Add tests by @artem-ogre in #89
• Add ground truth tests helpers and add a test by @artem-ogre in #90
• Make ground truth tests data driven, fix topology neighbor indices by @artem-ogre in #91
• Extend ground truth tests by @artem-ogre in #92
• #84 improve erase xxx perf by @artem-ogre in #93
• #100 Fix bug in predicates by @artem-ogre in #101
• 86 avoid stack overflow by @artem-ogre in #102

New Contributors

• @kalleakerblom made their first contribution in #60
• @Islam0mar made their first contribution in #67
• @egladil86 made their first contribution in #72

Full Changelog: 1.1.2...1.2

[v1.1.2] Performance improvements and overlapping boundaries support

This is a major release containing new features.

Performance Improvements

• Vertex insertion order is now randomized by default. This results in better performance overall and avoids many worst-case situations.
• Boost's RTree is replaced with a custom kd-tree implementation included into CDT sources.
  It outperforms boost::rtree and has a significantly smaller memory footprint.
• Boost RTree and nearest-random point locators are removed.
• Index types used by CDT are changed to 32-bit to reduce required memory. 64-bit indices can be enabled with CDT_USE_64_BIT_INDEX_TYPE.

Also see: Issue: #40 Pull-request: #45

Boost dependency is not necessary

As boost::rtree is replaced with custom kd-tree implementation, boost is mostly needed for c++98 compatibility and not for performance.
This means that most of the users will not need to enable boost.

Overlapping boundaries support

Enables handling overlaping boundaries in hole-removal algorithm.
Here is an example:

Algorithm tracks edges that were constrained more than once in insertEdges.
New PeelLayer and CalculateTriangleDepth functions handle overlapping boundaries.
Peel layer can now return seeds for next layer and deeper layers (due to overlapping boundaries).

Also see: Issue: #42 Pull-request: #43

Other changes/fixes

• README and doxygen docs are updated
• #34 Do not allow flipping a fixed edge #44
• Some fixes for broken c++98 compatibility
• Fixes in verifyTopology and InitializeWithGrid: #47 #48
• More fixes after 1.1.1: #51

[v1.0.1] Fix bug in "is edge flip required' test

Overview

Bug-fix release: fix an error in code that tests if an edge flip is required.
Issue: #37
Fixing PR: #38

Fix Details

Previously flip was rejected only if both vertices of flip-candidate edge belong to the super-triangle.
This sometimes resulted in wrong edges and incorrect convex-hull.
The change: instead reject the edge-flip if

• at least one flip-candidate edge's vertex belongs to super-triangle
• original edge does not touch super-triangle.

If the case when both original edge and flip-candidate edge touch super-triangle use normal circumcircle test as a tie-breaker.

Two test files for regression testing are added.

[v1.0.0] CMake, custom point/edge types, custom super geometries

This is a first stable version that uses modern CMake. This enables easy consumption for CMake-based projects.

New features and improvements:

• Custom point/edge types supported in insertVertices and insertEdges
• Functionality to use any custom geometry as a target instead of a super-triangle (see InitializeWithGrid.h)
• Refactor calculating triangle contour depths
• Extend RemoveDuplicatesAndRemapEdges to also return indices duplicates
• Small performance improvements and fixes