#+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](https://hackage.haskell.org/package/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.