Safe Haskell | None |
---|---|
Language | Haskell2010 |
- delaunayTriangulation :: (Ord r, Fractional r) => NonEmpty (Point 2 r :+ p) -> Triangulation p r
- delaunayTriangulation' :: (Ord r, Fractional r) => BinLeafTree Size (Point 2 r :+ p) -> Mapping p r -> (Adj, ConvexPolygon (p :+ VertexID) r)
- firsts :: SimplePolygon (p :+ VertexID) r -> IntMap VertexID
- fromHull :: Ord r => Mapping p r -> SimplePolygon (p :+ q) r -> Adj
- merge :: (Ord r, Fractional r) => Adj -> Adj -> LineSegment 2 (p :+ VertexID) r -> LineSegment 2 (p :+ VertexID) r -> Mapping p r -> Firsts -> Adj
- type Merge p r = StateT Adj (Reader (Mapping p r, Firsts))
- type Firsts = IntMap VertexID
- moveUp :: (Ord r, Fractional r) => (VertexID, VertexID) -> VertexID -> VertexID -> Merge p r ()
- rotateR :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Merge p r (Vertex, Bool)
- rotateR' :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Vertex -> Merge p r Vertex
- rotateL :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Merge p r (Vertex, Bool)
- rotateL' :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Vertex -> Merge p r Vertex
- qTest :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Vertex -> Merge p r Bool
- insert :: (Num r, Ord r) => VertexID -> VertexID -> Merge p r ()
- rotateToFirst :: VertexID -> Firsts -> Merge p r ()
- insert' :: (Num r, Ord r) => VertexID -> VertexID -> Mapping p r -> Adj -> Adj
- delete :: VertexID -> VertexID -> Adj -> Adj
- isLeftOf :: (Ord r, Num r) => VertexID -> (VertexID, VertexID) -> Merge p r Bool
- isRightOf :: (Ord r, Num r) => VertexID -> (VertexID, VertexID) -> Merge p r Bool
- lookup' :: Ord k => Map k a -> k -> a
- size' :: BinLeafTree Size a -> Size
- rotateTo :: Eq a => a -> CList a -> CList a
- pred' :: CList a -> CList a
- succ' :: CList a -> CList a
- focus' :: CList a -> a
- nub' :: Eq a => NonEmpty (a :+ b) -> NonEmpty (a :+ b)
- withID :: (c :+ e) -> e' -> c :+ (e :+ e')
- lookup'' :: Int -> IntMap a -> a
Divide & Conqueror Delaunay Triangulation
delaunayTriangulation :: (Ord r, Fractional r) => NonEmpty (Point 2 r :+ p) -> Triangulation p r Source
Computes the delaunay triangulation of a set of points.
Running time: $O(n log n)$ (note: We use an IntMap in the implementation. So maybe actually $O(n log^2 n)$)
pre: the input is a *SET*, i.e. contains no duplicate points. (If the input does contain duplicate points, the implementation throws them away)
delaunayTriangulation' :: (Ord r, Fractional r) => BinLeafTree Size (Point 2 r :+ p) -> Mapping p r -> (Adj, ConvexPolygon (p :+ VertexID) r) Source
Implementation
firsts :: SimplePolygon (p :+ VertexID) r -> IntMap VertexID Source
Mapping that says for each vtx in the convex hull what the first entry in the adj. list should be. The input polygon is given in Clockwise order
fromHull :: Ord r => Mapping p r -> SimplePolygon (p :+ q) r -> Adj Source
Given a polygon; construct the adjacency list representation pre: at least two elements
:: (Ord r, Fractional r) | |
=> Adj | |
-> Adj | |
-> LineSegment 2 (p :+ VertexID) r | lower tangent |
-> LineSegment 2 (p :+ VertexID) r | upper tangent |
-> Mapping p r | |
-> Firsts | |
-> Adj |
Merge the two delaunay triangulations.
running time: $O(n)$ (although we cheat a bit by using a IntMap)
moveUp :: (Ord r, Fractional r) => (VertexID, VertexID) -> VertexID -> VertexID -> Merge p r () Source
Merges the two delaunay traingulations.
rotateR :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Merge p r (Vertex, Bool) Source
'rotates'
around r and removes all neighbours of r that violate the
delaunay condition. Returns the first vertex (as a Neighbour of r) that
should remain in the Delaunay Triangulation, as well as a boolean A that
helps deciding if we merge up by rotating left or rotating right (See
description in the paper for more info)
rotateR' :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Vertex -> Merge p r Vertex Source
The code that does the actual rotating
rotateL :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Merge p r (Vertex, Bool) Source
Symmetric to rotateR
rotateL' :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Vertex -> Merge p r Vertex Source
The code that does the actual rotating. Symmetric to rotateR'
Primitives used by the Algorithm
qTest :: (Ord r, Fractional r) => VertexID -> VertexID -> Vertex -> Vertex -> Merge p r Bool Source
returns True if the forth point (vertex) does not lie in the disk defined by the first three points.
insert :: (Num r, Ord r) => VertexID -> VertexID -> Merge p r () Source
Inserts an edge into the right position.
rotateToFirst :: VertexID -> Firsts -> Merge p r () Source
make sure that the first vtx in the adj list of v is its predecessor on the CH
insert' :: (Num r, Ord r) => VertexID -> VertexID -> Mapping p r -> Adj -> Adj Source
Inserts an edge (and makes sure that the vertex is inserted in the correct. pos in the adjacency lists)
isLeftOf :: (Ord r, Num r) => VertexID -> (VertexID, VertexID) -> Merge p r Bool Source
Lifted version of Convex.IsLeftOf
isRightOf :: (Ord r, Num r) => VertexID -> (VertexID, VertexID) -> Merge p r Bool Source
Lifted version of Convex.IsRightOf
Some Helper functions
size' :: BinLeafTree Size a -> Size Source
rotateTo :: Eq a => a -> CList a -> CList a Source
an unsafe
version of rotateTo that assumes the element to rotate to
occurs in the list.
pred' :: CList a -> CList a Source
Adjacency lists are stored in clockwise order, so pred means rotate right