hgeometry 0.12.0.0 → 0.12.0.1

raw patch · 2 files changed

+165/−2 lines, 2 filesdep ~vectorPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependency ranges changed: vector

API changes (from Hackage documentation)

Files

• changelog +162/−0
• hgeometry.cabal +3/−2

@@ -0,0 +1,162 @@+#+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.

@@ -1,5 +1,5 @@ name:                hgeometry-version:             0.12.0.0+version:             0.12.0.1 synopsis:            Geometric Algorithms, Data structures, and Data types. description:   HGeometry provides some basic geometry types, and geometric algorithms and@@ -20,6 +20,7 @@ build-type:          Simple  extra-source-files:  README.md+                     changelog                      changelog.org  Extra-doc-files:     docs/Data/PlaneGraph/small.png@@ -256,7 +257,7 @@               -- , ghc-typelits-natnormalise >= 0.6               -- , ghc-typelits-knownnat     >= 0.6 -              , vector                  >= 0.11 && < 0.12.2.0+              , vector                  >= 0.11               , data-clist              >= 0.1.2.3               , vector-circular         >= 0.1.2               , nonempty-vector         >= 0.2.0.0