| Copyright | (c) Frank Staals |
|---|---|
| License | See LICENCE file |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.Geometry.Polygon.Convex
Description
- type ConvexPolygon = SimplePolygon
- merge :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> (ConvexPolygon p r, LineSegment 2 p r, LineSegment 2 p r)
- lowerTangent :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> LineSegment 2 p r
- upperTangent :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> LineSegment 2 p r
- isLeftOf :: (Num r, Ord r) => (Point 2 r :+ p) -> (Point 2 r :+ p', Point 2 r :+ p'') -> Bool
- isRightOf :: (Num r, Ord r) => (Point 2 r :+ p) -> (Point 2 r :+ p', Point 2 r :+ p'') -> Bool
- extremes :: (Num r, Ord r) => Vector 2 r -> ConvexPolygon p r -> (Point 2 r :+ p, Point 2 r :+ p)
- maxInDirection :: (Num r, Ord r) => Vector 2 r -> ConvexPolygon p r -> Point 2 r :+ p
Documentation
type ConvexPolygon = SimplePolygon Source
merge :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> (ConvexPolygon p r, LineSegment 2 p r, LineSegment 2 p r) Source
Rotating Right - rotate clockwise
Merging two convex hulls, based on the paper:
Two Algorithms for Constructing a Delaunay Triangulation Lee and Schachter International Journal of Computer and Information Sciences, Vol 9, No. 3, 1980
: (combined hull, lower tangent that was added, upper tangent thtat was added)
lowerTangent :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> LineSegment 2 p r Source
Compute the lower tangent of the two polgyons
pre: - polygons lp and rp have at least 1 vertex - lp and rp are disjoint, and there is a vertical line separating the two polygons. - The vertices of the polygons are given in clockwise order
Running time: O(n+m), where n and m are the sizes of the two polygons respectively
upperTangent :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> LineSegment 2 p r Source
Compute the upper tangent of the two polgyons
pre: - polygons lp and rp have at least 1 vertex - lp and rp are disjoint, and there is a vertical line separating the two polygons. - The vertices of the polygons are given in clockwise order
Running time: O(n+m), where n and m are the sizes of the two polygons respectively
isLeftOf :: (Num r, Ord r) => (Point 2 r :+ p) -> (Point 2 r :+ p', Point 2 r :+ p'') -> Bool Source
isRightOf :: (Num r, Ord r) => (Point 2 r :+ p) -> (Point 2 r :+ p', Point 2 r :+ p'') -> Bool Source
extremes :: (Num r, Ord r) => Vector 2 r -> ConvexPolygon p r -> (Point 2 r :+ p, Point 2 r :+ p) Source
Finds the extreme points, minimum and maximum, in a given direction
pre: The input polygon is strictly convex.
running time: $O(log n)$
maxInDirection :: (Num r, Ord r) => Vector 2 r -> ConvexPolygon p r -> Point 2 r :+ p Source
Finds the extreme maximum point in the given direction. Based on http://geomalgorithms.com/a14-_extreme_pts.html
pre: The input polygon is strictly convex.
running time: $O(log^2 n)$