#+STARTUP: showeverything

* Changelog

** 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.