| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Data.Geometry.Polygon.Convex
Description
Convex Polygons
Synopsis
- newtype ConvexPolygon p r = ConvexPolygon {
- _simplePolygon :: SimplePolygon p r
- simplePolygon :: forall p r p r. Iso (ConvexPolygon p r) (ConvexPolygon p r) (SimplePolygon p r) (SimplePolygon p r)
- 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
- lowerTangent' :: (Ord r, Num r, Foldable1 f) => f (Point 2 r :+ p) -> f (Point 2 r :+ p) -> Two ((Point 2 r :+ p) :+ [Point 2 r :+ p])
- upperTangent :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> LineSegment 2 p r
- upperTangent' :: (Ord r, Num r, Foldable1 f) => f (Point 2 r :+ p) -> f (Point 2 r :+ p) -> Two ((Point 2 r :+ p) :+ [Point 2 r :+ p])
- 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
- leftTangent :: (Ord r, Num r) => ConvexPolygon p r -> Point 2 r -> Point 2 r :+ p
- rightTangent :: (Ord r, Num r) => ConvexPolygon p r -> Point 2 r -> Point 2 r :+ p
- minkowskiSum :: (Ord r, Num r) => ConvexPolygon p r -> ConvexPolygon q r -> ConvexPolygon (p, q) r
- bottomMost :: Ord r => CSeq (Point 2 r :+ p) -> CSeq (Point 2 r :+ p)
Documentation
newtype ConvexPolygon p r Source #
Data Type representing a convex polygon
Constructors
| ConvexPolygon | |
Fields
| |
Instances
simplePolygon :: forall p r p r. Iso (ConvexPolygon p r) (ConvexPolygon p r) (SimplePolygon p r) (SimplePolygon p r) 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
lowerTangent' :: (Ord r, Num r, Foldable1 f) => f (Point 2 r :+ p) -> f (Point 2 r :+ p) -> Two ((Point 2 r :+ p) :+ [Point 2 r :+ p]) Source #
Compute the lower tangent of the two convex chains lp and rp
pre: - the chains lp and rp have at least 1 vertex - lp and rp are disjoint, and there is a vertical line having lp on the left and rp on the right. - The vertices in the left-chain are given in clockwise order, (right to left) - The vertices in the right chain are given in counterclockwise order (left-to-right)
The result returned is the two endpoints l and r of the tangents, and the remainders lc and rc of the chains (i.e.) such that the lower hull of both chains is: (reverse lc) ++ [l,h] ++ rc
Running time: \(O(n+m)\), where n and m are the sizes of the two chains 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
upperTangent' :: (Ord r, Num r, Foldable1 f) => f (Point 2 r :+ p) -> f (Point 2 r :+ p) -> Two ((Point 2 r :+ p) :+ [Point 2 r :+ p]) Source #
Compute the upper tangent of the two convex chains lp and rp
pre: - the chains lp and rp have at least 1 vertex - lp and rp are disjoint, and there is a vertical line having lp on the left and rp on the right. - The vertices in the left-chain are given in clockwise order, (right to left) - The vertices in the right chain are given in counterclockwise order (left-to-right)
The result returned is the two endpoints l and r of the tangents, and the remainders lc and rc of the chains (i.e.) such that the upper hull of both chains is: (reverse lc) ++ [l,h] ++ rc
Running time: \(O(n+m)\), where n and m are the sizes of the two chains respectively
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)\)
leftTangent :: (Ord r, Num r) => ConvexPolygon p r -> Point 2 r -> Point 2 r :+ p Source #
rightTangent :: (Ord r, Num r) => ConvexPolygon p r -> Point 2 r -> Point 2 r :+ p Source #
minkowskiSum :: (Ord r, Num r) => ConvexPolygon p r -> ConvexPolygon q r -> ConvexPolygon (p, q) r Source #
Computes the Minkowski sum of the two input polygons with $n$ and $m$ vertices respectively.
pre: input polygons are in CCW order.
running time: \(O(n+m)\).