#+STARTUP: showeverything

* Changelog

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