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 :: Iso (ConvexPolygon p1 r1) (ConvexPolygon p2 r2) (SimplePolygon p1 r1) (SimplePolygon p2 r2)
convexPolygon :: forall t p r. (Ord r, Num r, Show r, Show p) => Polygon t p r -> ConvexPolygon p r
isConvex :: (Ord r, Num r) => SimplePolygon p r -> Bool
verifyConvex :: (Ord r, Num r) => ConvexPolygon p r -> Bool
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 => CircularVector (Point 2 r :+ p) -> CircularVector (Point 2 r :+ p)
inConvex :: forall p r. (Fractional r, Ord r) => Point 2 r -> ConvexPolygon p r -> PointLocationResult
randomConvex :: RandomGen g => Int -> Int -> Rand g (ConvexPolygon () Rational)
diameter :: (Ord r, Floating r) => ConvexPolygon p r -> r
diametralPair :: (Ord r, Num r) => ConvexPolygon p r -> (Point 2 r :+ p, Point 2 r :+ p)
diametralIndexPair :: (Ord r, Num r) => ConvexPolygon p r -> (Int, Int)

Documentation

newtype ConvexPolygon p r Source #

Data Type representing a convex polygon

Constructors

ConvexPolygon
Fields _simplePolygon :: SimplePolygon p r

Instances

Instances details

PointFunctor (ConvexPolygon p) Source #
Instance details Defined in Data.Geometry.Polygon.Convex Methods pmap :: (Point (Dimension (ConvexPolygon p r)) r -> Point (Dimension (ConvexPolygon p s)) s) -> ConvexPolygon p r -> ConvexPolygon p s Source #
(Eq p, Eq r) => Eq (ConvexPolygon p r) Source #
Instance details Defined in Data.Geometry.Polygon.Convex Methods (==) :: ConvexPolygon p r -> ConvexPolygon p r -> Bool # (/=) :: ConvexPolygon p r -> ConvexPolygon p r -> Bool #
(Show p, Show r) => Show (ConvexPolygon p r) Source #
Instance details Defined in Data.Geometry.Polygon.Convex Methods showsPrec :: Int -> ConvexPolygon p r -> ShowS # show :: ConvexPolygon p r -> String # showList :: [ConvexPolygon p r] -> ShowS #
(NFData p, NFData r) => NFData (ConvexPolygon p r) Source #
Instance details Defined in Data.Geometry.Polygon.Convex Methods rnf :: ConvexPolygon p r -> () #
Fractional r => IsTransformable (ConvexPolygon p r) Source #
Instance details Defined in Data.Geometry.Polygon.Convex Methods transformBy :: Transformation (Dimension (ConvexPolygon p r)) (NumType (ConvexPolygon p r)) -> ConvexPolygon p r -> ConvexPolygon p r Source #
IsBoxable (ConvexPolygon p r) Source #
Instance details Defined in Data.Geometry.Polygon.Convex Methods boundingBox :: ConvexPolygon p r -> Box (Dimension (ConvexPolygon p r)) () (NumType (ConvexPolygon p r)) Source #
type NumType (ConvexPolygon p r) Source #
Instance details Defined in Data.Geometry.Polygon.Convex type NumType (ConvexPolygon p r) = r
type Dimension (ConvexPolygon p r) Source #	Polygons are per definition 2 dimensional
Instance details Defined in Data.Geometry.Polygon.Convex type Dimension (ConvexPolygon p r) = 2

simplePolygon :: Iso (ConvexPolygon p1 r1) (ConvexPolygon p2 r2) (SimplePolygon p1 r1) (SimplePolygon p2 r2) Source #

ConvexPolygons are isomorphic to SimplePolygons with the added constraint that they have no reflex vertices.

convexPolygon :: forall t p r. (Ord r, Num r, Show r, Show p) => Polygon t p r -> ConvexPolygon p r Source #

$ O(n) $ Convex hull of a simple polygon.

For algorithmic details see: https://en.wikipedia.org/wiki/Convex_hull_of_a_simple_polygon

isConvex :: (Ord r, Num r) => SimplePolygon p r -> Bool Source #

$ O(n) $ Check if a polygon is strictly convex.

verifyConvex :: (Ord r, Num r) => ConvexPolygon p r -> Bool Source #

$ O(n) $ Verify that a convex polygon is strictly convex.

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 n)$

leftTangent :: (Ord r, Num r) => ConvexPolygon p r -> Point 2 r -> Point 2 r :+ p Source #

Given a convex polygon poly, and a point outside the polygon, find the left tangent of q and the polygon, i.e. the vertex v of the convex polygon s.t. the polygon lies completely to the right of the line from q to v.

running time: $O(\log n)$.

rightTangent :: (Ord r, Num r) => ConvexPolygon p r -> Point 2 r -> Point 2 r :+ p Source #

Given a convex polygon poly, and a point outside the polygon, find the right tangent of q and the polygon, i.e. the vertex v of the convex polygon s.t. the polygon lies completely to the left of the line from q to v.

running time: $O(\log n)$.

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)$.

bottomMost :: Ord r => CircularVector (Point 2 r :+ p) -> CircularVector (Point 2 r :+ p) Source #

Rotate to the bottommost point (and leftmost in case of ties)

inConvex :: forall p r. (Fractional r, Ord r) => Point 2 r -> ConvexPolygon p r -> PointLocationResult Source #

$ O(\log n) $ Check if a point lies inside a convex polygon, on the boundary, or outside of the convex polygon.

randomConvex :: RandomGen g => Int -> Int -> Rand g (ConvexPolygon () Rational) Source #

$ O(n \log n) $ Generate a uniformly random ConvexPolygon with N vertices and a granularity of vMax.

diameter :: (Ord r, Floating r) => ConvexPolygon p r -> r Source #

$ O(n) $ Computes the Euclidean diameter by scanning antipodal pairs.

diametralPair :: (Ord r, Num r) => ConvexPolygon p r -> (Point 2 r :+ p, Point 2 r :+ p) Source #

$ O(n) $ Computes the Euclidean diametral pair by scanning antipodal pairs.

diametralIndexPair :: (Ord r, Num r) => ConvexPolygon p r -> (Int, Int) Source #

$ O(n) $ Computes the Euclidean diametral pair by scanning antipodal pairs.