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

This is a package candidate release! Here you can preview how this package release will appear once published to the main package index (which can be accomplished via the 'maintain' link below). Please note that once a package has been published to the main package index it cannot be undone! Please consult the package uploading documentation for more information.

[maintain] [Publish]

Warnings:

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. Note that HGeometry is still highly experimental, don't be surprised to find bugs.


[Skip to Readme]

Properties

Versions 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.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
Change log None available
Dependencies base (>=4.8 && <5), bifunctors (>=4.1), bytestring (>=0.10), containers (>=0.5.5), contravariant (>=1.4), data-clist (>=0.0.7.2), deepseq (>=1.1), directory, fixed-vector (>=0.6.4.0), Frames (>=0.1.3.0), hexpat (>=0.20.9), lens (>=4.2), linear (>=1.10), mtl, optparse-applicative, parsec (>=3), random, semigroupoids (>=5), semigroups (>=0.18), singletons (>=2.0), template-haskell, text (>=1.1.1.0), time, vector (>=0.11), vinyl (>=0.5 && <0.6) [details]
License BSD-3-Clause
Author Frank Staals
Maintainer frank@fstaals.net
Category Geometry
Home page https://fstaals.net/software/hgeometry
Source repo head: git clone https://github.com/noinia/hgeometry
Uploaded by FrankStaals at 2017-01-17T19:32:56Z

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

Maintainer's Corner

Package maintainers

For package maintainers and hackage trustees


Readme for hgeometry-0.6.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:

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

Please note that aspect (2), implementing good algorithms, is much work in progress. Only a few algorithms have been implemented, some of which could use some improvements. Currently, HGeometry provides the following algorithms:

It also has some geometric data structures. In particular, HGeometry contans an implementation of

HGeometry also includes a datastructure/data type for planar graphs. In particular, it has a `EdgeOracle' data structure, that can be built in \(O(n)\) time that can test if the graph contains an edge in constant time.

Numeric Types

All geometry types are parameterized by a numerical type r. It is well known that Floating-point arithmetic and Geometric algorithms don't go well together; i.e. because of floating point errors one may get completely wrong results. Hence, I strongly advise against using Double or Float for these types. In several algorithms it is sufficient if the type r is Fractional. Hence, you can use an exact number type such as Rational.

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.CSeq (Point 2 r :+ p)                         -> Polygon Simple p r
  MultiPolygon  :: C.CSeq (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! Here is an example showing reading a set of points from an Ipe file, computing the DelaunayTriangulation, and writing the result again to an output file

mainWith                          :: Options -> IO ()
mainWith (Options inFile outFile) = do
    ePage <- readSinglePageFile inFile
    case ePage of
      Left err                         -> print err
      Right (page :: IpePage Rational) -> case page^..content.traverse._IpeUse of
        []         -> putStrLn "No points found"
        syms@(_:_) -> do
           let pts  = syms&traverse.core %~ (^.symbolPoint)
               pts' = NonEmpty.fromList pts
               dt   = delaunayTriangulation $ pts'
               out  = [asIpe drawTriangulation dt]
           writeIpeFile outFile . singlePageFromContent $ out

See the examples directory for more examples.