Data.Geometry.Polygon.Convex

Documentation

newtype ConvexPolygon p r

Constructors

ConvexPolygon

Fields

• _simplePolygon :: SimplePolygon p r

Instances

PointFunctor (ConvexPolygon p)

Methods

pmap :: (Point (Dimension (ConvexPolygon p r)) r -> Point (Dimension (ConvexPolygon p s)) s) -> ConvexPolygon p r -> ConvexPolygon p s

(Eq r, Eq p) => Eq (ConvexPolygon p r)

Methods

(==) :: ConvexPolygon p r -> ConvexPolygon p r -> Bool

(/=) :: ConvexPolygon p r -> ConvexPolygon p r -> Bool

(Show r, Show p) => Show (ConvexPolygon p r)

Methods

showsPrec :: Int -> ConvexPolygon p r -> ShowS

show :: ConvexPolygon p r -> String

showList :: [ConvexPolygon p r] -> ShowS

Num r => IsTransformable (ConvexPolygon p r)

Methods

transformBy :: Transformation (Dimension (ConvexPolygon p r)) (NumType (ConvexPolygon p r)) -> ConvexPolygon p r -> ConvexPolygon p r

IsBoxable (ConvexPolygon p r)

Methods

boundingBox :: ConvexPolygon p r -> Box (Dimension (ConvexPolygon p r)) () (NumType (ConvexPolygon p r))

HasDefaultIpeOut (ConvexPolygon p r)

Associated Types

type DefaultIpeOut (ConvexPolygon p r) :: * -> *

Methods

defaultIpeOut :: IpeOut (ConvexPolygon p r) (IpeObject' (DefaultIpeOut (ConvexPolygon p r)) (NumType (ConvexPolygon p r)))

type NumType (ConvexPolygon p r)

type NumType (ConvexPolygon p r) = r

type Dimension (ConvexPolygon p r)

type Dimension (ConvexPolygon p r) = 2

type DefaultIpeOut (ConvexPolygon p r)

type DefaultIpeOut (ConvexPolygon p r) = Path

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)

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

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

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

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)

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

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

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

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 => CSeq (Point 2 r :+ p) -> CSeq (Point 2 r :+ p)

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