hgeometry: Geometric Algorithms, Data structures, and Data types.

[ bsd3, geometry, library ] [ Propose Tags ]

HGeometry provides some basic geometry types, and geometric algorithms and data structures for them. The main two focusses are: (1) Strong type safety, and (2) implementations of geometric algorithms and data structures with good asymptotic running time guarantees.


[Skip to Readme]

Modules

[Index]

Flags

Manual Flags

NameDescriptionDefault
examples

Build demonstration programs

Disabled

Use -f <flag> to enable a flag, or -f -<flag> to disable that flag. More info

Downloads

Note: This package has metadata revisions in the cabal description newer than included in the tarball. To unpack the package including the revisions, use 'cabal get'.

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees

Candidates

Versions [RSS] 0.1.0.0, 0.1.1.0, 0.1.1.1, 0.4.0.0, 0.5.0.0, 0.6.0.0, 0.7.0.0, 0.8.0.0, 0.9.0.0, 0.10.0.0, 0.11.0.0, 0.12.0.0, 0.12.0.1, 0.12.0.2, 0.12.0.3, 0.12.0.4, 0.13, 0.14
Dependencies base (>=4.8 && <5), bifunctors (>=5), bytestring (>=0.10), containers (>=0.5.5), data-clist (>=0.0.7.2), directory, fixed-vector (>=0.6.4.0 && <0.10), Frames (>=0.1.0.0), hexpat (>=0.20.9), lens (>=4.2), linear (>=1.10), mtl, optparse-applicative, parsec (>=3), random, semigroupoids (>=5), semigroups (>=0.15), singletons (>=1.0 && <2.0), template-haskell, text (>=1.1.1.0), time, vector (>=0.10), vinyl (>=0.5 && <0.6) [details]
License BSD-3-Clause
Author Frank Staals
Maintainer frank@fstaals.net
Revised Revision 1 made by GeorgeWilson at 2018-06-04T07:52:39Z
Category Geometry
Home page https://fstaals.net/software/hgeometry
Source repo head: git clone https://github.com/noinia/hgeometry
Uploaded by FrankStaals at 2016-06-11T10:07:51Z
Distributions
Reverse Dependencies 6 direct, 8 indirect [details]
Executables hgeometry-examples
Downloads 11665 total (66 in the last 30 days)
Rating 2.0 (votes: 1) [estimated by Bayesian average]
Your Rating
  • λ
  • λ
  • λ
Status Docs uploaded by user
Build status unknown [no reports yet]

Readme for hgeometry-0.5.0.0

[back to package description]

HGeometry

Build Status Hackage

HGeometry provides some basic geometry types, and geometric algorithms and data structures for them. The main two focusses are: (1) Strong type safety, and (2) implementations of geometric algorithms and data structures with good asymptotic running time guarantees. Design choices showing these aspects are for example:

  • we provide a data type Point d r parameterized by a type-level natural number d, representing d-dimensional points (in all cases our type parameter r represents the (numeric) type for the (real)-numbers):
newtype Point (d :: Nat) (r :: *) = Point { toVec :: Vector d r }
  • the vertices of a PolyLine d p r are stored in a Data.Seq2 which enforces that a polyline is a proper polyline, and thus has at least two vertices.

Please note that aspect (2), implementing good algorithms, is much work in progress. HGeometry currently has only very basic types, and implements only a few algorithms:

  • two (optimal) \(O(n \log n)\) time algorithms for convex hull in \(\mathbb{R}^2\): the typical Graham scan, and a divide and conqueror algorithm,
  • an \(O(n)\) expected time algorithm for smallest enclosing disk in \(\mathbb{R}^\)2,
  • the well-known Douglas Peucker polyline line simplification algorithm,
  • an \(O(n \log n)\) time algorithm for computing the Delaunay triangulation (using divide and conqueror).
  • an \(O(n \log n)\) time algorithm for computing the Euclidean Minimum Spanning Tree (EMST), based on computing the Delaunay Triangulation.

A Note on the Ext (:+) data type

In many applications we do not just have geometric data, e.g. Point d rs or Polygon rs, but instead, these types have some additional properties, like a color, size, thickness, elevation, or whatever. Hence, we would like that our library provides functions that also allow us to work with ColoredPolygon rs etc. The typical Haskell approach would be to construct type-classes such as PolygonLike and define functions that work with any type that is PolygonLike. However, geometric algorithms are often hard enough by themselves, and thus we would like all the help that the type-system/compiler can give us. Hence, we choose to work with concrete types.

To still allow for some extensibility our types will use the Ext (:+) type. For example, our Polygon data type, has an extra type parameter p that allows the vertices of the polygon to cary some extra information of type p (for example a color, a size, or whatever).

data Polygon (t :: PolygonType) p r where
  SimplePolygon :: C.CList (Point 2 r :+ p)                         -> Polygon Simple p r
  MultiPolygon  :: C.CList (Point 2 r :+ p) -> [Polygon Simple p r] -> Polygon Multi  p r

In all places this extra data is accessable by the (:+) type in Data.Ext, which is essentially just a pair.

Reading and Writing Ipe files

Apart from geometric types, HGeometry provides some interface for reading and writing Ipe (http://ipe.otfried.org). However, this is all very work in progress. Hence, the API is experimental and may change at any time!