HGeometry is a library for computing with geometric objects such as points, line segments, and polygons, in Haskell. It defines basic geometric types and primitive operations on these types (for example functions to test or compute the intersection of two line segments), and it implements some geometric data structures and algorithms. The main two focusses are:
Please note that first aspect --implementing good algorithms and data structures-- is much of a work in progress. Only a few algorithms have been implemented, and most likely they can use some improvements.
HGeometry currently consists of three packages:
hgeometry-combinatorial,
which defines the non-geometric (i.e. combinatorial) data types, data structures, and algorithms.
hgeometry,
which defines the actual geometric algorithms and data structures, and
hgeometry-examples
which defines some examples that showcase using hgeometry.
The hgeometry package itself actually consists of several libraries:
hgeometry
The main library that defines the actual algorithms and data structures.
hgeometry:vector
Defines length annotated Vector types and typeclasses. The hgeometry-point library depends on this.
hgeometry:point
Defines types and typeclasses representing points in space, and basic operations on points.
hgeometry:kernel
Defines other geometric "constant complexity" geometric types and primitives. For example lines, halfspaces, line segments, balls, circles, rectangles etc.
hgeometry:ipe
Defines functions for reading, writing, and manipulating ipe files and the geometric objects therein.
hgeometry:svg
Defines functions for writing the geometry types to svg files.
The hgeometry-examples provides some examples of using the library.
This is a brief overview of some of the main available algorithms in HGeometry. Refer to the haddocks for more details. HGeometry contains algorithms for computing
the convex hull of $n$ points in $\mathbb{R}^2$. In particular,
Furtheremore, an optimal linear time algorithm for when the points are the vertices of a convex polygon.
the closest pair among $n$ points in $\mathbb{R}^2$
the intersections among a set of $n$ line segments in $\mathbb{R}^2$.
the Minkowski sum of two convex polygons. The algorithm runs in optimal $O(n+m)$ time, where $n$ and $m$ are the sizes of the polygons.
if a point lies in a polygon. In particular,
tangents and extremal points in a polygon In particular,
a simplification of a polyline. In particular, an implementation of
HGeometry also contains an implementation of some geometric data structures. In particular,
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 most algorithms it is sufficient if the type r
is
Fractional
. Hence, you can use an exact number type such as
Data.Ratio.Rational
or HGeometry.Number.Real.Rational
(which is
essentially just a Rational
with a friendlier Show
instance).
Interval Arithmetic (to speed up our computations) is one of the things on the main things on the TODO list.
In many applications we do not just have geometric data, e.g. Point d r
s or Polygon r
s, but instead, these types have some additional
properties, like a color, size, thickness, elevation, or whatever. We
use typeclasses to make sure it is easy to use the functions with
custom geometric types that store such additional fields. For example,
the 2d convex hull algorithms have type:
convexHull :: (Ord r, Num r, Point_ point 2 r) => NonEmpty point -> ConvexPolygon point
In many cases you may not want to explicitly declare a new specific
point type, but just "attach" an additional value (e.g. a color) to a
point. You may want to use the Ext
type (typically seen as (:+)
from Heometry.Ext
in such cases.
HGeometry heavily relies on typeclasses to support polymorphic
inputs. Therefore, if you are using this package, it is recommended to
compile your package with GHC options -fspecialise-aggressively -fexpose-all-unfoldings
to make sure GHC sufficiently specializes the
calls. You can do so by adding the following to your
executable/library stanza in your cabal file:
ghc-options: -fspecialise-aggressively -fexpose-all-unfoldings
Not doing so may significantly impact the performance of your compiled code.