--------------------------------------------------------------------------------
-- |
-- 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     :: forall s t p r. (Ord r, Fractional r)
                => Polygon t p r -> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
triangulate :: Polygon t p r
-> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
triangulate Polygon t p r
pg' = LineSegment 2 p r
-> [LineSegment 2 p r]
-> [LineSegment 2 p r]
-> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
forall k (s :: k) r p.
(Fractional r, Ord r) =>
LineSegment 2 p r
-> [LineSegment 2 p r]
-> [LineSegment 2 p r]
-> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
constructSubdivision 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'     :: forall s t p r. (Ord r, Fractional r)
                 => Polygon t p r -> PlaneGraph s p PolygonEdgeType PolygonFaceData r
triangulate' :: Polygon t p r -> PlaneGraph s p PolygonEdgeType PolygonFaceData r
triangulate' Polygon t p r
pg' = LineSegment 2 p r
-> [LineSegment 2 p r]
-> [LineSegment 2 p r]
-> PlaneGraph s p PolygonEdgeType PolygonFaceData r
forall k (s :: k) r p.
(Fractional r, Ord r) =>
LineSegment 2 p r
-> [LineSegment 2 p r]
-> [LineSegment 2 p r]
-> PlaneGraph s p PolygonEdgeType PolygonFaceData r
constructGraph 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 () p PolygonEdgeType PolygonFaceData r
monotoneP     = Polygon t p r
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
forall k (s :: k) (t :: PolygonType) p r.
(Fractional r, Ord r) =>
Polygon t p r
-> PlanarSubdivision s p PolygonEdgeType PolygonFaceData r
MM.makeMonotone @() Polygon t p r
pg -- use some arbitrary proxy type
    -- outerFaceId'  = outerFaceId monotoneP

    monotoneDiags :: [LineSegment 2 p r]
monotoneDiags = ((Dart (), LineSegment 2 p r :+ PolygonEdgeType)
 -> LineSegment 2 p r)
-> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)]
-> [LineSegment 2 p r]
forall a b. (a -> b) -> [a] -> [b]
map ((Dart (), LineSegment 2 p r :+ PolygonEdgeType)
-> Getting
     (LineSegment 2 p r)
     (Dart (), 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 (), LineSegment 2 p r :+ PolygonEdgeType)
-> Const
     (LineSegment 2 p r) (Dart (), 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 (), LineSegment 2 p r :+ PolygonEdgeType)
 -> Const
      (LineSegment 2 p r)
      (Dart (), 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 (), 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 (), LineSegment 2 p r :+ PolygonEdgeType)]
 -> [LineSegment 2 p r])
-> (PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
    -> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)])
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> [LineSegment 2 p r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((Dart (), LineSegment 2 p r :+ PolygonEdgeType) -> Bool)
-> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)]
-> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)]
forall a. (a -> Bool) -> [a] -> [a]
filter (\(Dart (), LineSegment 2 p r :+ PolygonEdgeType)
e' -> (Dart (), LineSegment 2 p r :+ PolygonEdgeType)
e'(Dart (), LineSegment 2 p r :+ PolygonEdgeType)
-> Getting
     PolygonEdgeType
     (Dart (), 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 (), LineSegment 2 p r :+ PolygonEdgeType)
-> Const
     PolygonEdgeType (Dart (), 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 (), LineSegment 2 p r :+ PolygonEdgeType)
 -> Const
      PolygonEdgeType (Dart (), LineSegment 2 p r :+ PolygonEdgeType))
-> ((PolygonEdgeType -> Const PolygonEdgeType PolygonEdgeType)
    -> (LineSegment 2 p r :+ PolygonEdgeType)
    -> Const PolygonEdgeType (LineSegment 2 p r :+ PolygonEdgeType))
-> Getting
     PolygonEdgeType
     (Dart (), 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 (), LineSegment 2 p r :+ PolygonEdgeType)]
 -> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)])
-> (PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
    -> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)])
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector (Dart (), LineSegment 2 p r :+ PolygonEdgeType)
-> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Vector (Dart (), LineSegment 2 p r :+ PolygonEdgeType)
 -> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)])
-> (PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
    -> Vector (Dart (), LineSegment 2 p r :+ PolygonEdgeType))
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> [(Dart (), LineSegment 2 p r :+ PolygonEdgeType)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> Vector (Dart (), 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 () p PolygonEdgeType PolygonFaceData r
 -> [LineSegment 2 p r])
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> [LineSegment 2 p r]
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision () 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 () p PolygonEdgeType PolygonFaceData r
    -> [Polygon 'Simple p r])
-> PlanarSubdivision () 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 () p PolygonEdgeType PolygonFaceData r
    -> [Either (Polygon 'Simple p r) (Polygon 'Multi p r)])
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> [Polygon 'Simple p r]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((FaceId' (),
  Either (Polygon 'Simple p r) (Polygon 'Multi p r)
  :+ PolygonFaceData)
 -> Either (Polygon 'Simple p r) (Polygon 'Multi p r))
-> [(FaceId' (),
     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' (),
 Either (Polygon 'Simple p r) (Polygon 'Multi p r)
 :+ PolygonFaceData)
-> Getting
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
     (FaceId' (),
      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' (),
    Either (Polygon 'Simple p r) (Polygon 'Multi p r)
    :+ PolygonFaceData)
-> Const
     (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
     (FaceId' (),
      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' (),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)
 -> Const
      (Either (Polygon 'Simple p r) (Polygon 'Multi p r))
      (FaceId' (),
       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' (),
      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' (),
   Either (Polygon 'Simple p r) (Polygon 'Multi p r)
   :+ PolygonFaceData)]
 -> [Either (Polygon 'Simple p r) (Polygon 'Multi p r)])
-> (PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
    -> [(FaceId' (),
         Either (Polygon 'Simple p r) (Polygon 'Multi p r)
         :+ PolygonFaceData)])
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> [Either (Polygon 'Simple p r) (Polygon 'Multi p r)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. ((FaceId' (),
  Either (Polygon 'Simple p r) (Polygon 'Multi p r)
  :+ PolygonFaceData)
 -> Bool)
-> [(FaceId' (),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
-> [(FaceId' (),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
forall a. (a -> Bool) -> [a] -> [a]
filter (\(FaceId' (),
 Either (Polygon 'Simple p r) (Polygon 'Multi p r)
 :+ PolygonFaceData)
mp -> (FaceId' (),
 Either (Polygon 'Simple p r) (Polygon 'Multi p r)
 :+ PolygonFaceData)
mp(FaceId' (),
 Either (Polygon 'Simple p r) (Polygon 'Multi p r)
 :+ PolygonFaceData)
-> Getting
     PolygonFaceData
     (FaceId' (),
      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' (),
    Either (Polygon 'Simple p r) (Polygon 'Multi p r)
    :+ PolygonFaceData)
-> Const
     PolygonFaceData
     (FaceId' (),
      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' (),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)
 -> Const
      PolygonFaceData
      (FaceId' (),
       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' (),
      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' (),
   Either (Polygon 'Simple p r) (Polygon 'Multi p r)
   :+ PolygonFaceData)]
 -> [(FaceId' (),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)])
-> (PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
    -> [(FaceId' (),
         Either (Polygon 'Simple p r) (Polygon 'Multi p r)
         :+ PolygonFaceData)])
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> [(FaceId' (),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Vector
  (FaceId' (),
   Either (Polygon 'Simple p r) (Polygon 'Multi p r)
   :+ PolygonFaceData)
-> [(FaceId' (),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
forall (t :: * -> *) a. Foldable t => t a -> [a]
F.toList (Vector
   (FaceId' (),
    Either (Polygon 'Simple p r) (Polygon 'Multi p r)
    :+ PolygonFaceData)
 -> [(FaceId' (),
      Either (Polygon 'Simple p r) (Polygon 'Multi p r)
      :+ PolygonFaceData)])
-> (PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
    -> Vector
         (FaceId' (),
          Either (Polygon 'Simple p r) (Polygon 'Multi p r)
          :+ PolygonFaceData))
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> [(FaceId' (),
     Either (Polygon 'Simple p r) (Polygon 'Multi p r)
     :+ PolygonFaceData)]
forall b c a. (b -> c) -> (a -> b) -> a -> c
. PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> Vector
     (FaceId' (),
      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)
internalFacePolygons (PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
 -> [LineSegment 2 p r])
-> PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
-> [LineSegment 2 p r]
forall a b. (a -> b) -> a -> b
$ PlanarSubdivision () p PolygonEdgeType PolygonFaceData r
monotoneP
    -- FIXME: we should already get all polygons in CCW order, so no
    -- need for the toClockwiseOrder' call