--------------------------------------------------------------------------------
-- |
-- Module      :  Algorithms.Geometry.PolygonTriangulation.Triangulate
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--------------------------------------------------------------------------------
module Algorithms.Geometry.PolygonTriangulation.Triangulate where


import qualified Algorithms.Geometry.PolygonTriangulation.MakeMonotone as MM
import qualified Algorithms.Geometry.PolygonTriangulation.TriangulateMonotone as TM
import           Algorithms.Geometry.PolygonTriangulation.Types
import           Control.Lens
import           Data.Either (lefts)
import           Data.Ext
import qualified Data.Foldable as F
import           Data.Geometry.LineSegment
import           Data.Geometry.PlanarSubdivision.Basic
import           Data.Geometry.Polygon

--------------------------------------------------------------------------------

-- | Triangulates a polygon of \(n\) vertices
--
-- running time: \(O(n \log n)\)
triangulate        :: (Ord r, Fractional r)
                   => proxy s -> Polygon t p r
                   -> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
triangulate :: proxy s
-> Polygon t p r
-> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
triangulate proxy s
px Polygon t p r
pg' = proxy s
-> LineSegment 2 p r
-> [LineSegment 2 p r]
-> [LineSegment 2 p r]
-> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
forall k (proxy :: k -> *) r (s :: k) p.
(Fractional r, Ord r) =>
proxy s
-> LineSegment 2 p r
-> [LineSegment 2 p r]
-> [LineSegment 2 p r]
-> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
constructSubdivision proxy s
px LineSegment 2 p r
e [LineSegment 2 p r]
es [LineSegment 2 p r]
diags
  where
    (Polygon t p r
pg, [LineSegment 2 p r]
diags)   = Polygon t p r -> (Polygon t p r, [LineSegment 2 p r])
forall r (t :: PolygonType) p.
(Ord r, Fractional r) =>
Polygon t p r -> (Polygon t p r, [LineSegment 2 p r])
computeDiagonals' Polygon t p r
pg'
    (LineSegment 2 p r
e:[LineSegment 2 p r]
es)        = Polygon t p r -> [LineSegment 2 p r]
forall (t :: PolygonType) p r. Polygon t p r -> [LineSegment 2 p r]
listEdges Polygon t p r
pg


-- | Triangulates a polygon of \(n\) vertices
--
-- running time: \(O(n \log n)\)
triangulate'        :: (Ord r, Fractional r)
                    => proxy s -> Polygon t p r
                    -> PlaneGraph s p PolygonEdgeType PolygonFaceData r
triangulate' :: proxy s
-> Polygon t p r
-> PlaneGraph s p PolygonEdgeType PolygonFaceData r
triangulate' proxy s
px Polygon t p r
pg' = proxy s
-> LineSegment 2 p r
-> [LineSegment 2 p r]
-> [LineSegment 2 p r]
-> PlaneGraph s p PolygonEdgeType PolygonFaceData r
forall k (proxy :: k -> *) r (s :: k) p.
(Fractional r, Ord r) =>
proxy s
-> LineSegment 2 p r
-> [LineSegment 2 p r]
-> [LineSegment 2 p r]
-> PlaneGraph s p PolygonEdgeType PolygonFaceData r
constructGraph proxy s
px LineSegment 2 p r
e [LineSegment 2 p r]
es [LineSegment 2 p r]
diags
  where
    (Polygon t p r
pg, [LineSegment 2 p r]
diags)   = Polygon t p r -> (Polygon t p r, [LineSegment 2 p r])
forall r (t :: PolygonType) p.
(Ord r, Fractional r) =>
Polygon t p r -> (Polygon t p r, [LineSegment 2 p r])
computeDiagonals' Polygon t p r
pg'
    (LineSegment 2 p r
e:[LineSegment 2 p r]
es)        = Polygon t p r -> [LineSegment 2 p r]
forall (t :: PolygonType) p r. Polygon t p r -> [LineSegment 2 p r]
listEdges Polygon t p r
pg


-- | Computes a set of diagaonals that together triangulate the input polygon
-- of \(n\) vertices.
--
-- running time: \(O(n \log n)\)
computeDiagonals :: (Ord r, Fractional r) => Polygon t p r -> [LineSegment 2 p r]
computeDiagonals :: Polygon t p r -> [LineSegment 2 p r]
computeDiagonals = (Polygon t p r, [LineSegment 2 p r]) -> [LineSegment 2 p r]
forall a b. (a, b) -> b
snd ((Polygon t p r, [LineSegment 2 p r]) -> [LineSegment 2 p r])
-> (Polygon t p r -> (Polygon t p r, [LineSegment 2 p r]))
-> Polygon t p r
-> [LineSegment 2 p r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Polygon t p r -> (Polygon t p r, [LineSegment 2 p r])
forall r (t :: PolygonType) p.
(Ord r, Fractional r) =>
Polygon t p r -> (Polygon t p r, [LineSegment 2 p r])
computeDiagonals'

-- | Computes a set of diagaonals that together triangulate the input polygon
-- of \(n\) vertices. Returns a copy of the input polygon, whose boundaries are
-- oriented in counter clockwise order, as well.
--
-- running time: \(O(n \log n)\)
computeDiagonals'     :: (Ord r, Fractional r)
                      => Polygon t p r -> (Polygon t p r, [LineSegment 2 p r])
computeDiagonals' :: Polygon t p r -> (Polygon t p r, [LineSegment 2 p r])
computeDiagonals' Polygon t p r
pg' = (Polygon t p r
pg, [LineSegment 2 p r]
monotoneDiags [LineSegment 2 p r] -> [LineSegment 2 p r] -> [LineSegment 2 p r]
forall a. Semigroup a => a -> a -> a
<> [LineSegment 2 p r]
extraDiags)
  where
    pg :: Polygon t p r
pg            = Polygon t p r -> Polygon t p r
forall r (t :: PolygonType) p.
(Eq r, Num r) =>
Polygon t p r -> Polygon t p r
toCounterClockWiseOrder Polygon t p r
pg'
    monotoneP :: PlanarSubdivision
  (Polygon t p r) p PolygonEdgeType PolygonFaceData r
monotoneP     = Identity (Polygon t p r)
-> Polygon t p r
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
forall k r (proxy :: k -> *) (s :: k) (t :: PolygonType) p.
(Fractional r, Ord r) =>
proxy s
-> Polygon t p r
-> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
MM.makeMonotone (Polygon t p r -> Identity (Polygon t p r)
forall a. a -> Identity a
Identity Polygon t p r
pg) Polygon t p r
pg -- use some arbitrary proxy type
    -- outerFaceId'  = outerFaceId monotoneP

    monotoneDiags :: [LineSegment 2 p r]
monotoneDiags = ((Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
 -> LineSegment 2 p r)
-> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)]
-> [LineSegment 2 p r]
forall a b. (a -> b) -> [a] -> [b]
map ((Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
-> Getting
     (LineSegment 2 p r)
     (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
     (LineSegment 2 p r)
-> LineSegment 2 p r
forall s a. s -> Getting a s a -> a
^.((LineSegment 2 p r :+ PolygonEdgeType)
 -> Const
      (LineSegment 2 p r) (LineSegment 2 p r :+ PolygonEdgeType))
-> (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
-> Const
     (LineSegment 2 p r)
     (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
forall s t a b. Field2 s t a b => Lens s t a b
_2(((LineSegment 2 p r :+ PolygonEdgeType)
  -> Const
       (LineSegment 2 p r) (LineSegment 2 p r :+ PolygonEdgeType))
 -> (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
 -> Const
      (LineSegment 2 p r)
      (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType))
-> ((LineSegment 2 p r
     -> Const (LineSegment 2 p r) (LineSegment 2 p r))
    -> (LineSegment 2 p r :+ PolygonEdgeType)
    -> Const
         (LineSegment 2 p r) (LineSegment 2 p r :+ PolygonEdgeType))
-> Getting
     (LineSegment 2 p r)
     (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
     (LineSegment 2 p r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(LineSegment 2 p r
 -> Const (LineSegment 2 p r) (LineSegment 2 p r))
-> (LineSegment 2 p r :+ PolygonEdgeType)
-> Const (LineSegment 2 p r) (LineSegment 2 p r :+ PolygonEdgeType)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core) ([(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)]
 -> [LineSegment 2 p r])
-> (PlanarSubdivision
      (Polygon t p r) p PolygonEdgeType PolygonFaceData r
    -> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)])
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [LineSegment 2 p r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
 -> Bool)
-> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)]
-> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)]
forall a. (a -> Bool) -> [a] -> [a]
filter (\(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
e' -> (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
e'(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
-> Getting
     PolygonEdgeType
     (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
     PolygonEdgeType
-> PolygonEdgeType
forall s a. s -> Getting a s a -> a
^.((LineSegment 2 p r :+ PolygonEdgeType)
 -> Const PolygonEdgeType (LineSegment 2 p r :+ PolygonEdgeType))
-> (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
-> Const
     PolygonEdgeType
     (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
forall s t a b. Field2 s t a b => Lens s t a b
_2(((LineSegment 2 p r :+ PolygonEdgeType)
  -> Const PolygonEdgeType (LineSegment 2 p r :+ PolygonEdgeType))
 -> (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
 -> Const
      PolygonEdgeType
      (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType))
-> ((PolygonEdgeType -> Const PolygonEdgeType PolygonEdgeType)
    -> (LineSegment 2 p r :+ PolygonEdgeType)
    -> Const PolygonEdgeType (LineSegment 2 p r :+ PolygonEdgeType))
-> Getting
     PolygonEdgeType
     (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
     PolygonEdgeType
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(PolygonEdgeType -> Const PolygonEdgeType PolygonEdgeType)
-> (LineSegment 2 p r :+ PolygonEdgeType)
-> Const PolygonEdgeType (LineSegment 2 p r :+ PolygonEdgeType)
forall core extra extra'.
Lens (core :+ extra) (core :+ extra') extra extra'
extra PolygonEdgeType -> PolygonEdgeType -> Bool
forall a. Eq a => a -> a -> Bool
== PolygonEdgeType
Diagonal)
                  ([(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)]
 -> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)])
-> (PlanarSubdivision
      (Polygon t p r) p PolygonEdgeType PolygonFaceData r
    -> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)])
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
-> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Vector
   (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
 -> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)])
-> (PlanarSubdivision
      (Polygon t p r) p PolygonEdgeType PolygonFaceData r
    -> Vector
         (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType))
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [(Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision
  (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> Vector
     (Dart (Polygon t p r), LineSegment 2 p r :+ PolygonEdgeType)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r
-> Vector (Dart s, LineSegment 2 v r :+ e)
edgeSegments (PlanarSubdivision
   (Polygon t p r) p PolygonEdgeType PolygonFaceData r
 -> [LineSegment 2 p r])
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [LineSegment 2 p r]
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision
  (Polygon t p r) p PolygonEdgeType PolygonFaceData r
monotoneP
    extraDiags :: [LineSegment 2 p r]
extraDiags    = (Polygon 'Simple p r -> [LineSegment 2 p r])
-> [Polygon 'Simple p r] -> [LineSegment 2 p r]
forall (t :: * -> *) a b. Foldable t => (a -> [b]) -> t a -> [b]
concatMap (Polygon 'Simple p r -> [LineSegment 2 p r]
forall r p.
(Ord r, Num r) =>
MonotonePolygon p r -> [LineSegment 2 p r]
TM.computeDiagonals (Polygon 'Simple p r -> [LineSegment 2 p r])
-> (Polygon 'Simple p r -> Polygon 'Simple p r)
-> Polygon 'Simple p r
-> [LineSegment 2 p r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Polygon 'Simple p r -> Polygon 'Simple p r
forall r (t :: PolygonType) p.
(Eq r, Num r) =>
Polygon t p r -> Polygon t p r
toCounterClockWiseOrder')
                  ([Polygon 'Simple p r] -> [LineSegment 2 p r])
-> (PlanarSubdivision
      (Polygon t p r) p PolygonEdgeType PolygonFaceData r
    -> [Polygon 'Simple p r])
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [LineSegment 2 p r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. [Either (Polygon 'Simple p r) (Polygon 'Multi p r)]
-> [Polygon 'Simple p r]
forall a b. [Either a b] -> [a]
lefts ([Either (Polygon 'Simple p r) (Polygon 'Multi p r)]
 -> [Polygon 'Simple p r])
-> (PlanarSubdivision
      (Polygon t p r) p PolygonEdgeType PolygonFaceData r
    -> [Either (Polygon 'Simple p r) (Polygon 'Multi p r)])
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [Polygon 'Simple p r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((FaceId' (Polygon t p r),
  Either (Polygon 'Simple p r) (Polygon 'Multi p r)
  :+ PolygonFaceData)
 -> Either (Polygon 'Simple p r) (Polygon 'Multi p r))
-> [(FaceId' (Polygon t p r),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
-> [Either (Polygon 'Simple p r) (Polygon 'Multi p r)]
forall a b. (a -> b) -> [a] -> [b]
map ((FaceId' (Polygon t p r),
 Either (Polygon 'Simple p r) (Polygon 'Multi p r)
 :+ PolygonFaceData)
-> Getting
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
     (FaceId' (Polygon t p r),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
-> Either (Polygon 'Simple p r) (Polygon 'Multi p r)
forall s a. s -> Getting a s a -> a
^.((Either (Polygon 'Simple p r) (Polygon 'Multi p r)
  :+ PolygonFaceData)
 -> Const
      (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
      (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
       :+ PolygonFaceData))
-> (FaceId' (Polygon t p r),
    Either (Polygon 'Simple p r) (Polygon 'Multi p r)
    :+ PolygonFaceData)
-> Const
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
     (FaceId' (Polygon t p r),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)
forall s t a b. Field2 s t a b => Lens s t a b
_2(((Either (Polygon 'Simple p r) (Polygon 'Multi p r)
   :+ PolygonFaceData)
  -> Const
       (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
       (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
        :+ PolygonFaceData))
 -> (FaceId' (Polygon t p r),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)
 -> Const
      (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
      (FaceId' (Polygon t p r),
       Either (Polygon 'Simple p r) (Polygon 'Multi p r)
       :+ PolygonFaceData))
-> ((Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     -> Const
          (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
          (Either (Polygon 'Simple p r) (Polygon 'Multi p r)))
    -> (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
        :+ PolygonFaceData)
    -> Const
         (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
         (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
          :+ PolygonFaceData))
-> Getting
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
     (FaceId' (Polygon t p r),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Either (Polygon 'Simple p r) (Polygon 'Multi p r)
 -> Const
      (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
      (Either (Polygon 'Simple p r) (Polygon 'Multi p r)))
-> (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
    :+ PolygonFaceData)
-> Const
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)
forall core extra core'.
Lens (core :+ extra) (core' :+ extra) core core'
core)
                  ([(FaceId' (Polygon t p r),
   Either (Polygon 'Simple p r) (Polygon 'Multi p r)
   :+ PolygonFaceData)]
 -> [Either (Polygon 'Simple p r) (Polygon 'Multi p r)])
-> (PlanarSubdivision
      (Polygon t p r) p PolygonEdgeType PolygonFaceData r
    -> [(FaceId' (Polygon t p r),
         Either (Polygon 'Simple p r) (Polygon 'Multi p r)
         :+ PolygonFaceData)])
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [Either (Polygon 'Simple p r) (Polygon 'Multi p r)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((FaceId' (Polygon t p r),
  Either (Polygon 'Simple p r) (Polygon 'Multi p r)
  :+ PolygonFaceData)
 -> Bool)
-> [(FaceId' (Polygon t p r),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
-> [(FaceId' (Polygon t p r),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
forall a. (a -> Bool) -> [a] -> [a]
filter (\(FaceId' (Polygon t p r),
 Either (Polygon 'Simple p r) (Polygon 'Multi p r)
 :+ PolygonFaceData)
mp -> (FaceId' (Polygon t p r),
 Either (Polygon 'Simple p r) (Polygon 'Multi p r)
 :+ PolygonFaceData)
mp(FaceId' (Polygon t p r),
 Either (Polygon 'Simple p r) (Polygon 'Multi p r)
 :+ PolygonFaceData)
-> Getting
     PolygonFaceData
     (FaceId' (Polygon t p r),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)
     PolygonFaceData
-> PolygonFaceData
forall s a. s -> Getting a s a -> a
^.((Either (Polygon 'Simple p r) (Polygon 'Multi p r)
  :+ PolygonFaceData)
 -> Const
      PolygonFaceData
      (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
       :+ PolygonFaceData))
-> (FaceId' (Polygon t p r),
    Either (Polygon 'Simple p r) (Polygon 'Multi p r)
    :+ PolygonFaceData)
-> Const
     PolygonFaceData
     (FaceId' (Polygon t p r),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)
forall s t a b. Field2 s t a b => Lens s t a b
_2(((Either (Polygon 'Simple p r) (Polygon 'Multi p r)
   :+ PolygonFaceData)
  -> Const
       PolygonFaceData
       (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
        :+ PolygonFaceData))
 -> (FaceId' (Polygon t p r),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)
 -> Const
      PolygonFaceData
      (FaceId' (Polygon t p r),
       Either (Polygon 'Simple p r) (Polygon 'Multi p r)
       :+ PolygonFaceData))
-> ((PolygonFaceData -> Const PolygonFaceData PolygonFaceData)
    -> (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
        :+ PolygonFaceData)
    -> Const
         PolygonFaceData
         (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
          :+ PolygonFaceData))
-> Getting
     PolygonFaceData
     (FaceId' (Polygon t p r),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)
     PolygonFaceData
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(PolygonFaceData -> Const PolygonFaceData PolygonFaceData)
-> (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
    :+ PolygonFaceData)
-> Const
     PolygonFaceData
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)
forall core extra extra'.
Lens (core :+ extra) (core :+ extra') extra extra'
extra PolygonFaceData -> PolygonFaceData -> Bool
forall a. Eq a => a -> a -> Bool
== PolygonFaceData
Inside) -- triangulate only the insides
                  -- . filter (\f -> f^._1 /= outerFaceId')
                  ([(FaceId' (Polygon t p r),
   Either (Polygon 'Simple p r) (Polygon 'Multi p r)
   :+ PolygonFaceData)]
 -> [(FaceId' (Polygon t p r),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)])
-> (PlanarSubdivision
      (Polygon t p r) p PolygonEdgeType PolygonFaceData r
    -> [(FaceId' (Polygon t p r),
         Either (Polygon 'Simple p r) (Polygon 'Multi p r)
         :+ PolygonFaceData)])
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [(FaceId' (Polygon t p r),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector
  (FaceId' (Polygon t p r),
   Either (Polygon 'Simple p r) (Polygon 'Multi p r)
   :+ PolygonFaceData)
-> [(FaceId' (Polygon t p r),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Vector
   (FaceId' (Polygon t p r),
    Either (Polygon 'Simple p r) (Polygon 'Multi p r)
    :+ PolygonFaceData)
 -> [(FaceId' (Polygon t p r),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)])
-> (PlanarSubdivision
      (Polygon t p r) p PolygonEdgeType PolygonFaceData r
    -> Vector
         (FaceId' (Polygon t p r),
          Either (Polygon 'Simple p r) (Polygon 'Multi p r)
          :+ PolygonFaceData))
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [(FaceId' (Polygon t p r),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision
  (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> Vector
     (FaceId' (Polygon t p r),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)
forall k (s :: k) v e f r.
PlanarSubdivision s v e f r
-> Vector (FaceId' s, SomePolygon v r :+ f)
rawFacePolygons (PlanarSubdivision
   (Polygon t p r) p PolygonEdgeType PolygonFaceData r
 -> [LineSegment 2 p r])
-> PlanarSubdivision
     (Polygon t p r) p PolygonEdgeType PolygonFaceData r
-> [LineSegment 2 p r]
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision
  (Polygon t p r) p PolygonEdgeType PolygonFaceData r
monotoneP

    -- -- we alredy know we get the polgyons in *clockwise* order, so skip the
    -- -- check if it is counter clockwise
    -- toCounterClockWiseOrder'' = reverseOuterBoundary