v1.4.0

DelaunayTriangulation v1.4.0

• Updated to AdaptivePredicates.jl v1.2, now allowing caches to be passed to the predicates involving incircle and orient3. These are only useful when using the AdaptiveKernel() kernel. Outside of triangulating, these caches are not passed by default, but can be provided. The functions get_incircle_cache and get_orient3_cache can be used for this purpose on a triangulation (without a triangulation, refer to AdaptivePredicate.jl's incircleadapt_cache and orient3adapt_cache). See #185.

Diff since v1.3.1

Merged pull requests:

• Upgrade to AdaptivePredicates 1.2 (#185) (@DanielVandH)

v1.3.1

DelaunayTriangulation v1.3.1

Diff since v1.3.0

Merged pull requests:

• Improve the README (#182) (@DanielVandH)
• Fix degenerate weighted triangulation (#184) (@DanielVandH)

Closed issues:

• Performance audit (#111)
• [JOSS] Review comments (#181)
• [BUG]: Degenerate weighted triangulation (#183)

v1.3.0

This release finally introduces weighted triangulations and power diagrams, and also allows for users to provide a generic convex polygon to for clipping a Voronoi tessellation instead of only the convex hull.

• Weighted triangulations have now been implemented, as have power diagrams. The weights are also no longer restricted to Float64 type. See #180.
• intersection_of_edge_and_bisector_ray now accepts a project keyword argument. See #180.
• get_weight(w, i) now returns, when i is not an integer, either i[3] if it represents a point in space or 0. See #180.
• Define project_onto_line(p, q, r) for projecting a point r onto the line defined by p and q. See #180.
• Fixed a bug with clipping Voronoi tessellations in cases where there are no intersections of any Voronoi polygon with the convex hull. See #180.
• voronoi now accepts an optional clip_polygon keyword argument, defaulting to nothing (corresponding to the convex hull), allowing for a convex clip polygon to be used instead of the convex hull. The clip_polygon should be a Tuple of the form (points, boundary_nodes) where the boundary_nodes give vertices of points adhering to the usual convention. Note that this could be used as an alternative to looping over get_polygon_coordinates for clipping to a rectangle. See #180.
• centroidal_smooth now accepts clip_points and clip_vertices as keyword arguments, defaulting to nothing (corresponding to the convex hull), to accommodate the new clip_polygon keyword argument in voronoi. See #180.
• has_multiple_curves, has_multiple_sections, and num_boundary_edges now have methods for Tuples of integers. A bug was also fixed with number_type of a Tuple of Tuples of coordinates returning the Tuple type instead of the coordinate type. See #180.

What's Changed

• Implement weighted Delaunay triangulations and power diagrams by @DanielVandH in #180

Full Changelog: v1.2.0...v1.3.0

v1.2.0

DelaunayTriangulation v1.2.0

Diff since v1.1.4

Merged pull requests:

• Better default set_point! for matrices, and check for dimension of the user's points (#178) (@DanielVandH)

Closed issues:

• [BUG]: centroidal_smooth fails when applied to the triangulation of a sphere, Möbius strip, or Swiss roll. (#177)

v1.1.4

DelaunayTriangulation v1.1.4

Diff since v1.1.3

Merged pull requests:

• Fix curve-bounded refinement with custom structs (#175) (@DanielVandH)

v1.1.3

DelaunayTriangulation v1.1.3

Diff since v1.1.2

Merged pull requests:

• make sort_triangle public (#174) (@DanielVandH)

v1.1.2

DelaunayTriangulation v1.1.2

Diff since v1.1.1

Merged pull requests:

• some notes in docstrings (#171) (@DanielVandH)

Closed issues:

• [BUG]: triangulate function is not type-stable (#170)

v1.1.1

DelaunayTriangulation v1.1.1

Diff since v1.1.0

Merged pull requests:

• Wrap matlab code in code blocks so it's easier to interpret in test/helper_functions.jl (#167) (@asinghvi17)
• Don't make exported symbols public (#168) (@DanielVandH)

v1.1.0

DelaunayTriangulation v1.1.0

Diff since v1.0.5

There are a lot of changes in this release, most of them irrelevant for the user. The most important change is the following:

• We now support a choice between fast, exact, and adaptive predicates via FastKernel(), ExactKernel(), and AdaptiveKernel(), respectively. The default is now AdaptiveKernel(). Moreover, triangle areas are now computed using the adaptive orient predicate to be more robust. See #165.

Previously, ExactPredicates.jl was used everywhere, which can be slow and not necessary for certain point sets. The FastKernel() option
has no exact or adaptive arithmetic and so should be used with caution. The documentation discusses these choices in more detail.

To actually configure the choice of predicate, you can e.g. in triangulate use the predicates keyword argument and pass one of
DelaunayTriangulation.FastKernel(), DelaunayTriangulation.ExactKernel(), or DelaunayTriangulation.AdaptiveKernel(). If you are computing a predicate manually, then the predicate is instead passed as the first argument.

Some other changes:

• Added DelauanyTriangulation.validate_triangulation for validating triangulations. See #131.
• Fixed a bug with the currently unused orient(p, q, r, s) predicate. See #131.
• Added private functions getz, _getz, getxyz, and _getxyz. See #131.
• jump_and_march has now been renamed to find_triangle. For compatibility, jump_and_march still works and is simply an alias of find_triangle. See #133.
• Mutable structs now use const on fields that aren't changed. For compatibility with older versions, this is implemented using a macro that is a no-op where this is not supported. See #140.
• We now use the public word to define public functions. This is only included on Julia versions v1.11 and above. See #140.
• We now test on the pre-release. See #140.
• The module DelaunayTriangulation now has a docstring. See #140.
• The .md files for tutorials and applications in the docs have been properly updated to match their literate counterparts. See #140.
• We now use a workflow to enforce changes to NEWS.md for any PRs. See #140.
• Improved the error message for an incorrect orientation. See #144.
• Added a CONTRIBUTING.md file and issue templates. See #160.
• Added is_point2 and is_point3 to detect if a given input is a point. This allows vector coordinates to be passed to convert_boundary_points_to_indices. See #161.
• Removed an allocation from add_vertex!. See #163.
• Fixed an issue with the user-supplied rng not being passed to lock_convex_hull!.

Merged pull requests:

• Allow for ExactPredicates to be toggled (#131) (@DanielVandH)
• Bump actions/checkout from 3 to 4 (#132) (@dependabot[bot])
• Change jump_and_march to find_triangle (#133) (@DanielVandH)
• Reorganise the includes (#135) (@DanielVandH)
• Change USE_EXACTPREDICATES to PREDICATES (#137) (@DanielVandH)
• Add public, const, and test on pre-release (#140) (@DanielVandH)
• Hint at what orientation means in the error message (#144) (@asinghvi17)
• Use contributions md (#160) (@DanielVandH)
• Fix convert_boundary_points_to_indices for vector of vector coordinates (#161) (@DanielVandH)
• Move out the config checks at the start of triangulate into their own function (#162) (@DanielVandH)
• Remove allocation in add_vertex! (#163) (@DanielVandH)
• Provide a choice of predicate kernel. Make AdaptivePredicates.jl the new default (#165) (@DanielVandH)
• Runic (#166) (@DanielVandH)

Closed issues:

• Spatial sorting for fast insertion (#34)
• Detection of intersecting segments in user input (#42)
• Support for clipped/centroidal Voronoi tessellations on non-convex geometries and multiply-connected/disjoint triangulations (#48)
• Integer division error with Float32 for clipped Voronoi (#72)
• Voronoi treemap (#87)
• Add an alias find_triangle for jump_and_march (#110)
• Add has_polygon_vertex for VoronoiTessellations (#115)
• Add clean!(::Triangulation) and clean!(::VoronoiTessellation) (with better names) (#116)
• Weighted triangulations and Voronoi power diagrams (#124)
• Centroidal Voronoi tessellations with inhomogeneous density (#125)
• Retriangulating perturbed data sets (#126)
• Inserting curves into a triangulation (#127)
• Maximum angle constraints (#128)
• Look into AdaptivePredicates.jl (#136)
• Thoughts for 3D Delaunay tetrahedralisations (#139)
• Add a reconstruct function for building triangulations from points and triangles (#143)

v1.0.5

DelaunayTriangulation v1.0.5

Diff since v1.0.4

Merged pull requests:

• Disable deepcopy on PolygonTrees (#130) (@DanielVandH)