Changelog of @hackage/hgeometry 0.14

#+STARTUP: showeverything

  • Changelog

** 0.14

  • Allow the associated/extra data of linesegments and intervals to differ when testing for intersections.
  • Intersection testing between line segments and rectangles
  • Testing if lines and/or line segments intersect no longer requires a Fractional constraint; Num is sufficient. However, in turn we now do need Ord rather than just Eq. That seemed a worthwile tradeoff though.
  • Cleaning up the public API by hiding several internal modules.
  • Introduced the 'HasSquaredEuclideanDistance' class describing geometry types for which we can compute the squared distance from a point to a geometry, and added instances for some of the basic geometries.
  • Fixed a bug in computing lengths to open line segments.
  • Removed some proxy arguments, in e.g. Data.Geometry.Point.coord, rather than take a Proxy to specify which coordinate we want, use type applications.
  • Support for GHC 9.0 and 9.2
  • Better support for open-ended line segments in the Bentley Ottmann line segment intersection algorithm.

** 0.13

  • Moved 'intersects' from the HasIntersectionWith class into a new class IsIntersectableWith. This allows separate (weaker) constraints for checking if geometries intersect rather than computing exact intersections.
  • New BezierSpline features.
  • "Zoom to fit" transformation.
  • Many fixes related to PlaneGraph/PlanarSubdivison; i.e. bugs in which order the vertices/darts where reported when traversing a face. The polygon representing the outer boundary now is some area inside a bounding polygon.
  • Fixed a bug in the DelaunayTriangulation.
  • Preliminary implementations for updating planar subdivisions (e.g. subdividing edges).

** 0.12

  • New website: https://hgeometry.org/
  • Switch polygon implementation from a circular seq to a circular vector.
  • Hide polygon implementation details.
  • Enforce CCW polygon order by default.
  • Fix bug in Data.Geometry.Polygon.Convex.extremes/maxInDirection.
  • Fix bug in pointInPolygon in case of degenerate situations.
  • Fix Read/Show instances for Point and Polygon such that 'read.show = id'.
  • Improved numerical robustness.
  • Random generation of monotone polygons. Thanks to @1ndy.
  • Random and uniform generation of convex polygons.
  • More IsIntersectableWith instances
  • Updated Show/Read instances for LineSegments
  • New algorithm: Visibility polygon in O(n log n) time.
  • New algorithm: Earclip triangulation in O(n^2) time worst case, O(n) time expected case.
  • New algorithm: Single-source shortest path in O(n) time.
  • New algorithm: Planar point locator in O(log n) time.
  • New algorithm: Point set diameter in O(n log n) time.
  • New algorithm: Convex hull of a polygon in O(n) time.
  • New algorithm: Diameter of a convex polygon in O(n) time.
  • New algorithm: Check if a point lies inside a convex polygon in O(n) time.
  • New algorithm: Discrete Frechet distance in O(n^2) time.

** 0.11

  • Removed Functor instance from Triangle and replaced it with Bifunctor/Bifoldable/Bitraversable
  • Testing if a point lies above/below a line is now in a typeclass, moreover there now is also an instance of this typeclass for planes. Hence, we can test if a point in R^3 lies above or below a plane.
  • Bugfixes in the incomingEdges and outgoingEdges functions in Planar/Plane graphs and Planar subdivisions
  • Added separate data types for Sides and Corners of Rectangles.
  • More functionality for working with Halfspaces
  • Fixed a bug in computing the intersection of overlapping linesegments
  • PolyLine.fromPoints now returns a Maybe PolyLine rather than a Polyine. Use fromPointsUnsafe for the old behavior.
  • Interval now no longer exports its constructor. Use the provided patterns instead.
  • Added an OpenLineSegment pattern/constructor
  • The corners and sides functions in Box now return specific types representing those rather than four tuples.
  • Added a BezierSpline module and data type (Thanks to Maarten).
  • Added a QuadTree implementation. It can be built from a set of points, and to represent the zeroset of some function.
  • Added a Naive implementation of Convex hull in R^3. Note however that it works only for points in general position. In particular, no four points should be coplanar.
  • Added a Data.Geometry.Directions module that defines cardinal and InterCardinal directions.
  • Added an Ellipse type (mostly so that hgeometry-ipe can read ellipses)
  • Added FunctorWithIndex, FoldableWithIndex, and TraversableWithIndex instances for Vector, and removed specifically exporting imap; we can now just use those functions from the Lens package.

** 0.10

  • renamed the smallest enclosing ball to RIC
  • improved tangency finding on convex hulls/chains
  • changes to how we order points in ccwCmpAround and cwCmpAround; these will report EQ if points appear at the same angle from the center point.
  • new functions ccwCmpAroundWith and cwCmpAroundWith that allow you to specify the direction corresponding to "zero".
  • bugfixes, in particular triangulating a polygon with holes now works properly.
  • removed some unused dependencies
  • we are no longer depending on ghc-plugins; as a result hgeometry now also compiles with ghcjs
  • more ToJSON/FromJSON instances.
  • removed the 'point2' and 'point3' functions in favor of the pattern synonyms Point2 and Point3.

** 0.9

  • Implemented 2D Linear Programming using randomized incremental construction (in (O(n)) expected time). This allows us to solve the following problems
    • testing starshapedness of simple polygons in expected linear time
    • testing if we can separate a set of red and a set of blue points in expected linear time.
  • Data types for halfspaces

** 0.8

  • Compatibility with GHC 8.6
  • Added (O(n\log n)) time closest pair algorithm.
  • Added arrangement data type
  • Various Bugfixes
  • Added Camera data type with some world to screen transformations.
  • Additional read/show instances
  • Updated some of the show instances for Ipe related types.

** 0.7

  • Compatibility with GHC 8.0-8.4
  • Implemented more Algorithms and Data Structures. This includes
    • Polygon triangulation
  • A new implementation of PlanarSubdivision that now also supports disconnected subdivsions.
  • Performance improvements by changing to a different Vector implementation. For low dimensional vectors (of dimension at most four) we now essentially use the types from linear, this gives significant speedups on several small benchmarks.
  • bugfixes.

** 0.6

  • Implemented more Algorithms and Data Structures. This includes
    • Bentley-Ottmannn line-segment intersection,
    • Well-Separated Pair decompositions,
    • extremal point/tangents for Convex hulls,
    • Minkowski sum for convex polygons,
    • one dimensional segment trees,
    • one dimensional interval trees, and a
    • KD-tree.
  • Several bug fixes, including a very stupid bug in Box
  • Separate ConvexPolygon type.
  • More thorough testing for some of the algorithms.
  • Started work on a proper representation for planar subdivsions. This includes a representation of planar graphs that support querying if two vertices are connected by an edge in \(O(1)\) time.
  • Dropped support for GHC 7.8

** 0.5

  • Implemented several algorithms, including Delaunay Triangulation, EMST, and Douglas Peucker.
  • Revamped the data types for Intersections

** 0.

  • Major rewrite from scratch, providing much stronger type-level guarantees. Incompatible with older versions.
  • Convex Hull and Smallest enclosing disk algorithms.
  • HGeometry now includes some very experimental and preliminary support for reading and writing Ipe7 files.

** 0.2 & 0.3

  • Internal releases.

** 0.1.1

  • Fixed a bug in point on n the line segment test
  • Generalized the types of inCircle, inDisc, onCircle, onDisc etc. We now need only that the type representing precision model implements the typeclass Num instead of `Floating'.

** 0.1

  • Initial release.