Copyright	(c) Frank Staals
License	See LICENCE file
Safe Haskell	None
Language	Haskell2010

Data.Geometry.Polygon

Contents

Polygons
Functions on Polygons

Description

Synopsis

data PolygonType
- = Simple
- | Multi
data Polygon (t :: PolygonType) p r where
- SimplePolygon :: CSeq (Point 2 r :+ p) -> Polygon Simple p r
- MultiPolygon :: CSeq (Point 2 r :+ p) -> [Polygon Simple p r] -> Polygon Multi p r
bitraverseVertices :: (Applicative f, Traversable t) => (p -> f q) -> (r -> f s) -> t (Point 2 r :+ p) -> f (t (Point 2 s :+ q))
type SimplePolygon = Polygon Simple
type MultiPolygon = Polygon Multi
type SomePolygon p r = Either (Polygon Simple p r) (Polygon Multi p r)
outerBoundary :: forall t p r. Lens' (Polygon t p r) (CSeq (Point 2 r :+ p))
polygonHoles :: forall p r. Lens' (Polygon Multi p r) [Polygon Simple p r]
outerVertex :: Int -> Lens' (Polygon t p r) (Point 2 r :+ p)
outerBoundaryEdge :: Int -> Polygon t p r -> LineSegment 2 p r
holeList :: Polygon t p r -> [Polygon Simple p r]
polygonVertices :: Polygon t p r -> NonEmpty (Point 2 r :+ p)
fromPoints :: [Point 2 r :+ p] -> SimplePolygon p r
outerBoundaryEdges :: Polygon t p r -> CSeq (LineSegment 2 p r)
listEdges :: Polygon t p r -> [LineSegment 2 p r]
withIncidentEdges :: Polygon t p r -> Polygon t (Two (LineSegment 2 p r)) r
toEdges :: CSeq (Point 2 r :+ p) -> CSeq (LineSegment 2 p r)
onBoundary :: (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> Bool
inPolygon :: forall t p r. (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> PointLocationResult
insidePolygon :: (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> Bool
area :: Fractional r => Polygon t p r -> r
signedArea :: Fractional r => SimplePolygon p r -> r
centroid :: Fractional r => SimplePolygon p r -> Point 2 r
isCounterClockwise :: (Eq r, Fractional r) => Polygon t p r -> Bool
toClockwiseOrder :: (Eq r, Fractional r) => Polygon t p r -> Polygon t p r
toCounterClockWiseOrder :: (Eq r, Fractional r) => Polygon t p r -> Polygon t p r
reverseOuterBoundary :: Polygon t p r -> Polygon t p r
asSimplePolygon :: Polygon t p r -> SimplePolygon p r
cmpExtreme :: (Num r, Ord r) => Vector 2 r -> (Point 2 r :+ p) -> (Point 2 r :+ q) -> Ordering
extremesLinear :: (Ord r, Num r) => Vector 2 r -> Polygon t p r -> (Point 2 r :+ p, Point 2 r :+ p)
numberVertices :: Polygon t p r -> Polygon t (SP Int p) r

Polygons

>>> :{
let simplePoly :: SimplePolygon () Rational
    simplePoly = SimplePolygon . C.fromList . map ext $ [ point2 0 0
                                                        , point2 10 0
                                                        , point2 10 10
                                                        , point2 5 15
                                                        , point2 1 11
                                                        ]
:}

data PolygonType Source #

We distinguish between simple polygons (without holes) and Polygons with holes.

Constructors

Simple
Multi

data Polygon (t :: PolygonType) p r where Source #

Constructors

SimplePolygon :: CSeq (Point 2 r :+ p) -> Polygon Simple p r
MultiPolygon :: CSeq (Point 2 r :+ p) -> [Polygon Simple p r] -> Polygon Multi p r

Instances

Bitraversable (Polygon t) Source #
Instance details Defined in Data.Geometry.Polygon Methods bitraverse :: Applicative f => (a -> f c) -> (b -> f d) -> Polygon t a b -> f (Polygon t c d) #
Bifoldable (Polygon t) Source #
Instance details Defined in Data.Geometry.Polygon Methods bifold :: Monoid m => Polygon t m m -> m # bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> Polygon t a b -> m # bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> Polygon t a b -> c # bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> Polygon t a b -> c #
Bifunctor (Polygon t) Source #
Instance details Defined in Data.Geometry.Polygon Methods bimap :: (a -> b) -> (c -> d) -> Polygon t a c -> Polygon t b d # first :: (a -> b) -> Polygon t a c -> Polygon t b c # second :: (b -> c) -> Polygon t a b -> Polygon t a c #
PointFunctor (Polygon t p) Source #
Instance details Defined in Data.Geometry.Polygon Methods pmap :: (Point (Dimension (Polygon t p r)) r -> Point (Dimension (Polygon t p s)) s) -> Polygon t p r -> Polygon t p s Source #
HasDefaultFromIpe (MultiPolygon () r) Source #
Instance details Defined in Data.Geometry.Ipe.FromIpe Associated Types type DefaultFromIpe (MultiPolygon () r) :: * -> * Source # Methods defaultFromIpe :: r0 ~ NumType (MultiPolygon () r) => Prism' (IpeObject r0) (MultiPolygon () r :+ IpeAttributes (DefaultFromIpe (MultiPolygon () r)) r0) Source #
HasDefaultFromIpe (SimplePolygon () r) Source #
Instance details Defined in Data.Geometry.Ipe.FromIpe Associated Types type DefaultFromIpe (SimplePolygon () r) :: * -> * Source # Methods defaultFromIpe :: r0 ~ NumType (SimplePolygon () r) => Prism' (IpeObject r0) (SimplePolygon () r :+ IpeAttributes (DefaultFromIpe (SimplePolygon () r)) r0) Source #
HasDefaultIpeOut (SomePolygon p r) Source #
Instance details Defined in Data.Geometry.Ipe.IpeOut Associated Types type DefaultIpeOut (SomePolygon p r) :: * -> * Source # Methods defaultIpeOut :: IpeOut (SomePolygon p r) (IpeObject' (DefaultIpeOut (SomePolygon p r)) (NumType (SomePolygon p r))) Source #
(Eq p, Eq r) => Eq (Polygon t p r) Source #
Instance details Defined in Data.Geometry.Polygon Methods (==) :: Polygon t p r -> Polygon t p r -> Bool # (/=) :: Polygon t p r -> Polygon t p r -> Bool #
(Show p, Show r) => Show (Polygon t p r) Source #
Instance details Defined in Data.Geometry.Polygon Methods showsPrec :: Int -> Polygon t p r -> ShowS # show :: Polygon t p r -> String # showList :: [Polygon t p r] -> ShowS #
(NFData p, NFData r) => NFData (Polygon t p r) Source #
Instance details Defined in Data.Geometry.Polygon Methods rnf :: Polygon t p r -> () #
Fractional r => IsTransformable (Polygon t p r) Source #
Instance details Defined in Data.Geometry.Polygon Methods transformBy :: Transformation (Dimension (Polygon t p r)) (NumType (Polygon t p r)) -> Polygon t p r -> Polygon t p r Source #
IsBoxable (Polygon t p r) Source #
Instance details Defined in Data.Geometry.Polygon Methods boundingBox :: Polygon t p r -> Box (Dimension (Polygon t p r)) () (NumType (Polygon t p r)) Source #
IpeWriteText r => IpeWriteText (Polygon t () r) Source #
Instance details Defined in Data.Geometry.Ipe.Writer Methods ipeWriteText :: Polygon t () r -> Maybe Text Source #
HasDefaultIpeOut (Polygon t p r) Source #
Instance details Defined in Data.Geometry.Ipe.IpeOut Associated Types type DefaultIpeOut (Polygon t p r) :: * -> * Source # Methods defaultIpeOut :: IpeOut (Polygon t p r) (IpeObject' (DefaultIpeOut (Polygon t p r)) (NumType (Polygon t p r))) Source #
type NumType (SomePolygon p r) Source #
Instance details Defined in Data.Geometry.Polygon type NumType (SomePolygon p r) = r
type Dimension (SomePolygon p r) Source #
Instance details Defined in Data.Geometry.Polygon type Dimension (SomePolygon p r) = 2
type DefaultFromIpe (MultiPolygon () r) Source #
Instance details Defined in Data.Geometry.Ipe.FromIpe type DefaultFromIpe (MultiPolygon () r) = Path
type DefaultFromIpe (SimplePolygon () r) Source #
Instance details Defined in Data.Geometry.Ipe.FromIpe type DefaultFromIpe (SimplePolygon () r) = Path
type DefaultIpeOut (SomePolygon p r) Source #
Instance details Defined in Data.Geometry.Ipe.IpeOut type DefaultIpeOut (SomePolygon p r) = Path
type IntersectionOf (Line 2 r) (Boundary (Polygon t p r)) Source #
Instance details Defined in Data.Geometry.Polygon type IntersectionOf (Line 2 r) (Boundary (Polygon t p r)) = Seq (Either (Point 2 r) (LineSegment 2 () r)) ': ([] :: [*])
type NumType (Polygon t p r) Source #
Instance details Defined in Data.Geometry.Polygon type NumType (Polygon t p r) = r
type Dimension (Polygon t p r) Source #
Instance details Defined in Data.Geometry.Polygon type Dimension (Polygon t p r) = 2
type DefaultIpeOut (Polygon t p r) Source #
Instance details Defined in Data.Geometry.Ipe.IpeOut type DefaultIpeOut (Polygon t p r) = Path

bitraverseVertices :: (Applicative f, Traversable t) => (p -> f q) -> (r -> f s) -> t (Point 2 r :+ p) -> f (t (Point 2 s :+ q)) Source #

type SimplePolygon = Polygon Simple Source #

type MultiPolygon = Polygon Multi Source #

type SomePolygon p r = Either (Polygon Simple p r) (Polygon Multi p r) Source #

Either a simple or multipolygon

Functions on Polygons

outerBoundary :: forall t p r. Lens' (Polygon t p r) (CSeq (Point 2 r :+ p)) Source #

polygonHoles :: forall p r. Lens' (Polygon Multi p r) [Polygon Simple p r] Source #

outerVertex :: Int -> Lens' (Polygon t p r) (Point 2 r :+ p) Source #

Access the i^th vertex on the outer boundary

outerBoundaryEdge :: Int -> Polygon t p r -> LineSegment 2 p r Source #

holeList :: Polygon t p r -> [Polygon Simple p r] Source #

Get all holes in a polygon

polygonVertices :: Polygon t p r -> NonEmpty (Point 2 r :+ p) Source #

The vertices in the polygon. No guarantees are given on the order in which they appear!

fromPoints :: [Point 2 r :+ p] -> SimplePolygon p r Source #

Creates a simple polygon from the given list of vertices.

pre: the input list constains no repeated vertices.

outerBoundaryEdges :: Polygon t p r -> CSeq (LineSegment 2 p r) Source #

The edges along the outer boundary of the polygon. The edges are half open.

running time: \(O(n)\)

listEdges :: Polygon t p r -> [LineSegment 2 p r] Source #

Lists all edges. The edges on the outer boundary are given before the ones on the holes. However, no other guarantees are given on the order.

running time: \(O(n)\)

withIncidentEdges :: Polygon t p r -> Polygon t (Two (LineSegment 2 p r)) r Source #

Pairs every vertex with its incident edges. The first one is its predecessor edge, the second one its successor edge.

>>> mapM_ print . polygonVertices $ withIncidentEdges simplePoly
Point2 [0 % 1,0 % 1] :+ SP LineSegment (Closed (Point2 [1 % 1,11 % 1] :+ ())) (Closed (Point2 [0 % 1,0 % 1] :+ ())) LineSegment (Closed (Point2 [0 % 1,0 % 1] :+ ())) (Closed (Point2 [10 % 1,0 % 1] :+ ()))
Point2 [10 % 1,0 % 1] :+ SP LineSegment (Closed (Point2 [0 % 1,0 % 1] :+ ())) (Closed (Point2 [10 % 1,0 % 1] :+ ())) LineSegment (Closed (Point2 [10 % 1,0 % 1] :+ ())) (Closed (Point2 [10 % 1,10 % 1] :+ ()))
Point2 [10 % 1,10 % 1] :+ SP LineSegment (Closed (Point2 [10 % 1,0 % 1] :+ ())) (Closed (Point2 [10 % 1,10 % 1] :+ ())) LineSegment (Closed (Point2 [10 % 1,10 % 1] :+ ())) (Closed (Point2 [5 % 1,15 % 1] :+ ()))
Point2 [5 % 1,15 % 1] :+ SP LineSegment (Closed (Point2 [10 % 1,10 % 1] :+ ())) (Closed (Point2 [5 % 1,15 % 1] :+ ())) LineSegment (Closed (Point2 [5 % 1,15 % 1] :+ ())) (Closed (Point2 [1 % 1,11 % 1] :+ ()))
Point2 [1 % 1,11 % 1] :+ SP LineSegment (Closed (Point2 [5 % 1,15 % 1] :+ ())) (Closed (Point2 [1 % 1,11 % 1] :+ ())) LineSegment (Closed (Point2 [1 % 1,11 % 1] :+ ())) (Closed (Point2 [0 % 1,0 % 1] :+ ()))

toEdges :: CSeq (Point 2 r :+ p) -> CSeq (LineSegment 2 p r) Source #

Given the vertices of the polygon. Produce a list of edges. The edges are half-open.

onBoundary :: (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> Bool Source #

Test if q lies on the boundary of the polygon. Running time: O(n)

>>> point2 1 1 `onBoundary` simplePoly
False
>>> point2 0 0 `onBoundary` simplePoly
True
>>> point2 10 0 `onBoundary` simplePoly
True
>>> point2 5 13 `onBoundary` simplePoly
False
>>> point2 5 10 `onBoundary` simplePoly
False
>>> point2 10 5 `onBoundary` simplePoly
True
>>> point2 20 5 `onBoundary` simplePoly
False

TODO: testcases multipolygon

inPolygon :: forall t p r. (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> PointLocationResult Source #

Check if a point lies inside a polygon, on the boundary, or outside of the polygon. Running time: O(n).

>>> point2 1 1 `inPolygon` simplePoly
Inside
>>> point2 0 0 `inPolygon` simplePoly
OnBoundary
>>> point2 10 0 `inPolygon` simplePoly
OnBoundary
>>> point2 5 13 `inPolygon` simplePoly
Inside
>>> point2 5 10 `inPolygon` simplePoly
Inside
>>> point2 10 5 `inPolygon` simplePoly
OnBoundary
>>> point2 20 5 `inPolygon` simplePoly
Outside

TODO: Add some testcases with multiPolygons TODO: Add some more onBoundary testcases

insidePolygon :: (Fractional r, Ord r) => Point 2 r -> Polygon t p r -> Bool Source #

Test if a point lies strictly inside the polgyon.

area :: Fractional r => Polygon t p r -> r Source #

Compute the area of a polygon

signedArea :: Fractional r => SimplePolygon p r -> r Source #

Compute the signed area of a simple polygon. The the vertices are in clockwise order, the signed area will be negative, if the verices are given in counter clockwise order, the area will be positive.

centroid :: Fractional r => SimplePolygon p r -> Point 2 r Source #

Compute the centroid of a simple polygon.

isCounterClockwise :: (Eq r, Fractional r) => Polygon t p r -> Bool Source #

Test if the outer boundary of the polygon is in clockwise or counter clockwise order.

running time: \(O(n)\)

toClockwiseOrder :: (Eq r, Fractional r) => Polygon t p r -> Polygon t p r Source #

Orient the outer boundary to clockwise order

toCounterClockWiseOrder :: (Eq r, Fractional r) => Polygon t p r -> Polygon t p r Source #

Orient the outer boundary to counter clockwise order

reverseOuterBoundary :: Polygon t p r -> Polygon t p r Source #

asSimplePolygon :: Polygon t p r -> SimplePolygon p r Source #

Convert a Polygon to a simple polygon by forgetting about any holes.

cmpExtreme :: (Num r, Ord r) => Vector 2 r -> (Point 2 r :+ p) -> (Point 2 r :+ q) -> Ordering Source #

Comparison that compares which point is larger in the direction given by the vector u.

extremesLinear :: (Ord r, Num r) => Vector 2 r -> Polygon t p r -> (Point 2 r :+ p, Point 2 r :+ p) Source #

Finds the extreme points, minimum and maximum, in a given direction

running time: \(O(n)\)

numberVertices :: Polygon t p r -> Polygon t (SP Int p) r Source #

assigns unique integer numbers to all vertices. Numbers start from 0, and are increasing along the outer boundary. The vertices of holes will be numbered last, in the same order.

>>> numberVertices simplePoly
SimplePolygon CSeq [Point2 [0 % 1,0 % 1] :+ SP 0 (),Point2 [10 % 1,0 % 1] :+ SP 1 (),Point2 [10 % 1,10 % 1] :+ SP 2 (),Point2 [5 % 1,15 % 1] :+ SP 3 (),Point2 [1 % 1,11 % 1] :+ SP 4 ()]