The hgeometry package

[Tags: bsd3, library]

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]

Properties

Versions0.1.0.0, 0.1.1.0, 0.1.1.1, 0.4.0.0
Change logNone available
Dependenciesbase (>=4.7 && <5), bifunctors (>=4.1), bytestring (>=0.10), containers (>=0.5.5), data-clist (>=0.0.7.2), fixed-vector (>=0.6.4.0 && <0.7), hexpat (>=0.20.7), lens (>=4.2), linear (>=1.10), mtl, parsec (>=3), random, semigroups (>=0.15), singletons (==1.0.*), text (>=0.11), validation (>=0.4), vector (>=0.10), vinyl (==0.5.*) [details]
LicenseBSD3
AuthorFrank Staals
Maintainerf.staals@uu.nl
CategoryGeometry
Home pagehttp://fstaals.net/software/hgeometry
Source repositoryhead: git clone http://github.com/noinia/hgeometry
UploadedMon May 4 15:20:41 UTC 2015 by FrankStaals
DistributionsNixOS:0.4.0.0
Downloads537 total (28 in last 30 days)
Votes
0 []
StatusDocs not available [build log]
All reported builds failed as of 2015-05-19 [all 2 reports]

Modules

Downloads

Maintainers' corner

For package maintainers and hackage trustees

Readme for hgeometry-0.4.0.0

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:

newtype Point (d :: Nat) (r :: *) = Point { toVec :: Vector d r }

Please note that aspect (2), implementing good algorithms, is much work in progress. HGeometry currently has only very basic types, and implements only two algorithms: an (optimal) $O(n \log n)$ time algorithm for convex hull, and an $O(n)$ expected time algorithm for smallest enclosing disk (both in $R^2$).

Current work is on implementing $O(n \log n + k)$ time red-blue line segment intersection. This would also allow for efficient polygon intersection and map overlay.

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

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