{-# LANGUAGE UndecidableInstances  #-}
{-# OPTIONS_GHC -Wno-unrecognised-pragmas #-}
{-# HLINT ignore "Use camelCase" #-}
--------------------------------------------------------------------------------
-- |
-- Module      :  HGeometry.Polygon.Convex.Unbounded
-- Copyright   :  (C) Frank Staals
-- License     :  see the LICENSE file
-- Maintainer  :  Frank Staals
--
-- A type for representing unbounded, Convex, polygonal regions.
--
--------------------------------------------------------------------------------
module HGeometry.Polygon.Convex.Unbounded
  ( UnboundedConvexRegion
  , UnboundedConvexRegionF(..), chain
  , extremalVertices
  , mapChain
  , boundedCore
  , boundingRays
  , unboundedBoundingHalfplanes

  , toBoundedFrom

  , LineUnboundedConvexRegionIntersection(..)
  ) where

import HGeometry.Small.TwoOrThree
import Control.Lens
import Data.Foldable1
import Data.List.NonEmpty (NonEmpty(..))
import Data.List.NonEmpty qualified as NonEmpty
import Data.Ord (comparing)
import HGeometry.Box as Box
import HGeometry.Cyclic
import HGeometry.HalfLine
import HGeometry.Foldable.Util
import HGeometry.HalfSpace
import HGeometry.HyperPlane.Class
import HGeometry.Intersection
import HGeometry.Line
import HGeometry.Point
import HGeometry.Polygon
import HGeometry.LineSegment
import HGeometry.LineSegment.PossiblyDegenerate
import HGeometry.Polygon.Simple.PossiblyDegenerate
import HGeometry.Properties
import HGeometry.Triangle as Triangle
import HGeometry.Vector
import Data.Kind (Type)
import GHC.Generics (Generic)
import Control.DeepSeq

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

-- | An unbounded polygonal Convex Region
type UnboundedConvexRegion vertex = UnboundedConvexRegionF (NumType vertex) NonEmpty vertex

-- | An unbounded polygonal ConvexRegion whose vertices are stored in an 'nonEmpty'
data UnboundedConvexRegionF r nonEmpty (vertex :: Type) =
  Unbounded (Vector 2 r)
            -- ^ vector indicating the direction of the unbounded edge
            -- incident to the first vertex. Note that this vector
            -- thus points INTO vertex v.
            (nonEmpty vertex)
            -- ^ the vertices in CCW order,
            (Vector 2 r)
            -- ^ the vector indicating the direction of the unbounded
            -- edge incident to the last vertex. The vector points
            -- away from the vertex (i.e. towards +infty).
  deriving stock (Int -> UnboundedConvexRegionF r nonEmpty vertex -> ShowS
[UnboundedConvexRegionF r nonEmpty vertex] -> ShowS
UnboundedConvexRegionF r nonEmpty vertex -> String
(Int -> UnboundedConvexRegionF r nonEmpty vertex -> ShowS)
-> (UnboundedConvexRegionF r nonEmpty vertex -> String)
-> ([UnboundedConvexRegionF r nonEmpty vertex] -> ShowS)
-> Show (UnboundedConvexRegionF r nonEmpty vertex)
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
forall r (nonEmpty :: * -> *) vertex.
(Show r, Show (nonEmpty vertex)) =>
Int -> UnboundedConvexRegionF r nonEmpty vertex -> ShowS
forall r (nonEmpty :: * -> *) vertex.
(Show r, Show (nonEmpty vertex)) =>
[UnboundedConvexRegionF r nonEmpty vertex] -> ShowS
forall r (nonEmpty :: * -> *) vertex.
(Show r, Show (nonEmpty vertex)) =>
UnboundedConvexRegionF r nonEmpty vertex -> String
$cshowsPrec :: forall r (nonEmpty :: * -> *) vertex.
(Show r, Show (nonEmpty vertex)) =>
Int -> UnboundedConvexRegionF r nonEmpty vertex -> ShowS
showsPrec :: Int -> UnboundedConvexRegionF r nonEmpty vertex -> ShowS
$cshow :: forall r (nonEmpty :: * -> *) vertex.
(Show r, Show (nonEmpty vertex)) =>
UnboundedConvexRegionF r nonEmpty vertex -> String
show :: UnboundedConvexRegionF r nonEmpty vertex -> String
$cshowList :: forall r (nonEmpty :: * -> *) vertex.
(Show r, Show (nonEmpty vertex)) =>
[UnboundedConvexRegionF r nonEmpty vertex] -> ShowS
showList :: [UnboundedConvexRegionF r nonEmpty vertex] -> ShowS
Show,UnboundedConvexRegionF r nonEmpty vertex
-> UnboundedConvexRegionF r nonEmpty vertex -> Bool
(UnboundedConvexRegionF r nonEmpty vertex
 -> UnboundedConvexRegionF r nonEmpty vertex -> Bool)
-> (UnboundedConvexRegionF r nonEmpty vertex
    -> UnboundedConvexRegionF r nonEmpty vertex -> Bool)
-> Eq (UnboundedConvexRegionF r nonEmpty vertex)
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
forall r (nonEmpty :: * -> *) vertex.
(Eq r, Eq (nonEmpty vertex)) =>
UnboundedConvexRegionF r nonEmpty vertex
-> UnboundedConvexRegionF r nonEmpty vertex -> Bool
$c== :: forall r (nonEmpty :: * -> *) vertex.
(Eq r, Eq (nonEmpty vertex)) =>
UnboundedConvexRegionF r nonEmpty vertex
-> UnboundedConvexRegionF r nonEmpty vertex -> Bool
== :: UnboundedConvexRegionF r nonEmpty vertex
-> UnboundedConvexRegionF r nonEmpty vertex -> Bool
$c/= :: forall r (nonEmpty :: * -> *) vertex.
(Eq r, Eq (nonEmpty vertex)) =>
UnboundedConvexRegionF r nonEmpty vertex
-> UnboundedConvexRegionF r nonEmpty vertex -> Bool
/= :: UnboundedConvexRegionF r nonEmpty vertex
-> UnboundedConvexRegionF r nonEmpty vertex -> Bool
Eq,(forall a b.
 (a -> b)
 -> UnboundedConvexRegionF r nonEmpty a
 -> UnboundedConvexRegionF r nonEmpty b)
-> (forall a b.
    a
    -> UnboundedConvexRegionF r nonEmpty b
    -> UnboundedConvexRegionF r nonEmpty a)
-> Functor (UnboundedConvexRegionF r nonEmpty)
forall a b.
a
-> UnboundedConvexRegionF r nonEmpty b
-> UnboundedConvexRegionF r nonEmpty a
forall a b.
(a -> b)
-> UnboundedConvexRegionF r nonEmpty a
-> UnboundedConvexRegionF r nonEmpty b
forall r (nonEmpty :: * -> *) a b.
Functor nonEmpty =>
a
-> UnboundedConvexRegionF r nonEmpty b
-> UnboundedConvexRegionF r nonEmpty a
forall r (nonEmpty :: * -> *) a b.
Functor nonEmpty =>
(a -> b)
-> UnboundedConvexRegionF r nonEmpty a
-> UnboundedConvexRegionF r nonEmpty b
forall (f :: * -> *).
(forall a b. (a -> b) -> f a -> f b)
-> (forall a b. a -> f b -> f a) -> Functor f
$cfmap :: forall r (nonEmpty :: * -> *) a b.
Functor nonEmpty =>
(a -> b)
-> UnboundedConvexRegionF r nonEmpty a
-> UnboundedConvexRegionF r nonEmpty b
fmap :: forall a b.
(a -> b)
-> UnboundedConvexRegionF r nonEmpty a
-> UnboundedConvexRegionF r nonEmpty b
$c<$ :: forall r (nonEmpty :: * -> *) a b.
Functor nonEmpty =>
a
-> UnboundedConvexRegionF r nonEmpty b
-> UnboundedConvexRegionF r nonEmpty a
<$ :: forall a b.
a
-> UnboundedConvexRegionF r nonEmpty b
-> UnboundedConvexRegionF r nonEmpty a
Functor,(forall m. Monoid m => UnboundedConvexRegionF r nonEmpty m -> m)
-> (forall m a.
    Monoid m =>
    (a -> m) -> UnboundedConvexRegionF r nonEmpty a -> m)
-> (forall m a.
    Monoid m =>
    (a -> m) -> UnboundedConvexRegionF r nonEmpty a -> m)
-> (forall a b.
    (a -> b -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b)
-> (forall a b.
    (a -> b -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b)
-> (forall b a.
    (b -> a -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b)
-> (forall b a.
    (b -> a -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b)
-> (forall a.
    (a -> a -> a) -> UnboundedConvexRegionF r nonEmpty a -> a)
-> (forall a.
    (a -> a -> a) -> UnboundedConvexRegionF r nonEmpty a -> a)
-> (forall a. UnboundedConvexRegionF r nonEmpty a -> [a])
-> (forall a. UnboundedConvexRegionF r nonEmpty a -> Bool)
-> (forall a. UnboundedConvexRegionF r nonEmpty a -> Int)
-> (forall a.
    Eq a =>
    a -> UnboundedConvexRegionF r nonEmpty a -> Bool)
-> (forall a. Ord a => UnboundedConvexRegionF r nonEmpty a -> a)
-> (forall a. Ord a => UnboundedConvexRegionF r nonEmpty a -> a)
-> (forall a. Num a => UnboundedConvexRegionF r nonEmpty a -> a)
-> (forall a. Num a => UnboundedConvexRegionF r nonEmpty a -> a)
-> Foldable (UnboundedConvexRegionF r nonEmpty)
forall a. Eq a => a -> UnboundedConvexRegionF r nonEmpty a -> Bool
forall a. Num a => UnboundedConvexRegionF r nonEmpty a -> a
forall a. Ord a => UnboundedConvexRegionF r nonEmpty a -> a
forall m. Monoid m => UnboundedConvexRegionF r nonEmpty m -> m
forall a. UnboundedConvexRegionF r nonEmpty a -> Bool
forall a. UnboundedConvexRegionF r nonEmpty a -> Int
forall a. UnboundedConvexRegionF r nonEmpty a -> [a]
forall a. (a -> a -> a) -> UnboundedConvexRegionF r nonEmpty a -> a
forall m a.
Monoid m =>
(a -> m) -> UnboundedConvexRegionF r nonEmpty a -> m
forall b a.
(b -> a -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
forall a b.
(a -> b -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
forall r (nonEmpty :: * -> *) a.
(Foldable nonEmpty, Eq a) =>
a -> UnboundedConvexRegionF r nonEmpty a -> Bool
forall r (nonEmpty :: * -> *) a.
(Foldable nonEmpty, Num a) =>
UnboundedConvexRegionF r nonEmpty a -> a
forall r (nonEmpty :: * -> *) a.
(Foldable nonEmpty, Ord a) =>
UnboundedConvexRegionF r nonEmpty a -> a
forall r (nonEmpty :: * -> *) m.
(Foldable nonEmpty, Monoid m) =>
UnboundedConvexRegionF r nonEmpty m -> m
forall r (nonEmpty :: * -> *) a.
Foldable nonEmpty =>
UnboundedConvexRegionF r nonEmpty a -> Bool
forall r (nonEmpty :: * -> *) a.
Foldable nonEmpty =>
UnboundedConvexRegionF r nonEmpty a -> Int
forall r (nonEmpty :: * -> *) a.
Foldable nonEmpty =>
UnboundedConvexRegionF r nonEmpty a -> [a]
forall r (nonEmpty :: * -> *) a.
Foldable nonEmpty =>
(a -> a -> a) -> UnboundedConvexRegionF r nonEmpty a -> a
forall r (nonEmpty :: * -> *) m a.
(Foldable nonEmpty, Monoid m) =>
(a -> m) -> UnboundedConvexRegionF r nonEmpty a -> m
forall r (nonEmpty :: * -> *) b a.
Foldable nonEmpty =>
(b -> a -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
forall r (nonEmpty :: * -> *) a b.
Foldable nonEmpty =>
(a -> b -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
forall (t :: * -> *).
(forall m. Monoid m => t m -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall m a. Monoid m => (a -> m) -> t a -> m)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall a b. (a -> b -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall b a. (b -> a -> b) -> b -> t a -> b)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. (a -> a -> a) -> t a -> a)
-> (forall a. t a -> [a])
-> (forall a. t a -> Bool)
-> (forall a. t a -> Int)
-> (forall a. Eq a => a -> t a -> Bool)
-> (forall a. Ord a => t a -> a)
-> (forall a. Ord a => t a -> a)
-> (forall a. Num a => t a -> a)
-> (forall a. Num a => t a -> a)
-> Foldable t
$cfold :: forall r (nonEmpty :: * -> *) m.
(Foldable nonEmpty, Monoid m) =>
UnboundedConvexRegionF r nonEmpty m -> m
fold :: forall m. Monoid m => UnboundedConvexRegionF r nonEmpty m -> m
$cfoldMap :: forall r (nonEmpty :: * -> *) m a.
(Foldable nonEmpty, Monoid m) =>
(a -> m) -> UnboundedConvexRegionF r nonEmpty a -> m
foldMap :: forall m a.
Monoid m =>
(a -> m) -> UnboundedConvexRegionF r nonEmpty a -> m
$cfoldMap' :: forall r (nonEmpty :: * -> *) m a.
(Foldable nonEmpty, Monoid m) =>
(a -> m) -> UnboundedConvexRegionF r nonEmpty a -> m
foldMap' :: forall m a.
Monoid m =>
(a -> m) -> UnboundedConvexRegionF r nonEmpty a -> m
$cfoldr :: forall r (nonEmpty :: * -> *) a b.
Foldable nonEmpty =>
(a -> b -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
foldr :: forall a b.
(a -> b -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
$cfoldr' :: forall r (nonEmpty :: * -> *) a b.
Foldable nonEmpty =>
(a -> b -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
foldr' :: forall a b.
(a -> b -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
$cfoldl :: forall r (nonEmpty :: * -> *) b a.
Foldable nonEmpty =>
(b -> a -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
foldl :: forall b a.
(b -> a -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
$cfoldl' :: forall r (nonEmpty :: * -> *) b a.
Foldable nonEmpty =>
(b -> a -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
foldl' :: forall b a.
(b -> a -> b) -> b -> UnboundedConvexRegionF r nonEmpty a -> b
$cfoldr1 :: forall r (nonEmpty :: * -> *) a.
Foldable nonEmpty =>
(a -> a -> a) -> UnboundedConvexRegionF r nonEmpty a -> a
foldr1 :: forall a. (a -> a -> a) -> UnboundedConvexRegionF r nonEmpty a -> a
$cfoldl1 :: forall r (nonEmpty :: * -> *) a.
Foldable nonEmpty =>
(a -> a -> a) -> UnboundedConvexRegionF r nonEmpty a -> a
foldl1 :: forall a. (a -> a -> a) -> UnboundedConvexRegionF r nonEmpty a -> a
$ctoList :: forall r (nonEmpty :: * -> *) a.
Foldable nonEmpty =>
UnboundedConvexRegionF r nonEmpty a -> [a]
toList :: forall a. UnboundedConvexRegionF r nonEmpty a -> [a]
$cnull :: forall r (nonEmpty :: * -> *) a.
Foldable nonEmpty =>
UnboundedConvexRegionF r nonEmpty a -> Bool
null :: forall a. UnboundedConvexRegionF r nonEmpty a -> Bool
$clength :: forall r (nonEmpty :: * -> *) a.
Foldable nonEmpty =>
UnboundedConvexRegionF r nonEmpty a -> Int
length :: forall a. UnboundedConvexRegionF r nonEmpty a -> Int
$celem :: forall r (nonEmpty :: * -> *) a.
(Foldable nonEmpty, Eq a) =>
a -> UnboundedConvexRegionF r nonEmpty a -> Bool
elem :: forall a. Eq a => a -> UnboundedConvexRegionF r nonEmpty a -> Bool
$cmaximum :: forall r (nonEmpty :: * -> *) a.
(Foldable nonEmpty, Ord a) =>
UnboundedConvexRegionF r nonEmpty a -> a
maximum :: forall a. Ord a => UnboundedConvexRegionF r nonEmpty a -> a
$cminimum :: forall r (nonEmpty :: * -> *) a.
(Foldable nonEmpty, Ord a) =>
UnboundedConvexRegionF r nonEmpty a -> a
minimum :: forall a. Ord a => UnboundedConvexRegionF r nonEmpty a -> a
$csum :: forall r (nonEmpty :: * -> *) a.
(Foldable nonEmpty, Num a) =>
UnboundedConvexRegionF r nonEmpty a -> a
sum :: forall a. Num a => UnboundedConvexRegionF r nonEmpty a -> a
$cproduct :: forall r (nonEmpty :: * -> *) a.
(Foldable nonEmpty, Num a) =>
UnboundedConvexRegionF r nonEmpty a -> a
product :: forall a. Num a => UnboundedConvexRegionF r nonEmpty a -> a
Foldable,Functor (UnboundedConvexRegionF r nonEmpty)
Foldable (UnboundedConvexRegionF r nonEmpty)
(Functor (UnboundedConvexRegionF r nonEmpty),
 Foldable (UnboundedConvexRegionF r nonEmpty)) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b)
 -> UnboundedConvexRegionF r nonEmpty a
 -> f (UnboundedConvexRegionF r nonEmpty b))
-> (forall (f :: * -> *) a.
    Applicative f =>
    UnboundedConvexRegionF r nonEmpty (f a)
    -> f (UnboundedConvexRegionF r nonEmpty a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b)
    -> UnboundedConvexRegionF r nonEmpty a
    -> m (UnboundedConvexRegionF r nonEmpty b))
-> (forall (m :: * -> *) a.
    Monad m =>
    UnboundedConvexRegionF r nonEmpty (m a)
    -> m (UnboundedConvexRegionF r nonEmpty a))
-> Traversable (UnboundedConvexRegionF r nonEmpty)
forall r (nonEmpty :: * -> *).
Traversable nonEmpty =>
Functor (UnboundedConvexRegionF r nonEmpty)
forall r (nonEmpty :: * -> *).
Traversable nonEmpty =>
Foldable (UnboundedConvexRegionF r nonEmpty)
forall r (nonEmpty :: * -> *) (m :: * -> *) a.
(Traversable nonEmpty, Monad m) =>
UnboundedConvexRegionF r nonEmpty (m a)
-> m (UnboundedConvexRegionF r nonEmpty a)
forall r (nonEmpty :: * -> *) (f :: * -> *) a.
(Traversable nonEmpty, Applicative f) =>
UnboundedConvexRegionF r nonEmpty (f a)
-> f (UnboundedConvexRegionF r nonEmpty a)
forall r (nonEmpty :: * -> *) (m :: * -> *) a b.
(Traversable nonEmpty, Monad m) =>
(a -> m b)
-> UnboundedConvexRegionF r nonEmpty a
-> m (UnboundedConvexRegionF r nonEmpty b)
forall r (nonEmpty :: * -> *) (f :: * -> *) a b.
(Traversable nonEmpty, Applicative f) =>
(a -> f b)
-> UnboundedConvexRegionF r nonEmpty a
-> f (UnboundedConvexRegionF r nonEmpty b)
forall (t :: * -> *).
(Functor t, Foldable t) =>
(forall (f :: * -> *) a b.
 Applicative f =>
 (a -> f b) -> t a -> f (t b))
-> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
-> (forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> t a -> m (t b))
-> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
-> Traversable t
forall (m :: * -> *) a.
Monad m =>
UnboundedConvexRegionF r nonEmpty (m a)
-> m (UnboundedConvexRegionF r nonEmpty a)
forall (f :: * -> *) a.
Applicative f =>
UnboundedConvexRegionF r nonEmpty (f a)
-> f (UnboundedConvexRegionF r nonEmpty a)
forall (m :: * -> *) a b.
Monad m =>
(a -> m b)
-> UnboundedConvexRegionF r nonEmpty a
-> m (UnboundedConvexRegionF r nonEmpty b)
forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> UnboundedConvexRegionF r nonEmpty a
-> f (UnboundedConvexRegionF r nonEmpty b)
$ctraverse :: forall r (nonEmpty :: * -> *) (f :: * -> *) a b.
(Traversable nonEmpty, Applicative f) =>
(a -> f b)
-> UnboundedConvexRegionF r nonEmpty a
-> f (UnboundedConvexRegionF r nonEmpty b)
traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b)
-> UnboundedConvexRegionF r nonEmpty a
-> f (UnboundedConvexRegionF r nonEmpty b)
$csequenceA :: forall r (nonEmpty :: * -> *) (f :: * -> *) a.
(Traversable nonEmpty, Applicative f) =>
UnboundedConvexRegionF r nonEmpty (f a)
-> f (UnboundedConvexRegionF r nonEmpty a)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
UnboundedConvexRegionF r nonEmpty (f a)
-> f (UnboundedConvexRegionF r nonEmpty a)
$cmapM :: forall r (nonEmpty :: * -> *) (m :: * -> *) a b.
(Traversable nonEmpty, Monad m) =>
(a -> m b)
-> UnboundedConvexRegionF r nonEmpty a
-> m (UnboundedConvexRegionF r nonEmpty b)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b)
-> UnboundedConvexRegionF r nonEmpty a
-> m (UnboundedConvexRegionF r nonEmpty b)
$csequence :: forall r (nonEmpty :: * -> *) (m :: * -> *) a.
(Traversable nonEmpty, Monad m) =>
UnboundedConvexRegionF r nonEmpty (m a)
-> m (UnboundedConvexRegionF r nonEmpty a)
sequence :: forall (m :: * -> *) a.
Monad m =>
UnboundedConvexRegionF r nonEmpty (m a)
-> m (UnboundedConvexRegionF r nonEmpty a)
Traversable,(forall x.
 UnboundedConvexRegionF r nonEmpty vertex
 -> Rep (UnboundedConvexRegionF r nonEmpty vertex) x)
-> (forall x.
    Rep (UnboundedConvexRegionF r nonEmpty vertex) x
    -> UnboundedConvexRegionF r nonEmpty vertex)
-> Generic (UnboundedConvexRegionF r nonEmpty vertex)
forall x.
Rep (UnboundedConvexRegionF r nonEmpty vertex) x
-> UnboundedConvexRegionF r nonEmpty vertex
forall x.
UnboundedConvexRegionF r nonEmpty vertex
-> Rep (UnboundedConvexRegionF r nonEmpty vertex) x
forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall r (nonEmpty :: * -> *) vertex x.
Rep (UnboundedConvexRegionF r nonEmpty vertex) x
-> UnboundedConvexRegionF r nonEmpty vertex
forall r (nonEmpty :: * -> *) vertex x.
UnboundedConvexRegionF r nonEmpty vertex
-> Rep (UnboundedConvexRegionF r nonEmpty vertex) x
$cfrom :: forall r (nonEmpty :: * -> *) vertex x.
UnboundedConvexRegionF r nonEmpty vertex
-> Rep (UnboundedConvexRegionF r nonEmpty vertex) x
from :: forall x.
UnboundedConvexRegionF r nonEmpty vertex
-> Rep (UnboundedConvexRegionF r nonEmpty vertex) x
$cto :: forall r (nonEmpty :: * -> *) vertex x.
Rep (UnboundedConvexRegionF r nonEmpty vertex) x
-> UnboundedConvexRegionF r nonEmpty vertex
to :: forall x.
Rep (UnboundedConvexRegionF r nonEmpty vertex) x
-> UnboundedConvexRegionF r nonEmpty vertex
Generic)

type instance NumType   (UnboundedConvexRegionF r nonEmpty vertex) = r
type instance Dimension (UnboundedConvexRegionF r nonEmpty vertex) = 2

instance (NFData r, NFData (nonEmpty vertex)
         ) => NFData (UnboundedConvexRegionF r nonEmpty vertex)

-- | Lens to access the chain of vertices in CCW order
chain :: Lens (UnboundedConvexRegionF r nonEmpty vertex)
              (UnboundedConvexRegionF r nonEmpty' vertex')
              (nonEmpty vertex) (nonEmpty' vertex')
chain :: forall r (nonEmpty :: * -> *) vertex (nonEmpty' :: * -> *) vertex'
       (f :: * -> *).
Functor f =>
(nonEmpty vertex -> f (nonEmpty' vertex'))
-> UnboundedConvexRegionF r nonEmpty vertex
-> f (UnboundedConvexRegionF r nonEmpty' vertex')
chain = (UnboundedConvexRegionF r nonEmpty vertex -> nonEmpty vertex)
-> (UnboundedConvexRegionF r nonEmpty vertex
    -> nonEmpty' vertex' -> UnboundedConvexRegionF r nonEmpty' vertex')
-> Lens
     (UnboundedConvexRegionF r nonEmpty vertex)
     (UnboundedConvexRegionF r nonEmpty' vertex')
     (nonEmpty vertex)
     (nonEmpty' vertex')
forall s a b t. (s -> a) -> (s -> b -> t) -> Lens s t a b
lens (\(Unbounded Vector 2 r
_ nonEmpty vertex
chain' Vector 2 r
_) -> nonEmpty vertex
chain')
             (\(Unbounded Vector 2 r
u nonEmpty vertex
_ Vector 2 r
v) nonEmpty' vertex'
chain' -> Vector 2 r
-> nonEmpty' vertex'
-> Vector 2 r
-> UnboundedConvexRegionF r nonEmpty' vertex'
forall r (nonEmpty :: * -> *) vertex.
Vector 2 r
-> nonEmpty vertex
-> Vector 2 r
-> UnboundedConvexRegionF r nonEmpty vertex
Unbounded Vector 2 r
u nonEmpty' vertex'
chain' Vector 2 r
v)

-- | map a function over the sequence of points
mapChain                       :: (nonEmpty vertex -> nonEmpty' vertex')
                               -> UnboundedConvexRegionF r nonEmpty vertex
                               -> UnboundedConvexRegionF r nonEmpty' vertex'
mapChain :: forall (nonEmpty :: * -> *) vertex (nonEmpty' :: * -> *) vertex' r.
(nonEmpty vertex -> nonEmpty' vertex')
-> UnboundedConvexRegionF r nonEmpty vertex
-> UnboundedConvexRegionF r nonEmpty' vertex'
mapChain nonEmpty vertex -> nonEmpty' vertex'
f (Unbounded Vector 2 r
v nonEmpty vertex
pts Vector 2 r
w) = Vector 2 r
-> nonEmpty' vertex'
-> Vector 2 r
-> UnboundedConvexRegionF r nonEmpty' vertex'
forall r (nonEmpty :: * -> *) vertex.
Vector 2 r
-> nonEmpty vertex
-> Vector 2 r
-> UnboundedConvexRegionF r nonEmpty vertex
Unbounded Vector 2 r
v (nonEmpty vertex -> nonEmpty' vertex'
f nonEmpty vertex
pts) Vector 2 r
w

-- | Compute the first and last vertex of the chain. Returns a Left if the first and last
-- are the same.
extremalVertices                            :: UnboundedConvexRegionF r NonEmpty vertex
                                            -> Either vertex (Vector 2 vertex)
extremalVertices :: forall r vertex.
UnboundedConvexRegionF r NonEmpty vertex
-> Either vertex (Vector 2 vertex)
extremalVertices (Unbounded Vector 2 r
_ (vertex
p :| [vertex]
pts) Vector 2 r
_) = case [vertex] -> Maybe (NonEmpty vertex)
forall a. [a] -> Maybe (NonEmpty a)
NonEmpty.nonEmpty [vertex]
pts of
                                                Maybe (NonEmpty vertex)
Nothing   -> vertex -> Either vertex (Vector 2 vertex)
forall a b. a -> Either a b
Left vertex
p
                                                Just NonEmpty vertex
pts' -> Vector 2 vertex -> Either vertex (Vector 2 vertex)
forall a b. b -> Either a b
Right (Vector 2 vertex -> Either vertex (Vector 2 vertex))
-> Vector 2 vertex -> Either vertex (Vector 2 vertex)
forall a b. (a -> b) -> a -> b
$ vertex -> vertex -> Vector 2 vertex
forall r. r -> r -> Vector 2 r
Vector2 vertex
p (NonEmpty vertex -> vertex
forall a. NonEmpty a -> a
NonEmpty.last NonEmpty vertex
pts')

-- | Computes the two bounding rays of the unbounded region. Note that the rays now are
-- both pointing toward infinity. The second ray has the unbounded region to its left,
-- whereas the first one has it to its right.
boundingRays                          :: (Point_ vertex 2 r, Num r)
                                      => UnboundedConvexRegionF r NonEmpty vertex
                                      -> Vector 2 (HalfLine vertex)
boundingRays :: forall vertex r.
(Point_ vertex 2 r, Num r) =>
UnboundedConvexRegionF r NonEmpty vertex
-> Vector 2 (HalfLine vertex)
boundingRays chain' :: UnboundedConvexRegionF r NonEmpty vertex
chain'@(Unbounded Vector 2 r
v NonEmpty vertex
_ Vector 2 r
w) = Vector 2 vertex -> Vector 2 (HalfLine vertex)
compute (Vector 2 vertex -> Vector 2 (HalfLine vertex))
-> Vector 2 vertex -> Vector 2 (HalfLine vertex)
forall a b. (a -> b) -> a -> b
$ case UnboundedConvexRegionF r NonEmpty vertex
-> Either vertex (Vector 2 vertex)
forall r vertex.
UnboundedConvexRegionF r NonEmpty vertex
-> Either vertex (Vector 2 vertex)
extremalVertices UnboundedConvexRegionF r NonEmpty vertex
chain' of
                                          Left vertex
p   -> vertex -> vertex -> Vector 2 vertex
forall r. r -> r -> Vector 2 r
Vector2 vertex
p vertex
p
                                          Right Vector 2 vertex
vs -> Vector 2 vertex
vs
  where
    compute :: Vector 2 vertex -> Vector 2 (HalfLine vertex)
compute (Vector2 vertex
p vertex
q) = HalfLine vertex -> HalfLine vertex -> Vector 2 (HalfLine vertex)
forall r. r -> r -> Vector 2 r
Vector2 (vertex
-> Vector (Dimension vertex) (NumType vertex) -> HalfLine vertex
forall point.
point -> Vector (Dimension point) (NumType point) -> HalfLine point
HalfLine vertex
p (Vector (Dimension vertex) (NumType vertex) -> HalfLine vertex)
-> Vector (Dimension vertex) (NumType vertex) -> HalfLine vertex
forall a b. (a -> b) -> a -> b
$ Vector (Dimension vertex) (NumType vertex)
-> Vector (Dimension vertex) (NumType vertex)
forall r vector (d :: Nat).
(Num r, Vector_ vector d r) =>
vector -> vector
negated Vector 2 r
Vector (Dimension vertex) (NumType vertex)
v) (vertex
-> Vector (Dimension vertex) (NumType vertex) -> HalfLine vertex
forall point.
point -> Vector (Dimension point) (NumType point) -> HalfLine point
HalfLine vertex
q Vector 2 r
Vector (Dimension vertex) (NumType vertex)
w)


-- | Computes the core of the unbounded region; i.e. the convex hull of the
-- vertices of the region.
boundedCore                     :: ( VertexContainer nonEmpty vertex, Point_ vertex 2 r
                                   , HasFromFoldable1 nonEmpty
                                   )
                                => UnboundedConvexRegionF r nonEmpty vertex
                                -> PossiblyDegenerateSimplePolygon vertex
                                        (ConvexPolygonF (Cyclic nonEmpty) vertex)
boundedCore :: forall (nonEmpty :: * -> *) vertex r.
(VertexContainer nonEmpty vertex, Point_ vertex 2 r,
 HasFromFoldable1 nonEmpty) =>
UnboundedConvexRegionF r nonEmpty vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic nonEmpty) vertex)
boundedCore (Unbounded Vector 2 r
_ nonEmpty vertex
pts Vector 2 r
_) = case nonEmpty vertex -> NonEmpty vertex
forall a. nonEmpty a -> NonEmpty a
forall (t :: * -> *) a. Foldable1 t => t a -> NonEmpty a
toNonEmpty nonEmpty vertex
pts of
  (vertex
u :| [])  -> vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic nonEmpty) vertex)
forall vertex polygon.
vertex -> PossiblyDegenerateSimplePolygon vertex polygon
DegenerateVertex vertex
u
  (vertex
u :| [vertex
v]) -> ClosedLineSegment vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic nonEmpty) vertex)
forall vertex polygon.
ClosedLineSegment vertex
-> PossiblyDegenerateSimplePolygon vertex polygon
DegenerateEdge (ClosedLineSegment vertex
 -> PossiblyDegenerateSimplePolygon
      vertex (ConvexPolygonF (Cyclic nonEmpty) vertex))
-> ClosedLineSegment vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic nonEmpty) vertex)
forall a b. (a -> b) -> a -> b
$ vertex -> vertex -> ClosedLineSegment vertex
forall point. point -> point -> ClosedLineSegment point
ClosedLineSegment vertex
u vertex
v
  NonEmpty vertex
_          -> ConvexPolygonF (Cyclic nonEmpty) vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic nonEmpty) vertex)
forall vertex polygon.
polygon -> PossiblyDegenerateSimplePolygon vertex polygon
ActualPolygon (ConvexPolygonF (Cyclic nonEmpty) vertex
 -> PossiblyDegenerateSimplePolygon
      vertex (ConvexPolygonF (Cyclic nonEmpty) vertex))
-> ConvexPolygonF (Cyclic nonEmpty) vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic nonEmpty) vertex)
forall a b. (a -> b) -> a -> b
$ nonEmpty vertex -> ConvexPolygonF (Cyclic nonEmpty) vertex
forall simplePolygon point r (f :: * -> *).
(SimplePolygon_ simplePolygon point r, Foldable1 f) =>
f point -> simplePolygon
forall (f :: * -> *).
Foldable1 f =>
f vertex -> ConvexPolygonF (Cyclic nonEmpty) vertex
uncheckedFromCCWPoints nonEmpty vertex
pts


-- | the 2 or three halfplanes bounding the unbounded part of the region
-- in particular: the region minus its bounded core
unboundedBoundingHalfplanes :: (Point_ vertex 2 r, Num r, Ord r)
                            => UnboundedConvexRegionF r NonEmpty vertex
                            -> TwoOrThree (HalfPlaneF (LinePV 2 r))
unboundedBoundingHalfplanes :: forall vertex r.
(Point_ vertex 2 r, Num r, Ord r) =>
UnboundedConvexRegionF r NonEmpty vertex
-> TwoOrThree (HalfPlaneF (LinePV 2 r))
unboundedBoundingHalfplanes region :: UnboundedConvexRegionF r NonEmpty vertex
region@(Unbounded Vector 2 r
v NonEmpty vertex
_ Vector 2 r
w) =
    Either
  (Two (HalfPlaneF (LinePV 2 r))) (Three (HalfPlaneF (LinePV 2 r)))
-> TwoOrThree (HalfPlaneF (LinePV 2 r))
forall a. Either (Two a) (Three a) -> TwoOrThree a
TwoOrThree (Either
   (Two (HalfPlaneF (LinePV 2 r))) (Three (HalfPlaneF (LinePV 2 r)))
 -> TwoOrThree (HalfPlaneF (LinePV 2 r)))
-> (Either vertex (Vector 2 vertex)
    -> Either
         (Two (HalfPlaneF (LinePV 2 r))) (Three (HalfPlaneF (LinePV 2 r))))
-> Either vertex (Vector 2 vertex)
-> TwoOrThree (HalfPlaneF (LinePV 2 r))
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (vertex -> Two (HalfPlaneF (LinePV 2 r)))
-> (Vector 2 vertex -> Three (HalfPlaneF (LinePV 2 r)))
-> Either vertex (Vector 2 vertex)
-> Either
     (Two (HalfPlaneF (LinePV 2 r))) (Three (HalfPlaneF (LinePV 2 r)))
forall a b c d. (a -> b) -> (c -> d) -> Either a c -> Either b d
forall (p :: * -> * -> *) a b c d.
Bifunctor p =>
(a -> b) -> (c -> d) -> p a c -> p b d
bimap vertex -> Two (HalfPlaneF (LinePV 2 r))
two Vector 2 vertex -> Three (HalfPlaneF (LinePV 2 r))
three (Either vertex (Vector 2 vertex)
 -> TwoOrThree (HalfPlaneF (LinePV 2 r)))
-> Either vertex (Vector 2 vertex)
-> TwoOrThree (HalfPlaneF (LinePV 2 r))
forall a b. (a -> b) -> a -> b
$ UnboundedConvexRegionF r NonEmpty vertex
-> Either vertex (Vector 2 vertex)
forall r vertex.
UnboundedConvexRegionF r NonEmpty vertex
-> Either vertex (Vector 2 vertex)
extremalVertices UnboundedConvexRegionF r NonEmpty vertex
region
  where
    two :: vertex -> Two (HalfPlaneF (LinePV 2 r))
two (Getting (Point 2 r) vertex (Point 2 r) -> vertex -> Point 2 r
forall s (m :: * -> *) a. MonadReader s m => Getting a s a -> m a
view Getting (Point 2 r) vertex (Point 2 r)
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' vertex (Point 2 r)
asPoint -> Point 2 r
p) = HalfPlaneF (LinePV 2 r)
-> HalfPlaneF (LinePV 2 r) -> Two (HalfPlaneF (LinePV 2 r))
forall a. a -> a -> Two a
Two (LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall r. (Num r, Ord r) => LinePV 2 r -> HalfSpaceF (LinePV 2 r)
leftHalfPlane (LinePV 2 r -> HalfPlaneF (LinePV 2 r))
-> LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall a b. (a -> b) -> a -> b
$ Point 2 r -> Vector 2 r -> LinePV 2 r
forall (d :: Nat) r. Point d r -> Vector d r -> LinePV d r
LinePV Point 2 r
p Vector 2 r
v) (LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall r. (Num r, Ord r) => LinePV 2 r -> HalfSpaceF (LinePV 2 r)
leftHalfPlane (LinePV 2 r -> HalfPlaneF (LinePV 2 r))
-> LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall a b. (a -> b) -> a -> b
$ Point 2 r -> Vector 2 r -> LinePV 2 r
forall (d :: Nat) r. Point d r -> Vector d r -> LinePV d r
LinePV Point 2 r
p Vector 2 r
w)
    three :: Vector 2 vertex -> Three (HalfPlaneF (LinePV 2 r))
three ((vertex -> Point 2 r) -> Vector 2 vertex -> Vector 2 (Point 2 r)
forall a b. (a -> b) -> Vector 2 a -> Vector 2 b
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (Getting (Point 2 r) vertex (Point 2 r) -> vertex -> Point 2 r
forall s (m :: * -> *) a. MonadReader s m => Getting a s a -> m a
view Getting (Point 2 r) vertex (Point 2 r)
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' vertex (Point 2 r)
asPoint) -> Vector2 Point 2 r
p Point 2 r
q) =
      HalfPlaneF (LinePV 2 r)
-> HalfPlaneF (LinePV 2 r)
-> HalfPlaneF (LinePV 2 r)
-> Three (HalfPlaneF (LinePV 2 r))
forall a. a -> a -> a -> Three a
Three (LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall r. (Num r, Ord r) => LinePV 2 r -> HalfSpaceF (LinePV 2 r)
leftHalfPlane (LinePV 2 r -> HalfPlaneF (LinePV 2 r))
-> LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall a b. (a -> b) -> a -> b
$ Point 2 r -> Vector 2 r -> LinePV 2 r
forall (d :: Nat) r. Point d r -> Vector d r -> LinePV d r
LinePV Point 2 r
p Vector 2 r
v        )
            (LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall r. (Num r, Ord r) => LinePV 2 r -> HalfSpaceF (LinePV 2 r)
leftHalfPlane (LinePV 2 r -> HalfPlaneF (LinePV 2 r))
-> LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall a b. (a -> b) -> a -> b
$ Point 2 r -> Vector 2 r -> LinePV 2 r
forall (d :: Nat) r. Point d r -> Vector d r -> LinePV d r
LinePV Point 2 r
q Vector 2 r
w        )
            (LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall r. (Num r, Ord r) => LinePV 2 r -> HalfSpaceF (LinePV 2 r)
leftHalfPlane (LinePV 2 r -> HalfPlaneF (LinePV 2 r))
-> LinePV 2 r -> HalfPlaneF (LinePV 2 r)
forall a b. (a -> b) -> a -> b
$ Point 2 r -> Vector 2 r -> LinePV 2 r
forall (d :: Nat) r. Point d r -> Vector d r -> LinePV d r
LinePV Point 2 r
p (Point 2 r
q Point 2 r -> Point 2 r -> Vector 2 r
forall point (d :: Nat) r.
(Affine_ point d r, Num r) =>
point -> point -> Vector d r
.-. Point 2 r
p))
{-
data Cone r apex = Cone { _apex                   :: apex
                        , _leftBoundingDirection  :: Vector 2 r
                        , _rightBoundingDirection :: Vector 2 r
                        }
                 deriving (Show,Eq)
makeLenses ''Cone

type instance Dimension (Cone r apex) = 2
type instance NumType   (Cone r apex) = r
-}

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

instance ( Traversable1 nonEmpty
         , Ixed (nonEmpty vertex), IxValue (nonEmpty vertex) ~ vertex
         , Index (nonEmpty vertex) ~ Int
         ) => HasVertices' (UnboundedConvexRegionF r nonEmpty vertex) where
  type Vertex   (UnboundedConvexRegionF r nonEmpty vertex) = vertex
  type VertexIx (UnboundedConvexRegionF r nonEmpty vertex) = Int
  -- I think we could get rid of the Int constraint here, and just use an arbitrary
  -- Index type. In that case, we need a slightly more general version of 'traversed1'
  -- to implement 'vertices' in the 'HasVertices' instance.
  vertexAt :: VertexIx (UnboundedConvexRegionF r nonEmpty vertex)
-> IndexedTraversal'
     (VertexIx (UnboundedConvexRegionF r nonEmpty vertex))
     (UnboundedConvexRegionF r nonEmpty vertex)
     (Vertex (UnboundedConvexRegionF r nonEmpty vertex))
vertexAt VertexIx (UnboundedConvexRegionF r nonEmpty vertex)
i = (nonEmpty vertex -> f (nonEmpty vertex))
-> UnboundedConvexRegionF r nonEmpty vertex
-> f (UnboundedConvexRegionF r nonEmpty vertex)
forall r (nonEmpty :: * -> *) vertex (nonEmpty' :: * -> *) vertex'
       (f :: * -> *).
Functor f =>
(nonEmpty vertex -> f (nonEmpty' vertex'))
-> UnboundedConvexRegionF r nonEmpty vertex
-> f (UnboundedConvexRegionF r nonEmpty' vertex')
chain ((nonEmpty vertex -> f (nonEmpty vertex))
 -> UnboundedConvexRegionF r nonEmpty vertex
 -> f (UnboundedConvexRegionF r nonEmpty vertex))
-> (p vertex (f vertex) -> nonEmpty vertex -> f (nonEmpty vertex))
-> p vertex (f vertex)
-> UnboundedConvexRegionF r nonEmpty vertex
-> f (UnboundedConvexRegionF r nonEmpty vertex)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> Index (nonEmpty vertex)
-> IndexedTraversal'
     (Index (nonEmpty vertex))
     (nonEmpty vertex)
     (IxValue (nonEmpty vertex))
forall m.
Ixed m =>
Index m -> IndexedTraversal' (Index m) m (IxValue m)
iix VertexIx (UnboundedConvexRegionF r nonEmpty vertex)
Index (nonEmpty vertex)
i
  numVertices :: UnboundedConvexRegionF r nonEmpty vertex -> Int
numVertices = nonEmpty vertex -> Int
forall a. nonEmpty a -> Int
forall (t :: * -> *) a. Foldable t => t a -> Int
length (nonEmpty vertex -> Int)
-> (UnboundedConvexRegionF r nonEmpty vertex -> nonEmpty vertex)
-> UnboundedConvexRegionF r nonEmpty vertex
-> Int
forall b c a. (b -> c) -> (a -> b) -> a -> c
. Getting
  (nonEmpty vertex)
  (UnboundedConvexRegionF r nonEmpty vertex)
  (nonEmpty vertex)
-> UnboundedConvexRegionF r nonEmpty vertex -> nonEmpty vertex
forall s (m :: * -> *) a. MonadReader s m => Getting a s a -> m a
view Getting
  (nonEmpty vertex)
  (UnboundedConvexRegionF r nonEmpty vertex)
  (nonEmpty vertex)
forall r (nonEmpty :: * -> *) vertex (nonEmpty' :: * -> *) vertex'
       (f :: * -> *).
Functor f =>
(nonEmpty vertex -> f (nonEmpty' vertex'))
-> UnboundedConvexRegionF r nonEmpty vertex
-> f (UnboundedConvexRegionF r nonEmpty' vertex')
chain

instance ( Traversable1 nonEmpty
         , Ixed (nonEmpty vertex)
         , IxValue (nonEmpty vertex) ~ vertex
         , IxValue (nonEmpty vertex') ~ vertex'
         , Index (nonEmpty vertex) ~ Int, Index (nonEmpty vertex') ~ Int
         ) => HasVertices (UnboundedConvexRegionF r nonEmpty vertex)
                          (UnboundedConvexRegionF r nonEmpty vertex') where
  vertices :: IndexedTraversal1
  (VertexIx (UnboundedConvexRegionF r nonEmpty vertex))
  (UnboundedConvexRegionF r nonEmpty vertex)
  (UnboundedConvexRegionF r nonEmpty vertex')
  (Vertex (UnboundedConvexRegionF r nonEmpty vertex))
  (Vertex (UnboundedConvexRegionF r nonEmpty vertex'))
vertices = (nonEmpty vertex -> f (nonEmpty vertex'))
-> UnboundedConvexRegionF r nonEmpty vertex
-> f (UnboundedConvexRegionF r nonEmpty vertex')
forall r (nonEmpty :: * -> *) vertex (nonEmpty' :: * -> *) vertex'
       (f :: * -> *).
Functor f =>
(nonEmpty vertex -> f (nonEmpty' vertex'))
-> UnboundedConvexRegionF r nonEmpty vertex
-> f (UnboundedConvexRegionF r nonEmpty' vertex')
chain ((nonEmpty vertex -> f (nonEmpty vertex'))
 -> UnboundedConvexRegionF r nonEmpty vertex
 -> f (UnboundedConvexRegionF r nonEmpty vertex'))
-> (p vertex (f vertex')
    -> nonEmpty vertex -> f (nonEmpty vertex'))
-> p vertex (f vertex')
-> UnboundedConvexRegionF r nonEmpty vertex
-> f (UnboundedConvexRegionF r nonEmpty vertex')
forall b c a. (b -> c) -> (a -> b) -> a -> c
.> p vertex (f vertex') -> nonEmpty vertex -> f (nonEmpty vertex')
forall (f :: * -> *) a b.
Traversable1 f =>
IndexedTraversal1 Int (f a) (f b) a b
IndexedTraversal1
  Int (nonEmpty vertex) (nonEmpty vertex') vertex vertex'
traversed1

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

instance ( Point_ vertex 2 r, Num r, Ord r
         , HyperPlane_ line 2 r
         , HalfLine vertex `HasIntersectionWith` HalfPlaneF line
         ) => HalfPlaneF line `HasIntersectionWith` UnboundedConvexRegionF r NonEmpty vertex where
  HalfPlaneF line
h intersects :: HalfPlaneF line -> UnboundedConvexRegionF r NonEmpty vertex -> Bool
`intersects` reg :: UnboundedConvexRegionF r NonEmpty vertex
reg@(Unbounded Vector 2 r
_ NonEmpty vertex
pts Vector 2 r
_) = (HalfLine vertex -> Bool) -> Vector 2 (HalfLine vertex) -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (HalfLine vertex -> HalfPlaneF line -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` HalfPlaneF line
h) (UnboundedConvexRegionF r NonEmpty vertex
-> Vector 2 (HalfLine vertex)
forall vertex r.
(Point_ vertex 2 r, Num r) =>
UnboundedConvexRegionF r NonEmpty vertex
-> Vector 2 (HalfLine vertex)
boundingRays UnboundedConvexRegionF r NonEmpty vertex
reg)
                                        Bool -> Bool -> Bool
|| Getting Any (NonEmpty vertex) (Point 2 r)
-> (Point 2 r -> Bool) -> NonEmpty vertex -> Bool
forall s a. Getting Any s a -> (a -> Bool) -> s -> Bool
anyOf ((vertex -> Const Any vertex)
-> NonEmpty vertex -> Const Any (NonEmpty vertex)
forall (f :: * -> *) a. Foldable f => IndexedFold Int (f a) a
IndexedFold Int (NonEmpty vertex) vertex
folded((vertex -> Const Any vertex)
 -> NonEmpty vertex -> Const Any (NonEmpty vertex))
-> ((Point 2 r -> Const Any (Point 2 r))
    -> vertex -> Const Any vertex)
-> Getting Any (NonEmpty vertex) (Point 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Const Any (Point 2 r)) -> vertex -> Const Any vertex
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' vertex (Point 2 r)
asPoint) (Point 2 r -> HalfPlaneF line -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` HalfPlaneF line
h) NonEmpty vertex
pts








-- -- | given a vertical line l through point (x,0) that intersects the unbounded convex region
-- -- intersect the convex region with the left halfplane of l.
-- intersectVerticalLeft :: r -> UnboundedConvexRegionF r nonEmpty vertex
--                            -> Either (UnboundedConvexRegionF r nonEmpty vertex)
--                                      (ConvexPolygonF (Cyclic NonEmpty) vertex)
-- intersectVerticalLeft x chain@(Chain v pts w) =
--   case (verticalLine x `intersect`) <$> boundingRays chain of
--     Vector2 Nothing Nothing


--------------------------------------------------------------------------------
-- * Intersection of a Point and a Unbounded Convex Polygon




instance (Point_ vertex 2 r, Ord r, Fractional r
         ) => Point 2 r `HasIntersectionWith` UnboundedConvexRegionF r NonEmpty vertex where
  Point 2 r
q intersects :: Point 2 r -> UnboundedConvexRegionF r NonEmpty vertex -> Bool
`intersects` UnboundedConvexRegionF r NonEmpty vertex
region = (HalfPlaneF (LinePV 2 r) -> Bool)
-> TwoOrThree (HalfPlaneF (LinePV 2 r)) -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Point 2 r
q Point 2 r -> HalfPlaneF (LinePV 2 r) -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects`) (UnboundedConvexRegionF r NonEmpty vertex
-> TwoOrThree (HalfPlaneF (LinePV 2 r))
forall vertex r.
(Point_ vertex 2 r, Num r, Ord r) =>
UnboundedConvexRegionF r NonEmpty vertex
-> TwoOrThree (HalfPlaneF (LinePV 2 r))
unboundedBoundingHalfplanes UnboundedConvexRegionF r NonEmpty vertex
region)
                       Bool -> Bool -> Bool
|| Point 2 r
q Point 2 r
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex)
-> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` UnboundedConvexRegionF r NonEmpty vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex)
forall (nonEmpty :: * -> *) vertex r.
(VertexContainer nonEmpty vertex, Point_ vertex 2 r,
 HasFromFoldable1 nonEmpty) =>
UnboundedConvexRegionF r nonEmpty vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic nonEmpty) vertex)
boundedCore UnboundedConvexRegionF r NonEmpty vertex
region

--------------------------------------------------------------------------------
-- * Intersection of a LineSegment with an Unbounded Convex Polygon

-- type instance Intersection (LineSegment endPoint point)
--                            (UnboundedConvexRegionF r nonEmpty vertex) =
--    Intersection (LineSegment endPoint point)
--                 (ConvexPolygonF (Cyclic nonEmpty) vertex)

-- data instance Intersection (LineSegment endPoint point)
--                            (ConvexPolygonF (Cyclic nonEmpty) vertex) =


instance (Point_ vertex 2 r, Ord r, Fractional r
         ) => LinePV 2 r
                `HasIntersectionWith` UnboundedConvexRegionF r NonEmpty vertex where
  LinePV 2 r
line intersects :: LinePV 2 r -> UnboundedConvexRegionF r NonEmpty vertex -> Bool
`intersects` UnboundedConvexRegionF r NonEmpty vertex
region = (HalfLine vertex -> Bool) -> Vector 2 (HalfLine vertex) -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
any (LinePV 2 r
line LinePV 2 r -> HalfLine vertex -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects`) (UnboundedConvexRegionF r NonEmpty vertex
-> Vector 2 (HalfLine vertex)
forall vertex r.
(Point_ vertex 2 r, Num r) =>
UnboundedConvexRegionF r NonEmpty vertex
-> Vector 2 (HalfLine vertex)
boundingRays UnboundedConvexRegionF r NonEmpty vertex
region)
                          Bool -> Bool -> Bool
|| LinePV 2 r
line LinePV 2 r
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex)
-> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` UnboundedConvexRegionF r NonEmpty vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex)
forall (nonEmpty :: * -> *) vertex r.
(VertexContainer nonEmpty vertex, Point_ vertex 2 r,
 HasFromFoldable1 nonEmpty) =>
UnboundedConvexRegionF r nonEmpty vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic nonEmpty) vertex)
boundedCore UnboundedConvexRegionF r NonEmpty vertex
region

-- | Intersection between a halfline and a unbounded convex region
data LineUnboundedConvexRegionIntersection r =
    Line_x_UnboundedConvexRegion_HalfLine    (HalfLine (Point 2 r))
  | Line_x_UnboundedConvexRegion_LineSegment (ClosedLineSegment (Point 2 r))
  | Line_x_UnboundedConvexRegion_Point       (Point 2 r)
  deriving (Int -> LineUnboundedConvexRegionIntersection r -> ShowS
[LineUnboundedConvexRegionIntersection r] -> ShowS
LineUnboundedConvexRegionIntersection r -> String
(Int -> LineUnboundedConvexRegionIntersection r -> ShowS)
-> (LineUnboundedConvexRegionIntersection r -> String)
-> ([LineUnboundedConvexRegionIntersection r] -> ShowS)
-> Show (LineUnboundedConvexRegionIntersection r)
forall r.
Show r =>
Int -> LineUnboundedConvexRegionIntersection r -> ShowS
forall r.
Show r =>
[LineUnboundedConvexRegionIntersection r] -> ShowS
forall r.
Show r =>
LineUnboundedConvexRegionIntersection r -> String
forall a.
(Int -> a -> ShowS) -> (a -> String) -> ([a] -> ShowS) -> Show a
$cshowsPrec :: forall r.
Show r =>
Int -> LineUnboundedConvexRegionIntersection r -> ShowS
showsPrec :: Int -> LineUnboundedConvexRegionIntersection r -> ShowS
$cshow :: forall r.
Show r =>
LineUnboundedConvexRegionIntersection r -> String
show :: LineUnboundedConvexRegionIntersection r -> String
$cshowList :: forall r.
Show r =>
[LineUnboundedConvexRegionIntersection r] -> ShowS
showList :: [LineUnboundedConvexRegionIntersection r] -> ShowS
Show,LineUnboundedConvexRegionIntersection r
-> LineUnboundedConvexRegionIntersection r -> Bool
(LineUnboundedConvexRegionIntersection r
 -> LineUnboundedConvexRegionIntersection r -> Bool)
-> (LineUnboundedConvexRegionIntersection r
    -> LineUnboundedConvexRegionIntersection r -> Bool)
-> Eq (LineUnboundedConvexRegionIntersection r)
forall r.
Eq r =>
LineUnboundedConvexRegionIntersection r
-> LineUnboundedConvexRegionIntersection r -> Bool
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
$c== :: forall r.
Eq r =>
LineUnboundedConvexRegionIntersection r
-> LineUnboundedConvexRegionIntersection r -> Bool
== :: LineUnboundedConvexRegionIntersection r
-> LineUnboundedConvexRegionIntersection r -> Bool
$c/= :: forall r.
Eq r =>
LineUnboundedConvexRegionIntersection r
-> LineUnboundedConvexRegionIntersection r -> Bool
/= :: LineUnboundedConvexRegionIntersection r
-> LineUnboundedConvexRegionIntersection r -> Bool
Eq)

instance (Ord r, Num r
         ) => Point 2 r `HasIntersectionWith` LineUnboundedConvexRegionIntersection r where
  intersects :: Point 2 r -> LineUnboundedConvexRegionIntersection r -> Bool
intersects Point 2 r
q = \case
    Line_x_UnboundedConvexRegion_HalfLine    HalfLine (Point 2 r)
hl  -> Point 2 r
q Point 2 r -> HalfLine (Point 2 r) -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` HalfLine (Point 2 r)
hl
    Line_x_UnboundedConvexRegion_LineSegment ClosedLineSegment (Point 2 r)
seg -> Point 2 r
q Point 2 r -> ClosedLineSegment (Point 2 r) -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` ClosedLineSegment (Point 2 r)
seg
    Line_x_UnboundedConvexRegion_Point       Point 2 r
p   -> Point 2 r
p Point 2 r -> Point 2 r -> Bool
forall a. Eq a => a -> a -> Bool
== Point 2 r
q


type instance Intersection (LinePV 2 r) (UnboundedConvexRegionF r nonEmpty vertex) =
  Maybe (LineUnboundedConvexRegionIntersection r)





-- boundingRayIntersections line rays = case withIntersection <$> rays of

--   where
--     withIntersection ray = (,ray) <$> line `intersect` ray

-- withIntersection <$> boundingRays

instance (Point_ vertex 2 r, Ord r, Fractional r
         ) => LinePV 2 r
                `IsIntersectableWith` UnboundedConvexRegionF r NonEmpty vertex where
  LinePV 2 r
line intersect :: LinePV 2 r
-> UnboundedConvexRegionF r NonEmpty vertex
-> Intersection
     (LinePV 2 r) (UnboundedConvexRegionF r NonEmpty vertex)
`intersect` UnboundedConvexRegionF r NonEmpty vertex
region = case HalfLine vertex
-> Maybe
     (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
withIntersection (HalfLine vertex
 -> Maybe
      (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))))
-> Vector 2 (HalfLine vertex)
-> Vector
     2
     (Maybe
        (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))))
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> UnboundedConvexRegionF r NonEmpty vertex
-> Vector 2 (HalfLine vertex)
forall vertex r.
(Point_ vertex 2 r, Num r) =>
UnboundedConvexRegionF r NonEmpty vertex
-> Vector 2 (HalfLine vertex)
boundingRays UnboundedConvexRegionF r NonEmpty vertex
region of
      -- somehow both rays intersect the line
      Vector2 (Just LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))
ps) (Just LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))
qs) -> LineUnboundedConvexRegionIntersection r
-> Maybe (LineUnboundedConvexRegionIntersection r)
forall a. a -> Maybe a
Just (LineUnboundedConvexRegionIntersection r
 -> Maybe (LineUnboundedConvexRegionIntersection r))
-> LineUnboundedConvexRegionIntersection r
-> Maybe (LineUnboundedConvexRegionIntersection r)
forall a b. (a -> b) -> a -> b
$ case LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))
ps of
        Line_x_HalfLine_HalfLine HalfLine (Point 2 r)
hl -> HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r
forall r.
HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_HalfLine HalfLine (Point 2 r)
hl
        Line_x_HalfLine_Point Point 2 r
p     -> case LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))
qs of
          Line_x_HalfLine_HalfLine HalfLine (Point 2 r)
hl         -> HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r
forall r.
HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_HalfLine HalfLine (Point 2 r)
hl
          Line_x_HalfLine_Point Point 2 r
q | Point 2 r
p Point 2 r -> Point 2 r -> Bool
forall a. Eq a => a -> a -> Bool
== Point 2 r
q    -> Point 2 r -> LineUnboundedConvexRegionIntersection r
forall r. Point 2 r -> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_Point Point 2 r
p
                                  | Bool
otherwise -> ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
forall r.
ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_LineSegment
                                                   (ClosedLineSegment (Point 2 r)
 -> LineUnboundedConvexRegionIntersection r)
-> ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
forall a b. (a -> b) -> a -> b
$ Point 2 r -> Point 2 r -> ClosedLineSegment (Point 2 r)
forall point. point -> point -> ClosedLineSegment point
ClosedLineSegment Point 2 r
p Point 2 r
q

      -- the rays do not intersect the line
      Vector2 Maybe (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
Nothing Maybe (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
Nothing                 -> Maybe
  (PossiblyDegenerateSegment
     (Point 2 r) (ClosedLineSegment (Point 2 r)))
Intersection
  (LinePV 2 r)
  (PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex))
boundedIntersection Maybe
  (PossiblyDegenerateSegment
     (Point 2 r) (ClosedLineSegment (Point 2 r)))
-> (PossiblyDegenerateSegment
      (Point 2 r) (ClosedLineSegment (Point 2 r))
    -> LineUnboundedConvexRegionIntersection r)
-> Maybe (LineUnboundedConvexRegionIntersection r)
forall (f :: * -> *) a b. Functor f => f a -> (a -> b) -> f b
<&> \case
         SinglePoint Point 2 r
p     -> Point 2 r -> LineUnboundedConvexRegionIntersection r
forall r. Point 2 r -> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_Point Point 2 r
p
         ActualSegment ClosedLineSegment (Point 2 r)
seg -> ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
forall r.
ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_LineSegment ClosedLineSegment (Point 2 r)
seg

      -- exactly one ray intersects the line
      Vector2 Maybe (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
ps Maybe (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
Nothing               -> LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))
-> LineUnboundedConvexRegionIntersection r
intersectBounded (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))
 -> LineUnboundedConvexRegionIntersection r)
-> Maybe
     (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
-> Maybe (LineUnboundedConvexRegionIntersection r)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
ps
      Vector2 Maybe (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
Nothing  Maybe (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
qs              -> LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))
-> LineUnboundedConvexRegionIntersection r
intersectBounded (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))
 -> LineUnboundedConvexRegionIntersection r)
-> Maybe
     (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
-> Maybe (LineUnboundedConvexRegionIntersection r)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Maybe (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
qs
    where
      withIntersection                :: HalfLine vertex
                                      -> Maybe (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))

                                               )
      withIntersection :: HalfLine vertex
-> Maybe
     (LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r)))
withIntersection (HalfLine vertex
p Vector (Dimension vertex) (NumType vertex)
v) = let ray :: HalfLine (Point 2 r)
ray = Point 2 r
-> Vector (Dimension (Point 2 r)) (NumType (Point 2 r))
-> HalfLine (Point 2 r)
forall point.
point -> Vector (Dimension point) (NumType point) -> HalfLine point
HalfLine (vertex
pvertex -> Getting (Point 2 r) vertex (Point 2 r) -> Point 2 r
forall s a. s -> Getting a s a -> a
^.Getting (Point 2 r) vertex (Point 2 r)
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' vertex (Point 2 r)
asPoint) Vector (Dimension vertex) (NumType vertex)
Vector (Dimension (Point 2 r)) (NumType (Point 2 r))
v
                                        in LinePV 2 r
line LinePV 2 r
-> HalfLine (Point 2 r)
-> Intersection (LinePV 2 r) (HalfLine (Point 2 r))
forall g h. IsIntersectableWith g h => g -> h -> Intersection g h
`intersect` HalfLine (Point 2 r)
ray

      boundedIntersection :: Intersection
  (LinePV 2 r)
  (PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex))
boundedIntersection = LinePV 2 r
line LinePV 2 r
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex)
-> Intersection
     (LinePV 2 r)
     (PossiblyDegenerateSimplePolygon
        vertex (ConvexPolygonF (Cyclic NonEmpty) vertex))
forall g h. IsIntersectableWith g h => g -> h -> Intersection g h
`intersect` UnboundedConvexRegionF r NonEmpty vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex)
forall (nonEmpty :: * -> *) vertex r.
(VertexContainer nonEmpty vertex, Point_ vertex 2 r,
 HasFromFoldable1 nonEmpty) =>
UnboundedConvexRegionF r nonEmpty vertex
-> PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic nonEmpty) vertex)
boundedCore UnboundedConvexRegionF r NonEmpty vertex
region

      intersectBounded :: LineHalfLineIntersection (Point 2 r) (HalfLine (Point 2 r))
-> LineUnboundedConvexRegionIntersection r
intersectBounded = \case
          Line_x_HalfLine_HalfLine HalfLine (Point 2 r)
l  -> HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r
forall r.
HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_HalfLine HalfLine (Point 2 r)
l
          Line_x_HalfLine_Point Point 2 r
p     -> case Intersection
  (LinePV 2 r)
  (PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex))
boundedIntersection of
                Maybe
  (PossiblyDegenerateSegment
     (Point 2 r) (ClosedLineSegment (Point 2 r)))
Intersection
  (LinePV 2 r)
  (PossiblyDegenerateSimplePolygon
     vertex (ConvexPolygonF (Cyclic NonEmpty) vertex))
Nothing                   -> HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r
forall r.
HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_HalfLine (HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r)
-> HalfLine (Point 2 r) -> LineUnboundedConvexRegionIntersection r
forall a b. (a -> b) -> a -> b
$ Point 2 r -> HalfLine (Point 2 r)
hl Point 2 r
p
                Just (SinglePoint Point 2 r
q)      -> ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
forall r.
ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_LineSegment (ClosedLineSegment (Point 2 r)
 -> LineUnboundedConvexRegionIntersection r)
-> ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
forall a b. (a -> b) -> a -> b
$
                                               Point 2 r -> Point 2 r -> ClosedLineSegment (Point 2 r)
forall point. point -> point -> ClosedLineSegment point
ClosedLineSegment Point 2 r
p Point 2 r
q
                Just (ActualSegment ClosedLineSegment (Point 2 r)
seg)  -> let q :: Point 2 r
q   = (Point 2 r -> Point 2 r -> Ordering)
-> ClosedLineSegment (Point 2 r) -> Point 2 r
forall (t :: * -> *) a.
Foldable1 t =>
(a -> a -> Ordering) -> t a -> a
maximumBy Point 2 r -> Point 2 r -> Ordering
cmp ClosedLineSegment (Point 2 r)
seg
                                                 cmp :: Point 2 r -> Point 2 r -> Ordering
cmp = (Point 2 r -> r) -> Point 2 r -> Point 2 r -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing (Point 2 r -> Point 2 r -> r
forall r point (d :: Nat) point'.
(Num r, Point_ point d r, Point_ point' d r,
 Metric_ (Vector d r) d r) =>
point -> point' -> r
squaredEuclideanDist Point 2 r
p)
                                                 res :: ClosedLineSegment (Point 2 r)
res = Point 2 r -> Point 2 r -> ClosedLineSegment (Point 2 r)
forall point. point -> point -> ClosedLineSegment point
ClosedLineSegment Point 2 r
p Point 2 r
q
                                             in ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
forall r.
ClosedLineSegment (Point 2 r)
-> LineUnboundedConvexRegionIntersection r
Line_x_UnboundedConvexRegion_LineSegment ClosedLineSegment (Point 2 r)
res
                                     -- the closest endpoint of seg must lie on
                                     -- the dummy edge of the core (connecting the two extremal)
                                     -- vertices of the chain
        where
          -- | given an intersection point p on one of the unbounded rays, compute
          -- the halfline that is contained in the unbounded region.
          hl :: Point 2 r -> HalfLine (Point 2 r)
hl Point 2 r
p = let v :: Vector 2 r
v       = LinePV 2 r
lineLinePV 2 r
-> Getting (Vector 2 r) (LinePV 2 r) (Vector 2 r) -> Vector 2 r
forall s a. s -> Getting a s a -> a
^.Getting (Vector 2 r) (LinePV 2 r) (Vector 2 r)
forall (d :: Nat) r.
(Dimension (LinePV 2 r) ~ d, NumType (LinePV 2 r) ~ r) =>
Lens' (LinePV 2 r) (Vector d r)
forall t (d :: Nat) r.
(HasDirection t, Dimension t ~ d, NumType t ~ r) =>
Lens' t (Vector d r)
Lens' (LinePV 2 r) (Vector 2 r)
direction
                     region' :: TwoOrThree (HalfPlaneF (LinePV 2 r))
region' = UnboundedConvexRegionF r NonEmpty vertex
-> TwoOrThree (HalfPlaneF (LinePV 2 r))
forall vertex r.
(Point_ vertex 2 r, Num r, Ord r) =>
UnboundedConvexRegionF r NonEmpty vertex
-> TwoOrThree (HalfPlaneF (LinePV 2 r))
unboundedBoundingHalfplanes UnboundedConvexRegionF r NonEmpty vertex
region
                     v' :: Vector 2 r
v'      = if (HalfPlaneF (LinePV 2 r) -> Bool)
-> TwoOrThree (HalfPlaneF (LinePV 2 r)) -> Bool
forall (t :: * -> *) a. Foldable t => (a -> Bool) -> t a -> Bool
all (Point 2 r
p Point 2 r -> Vector 2 r -> Point 2 r
forall point (d :: Nat) r.
(Affine_ point d r, Num r) =>
point -> Vector d r -> point
.+^ Vector 2 r
v Point 2 r -> HalfPlaneF (LinePV 2 r) -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects`) TwoOrThree (HalfPlaneF (LinePV 2 r))
region' then Vector 2 r
v else Vector 2 r -> Vector 2 r
forall r vector (d :: Nat).
(Num r, Vector_ vector d r) =>
vector -> vector
negated Vector 2 r
v
                  in Point 2 r
-> Vector (Dimension (Point 2 r)) (NumType (Point 2 r))
-> HalfLine (Point 2 r)
forall point.
point -> Vector (Dimension point) (NumType point) -> HalfLine point
HalfLine Point 2 r
p Vector 2 r
Vector (Dimension (Point 2 r)) (NumType (Point 2 r))
v'
                  -- if the point along v lies inside the (the unbounded part of the) region
                  -- use direction v, otherwise use direction v'.
                  -- note that since the intersection is guaranteed to be a halfline
                  -- this remainder of the halflien should lie in the unbounded part

instance ( Point_ vertex 2 r, Point_ point 2 r, Ord r, Fractional r
         , IxValue (endPoint point) ~ point, EndPoint_ (endPoint point)
         , HasOnSegment        (LineSegment endPoint point) 2
         , HasIntersectionWith (ClosedLineSegment (Point 2 r)) (LineSegment endPoint point)
         , HasIntersectionWith (HalfLine (Point 2 r))          (LineSegment endPoint point)
         ) => LineSegment endPoint point
                `HasIntersectionWith` UnboundedConvexRegionF r NonEmpty vertex where
  LineSegment endPoint point
seg intersects :: LineSegment endPoint point
-> UnboundedConvexRegionF r NonEmpty vertex -> Bool
`intersects` UnboundedConvexRegionF r NonEmpty vertex
region = case LineSegment endPoint point
-> LinePV
     (Dimension (LineSegment endPoint point))
     (NumType (LineSegment endPoint point))
forall t.
HasSupportingLine t =>
t -> LinePV (Dimension t) (NumType t)
supportingLine LineSegment endPoint point
seg LinePV 2 r
-> UnboundedConvexRegionF r NonEmpty vertex
-> Intersection
     (LinePV 2 r) (UnboundedConvexRegionF r NonEmpty vertex)
forall g h. IsIntersectableWith g h => g -> h -> Intersection g h
`intersect` UnboundedConvexRegionF r NonEmpty vertex
region of
      Maybe (LineUnboundedConvexRegionIntersection r)
Intersection
  (LinePV 2 r) (UnboundedConvexRegionF r NonEmpty vertex)
Nothing     -> Bool
False
      Just LineUnboundedConvexRegionIntersection r
inters -> case LineUnboundedConvexRegionIntersection r
inters of
        Line_x_UnboundedConvexRegion_Point Point 2 r
p          -> Point 2 r
p    Point 2 r -> LineSegment endPoint point -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` LineSegment endPoint point
seg
        Line_x_UnboundedConvexRegion_LineSegment ClosedLineSegment (Point 2 r)
seg' -> ClosedLineSegment (Point 2 r)
seg' ClosedLineSegment (Point 2 r) -> LineSegment endPoint point -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` LineSegment endPoint point
seg
        Line_x_UnboundedConvexRegion_HalfLine  HalfLine (Point 2 r)
hl     ->
          (LineSegment endPoint point
segLineSegment endPoint point
-> Getting (Point 2 r) (LineSegment endPoint point) (Point 2 r)
-> Point 2 r
forall s a. s -> Getting a s a -> a
^.(point -> Const (Point 2 r) point)
-> LineSegment endPoint point
-> Const (Point 2 r) (LineSegment endPoint point)
forall seg p. HasStart seg p => Lens' seg p
Lens' (LineSegment endPoint point) point
start((point -> Const (Point 2 r) point)
 -> LineSegment endPoint point
 -> Const (Point 2 r) (LineSegment endPoint point))
-> ((Point 2 r -> Const (Point 2 r) (Point 2 r))
    -> point -> Const (Point 2 r) point)
-> Getting (Point 2 r) (LineSegment endPoint point) (Point 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Const (Point 2 r) (Point 2 r))
-> point -> Const (Point 2 r) point
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' point (Point 2 r)
asPoint) Point 2 r -> HalfLine (Point 2 r) -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` HalfLine (Point 2 r)
hl Bool -> Bool -> Bool
|| (LineSegment endPoint point
segLineSegment endPoint point
-> Getting (Point 2 r) (LineSegment endPoint point) (Point 2 r)
-> Point 2 r
forall s a. s -> Getting a s a -> a
^.(point -> Const (Point 2 r) point)
-> LineSegment endPoint point
-> Const (Point 2 r) (LineSegment endPoint point)
forall seg p. HasEnd seg p => Lens' seg p
Lens' (LineSegment endPoint point) point
end((point -> Const (Point 2 r) point)
 -> LineSegment endPoint point
 -> Const (Point 2 r) (LineSegment endPoint point))
-> ((Point 2 r -> Const (Point 2 r) (Point 2 r))
    -> point -> Const (Point 2 r) point)
-> Getting (Point 2 r) (LineSegment endPoint point) (Point 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Const (Point 2 r) (Point 2 r))
-> point -> Const (Point 2 r) point
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' point (Point 2 r)
asPoint) Point 2 r -> HalfLine (Point 2 r) -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` HalfLine (Point 2 r)
hl
            -- this is essentially the simplified version of 'hl `intersects` seg'
            -- as we already know they are colinear

--------------------------------------------------------------------------------
-- * Intersection of a Triangle with an Unbounded Convex Polygon

type instance Intersection (Triangle corner) (UnboundedConvexRegionF r nonEmpty vertex)
  = Intersection (Triangle corner) (ConvexPolygonF (Cyclic nonEmpty) vertex)

instance (Point_ vertex 2 r, Point_ corner 2 r, Ord r, Fractional r
         ) => Triangle corner `HasIntersectionWith` UnboundedConvexRegionF r NonEmpty vertex where
  Triangle corner
tri intersects :: Triangle corner -> UnboundedConvexRegionF r NonEmpty vertex -> Bool
`intersects` UnboundedConvexRegionF r NonEmpty vertex
region =
       Getting Any (UnboundedConvexRegionF r NonEmpty vertex) (Point 2 r)
-> (Point 2 r -> Bool)
-> UnboundedConvexRegionF r NonEmpty vertex
-> Bool
forall s a. Getting Any s a -> (a -> Bool) -> s -> Bool
anyOf ((vertex -> Const Any vertex)
-> UnboundedConvexRegionF r NonEmpty vertex
-> Const Any (UnboundedConvexRegionF r NonEmpty vertex)
(Vertex (UnboundedConvexRegionF r NonEmpty vertex)
 -> Const Any (Vertex (UnboundedConvexRegionF r NonEmpty vertex)))
-> UnboundedConvexRegionF r NonEmpty vertex
-> Const Any (UnboundedConvexRegionF r NonEmpty vertex)
forall graph graph'.
HasVertices graph graph' =>
IndexedTraversal1
  (VertexIx graph) graph graph' (Vertex graph) (Vertex graph')
IndexedTraversal1
  (VertexIx (UnboundedConvexRegionF r NonEmpty vertex))
  (UnboundedConvexRegionF r NonEmpty vertex)
  (UnboundedConvexRegionF r NonEmpty vertex)
  (Vertex (UnboundedConvexRegionF r NonEmpty vertex))
  (Vertex (UnboundedConvexRegionF r NonEmpty vertex))
vertices((vertex -> Const Any vertex)
 -> UnboundedConvexRegionF r NonEmpty vertex
 -> Const Any (UnboundedConvexRegionF r NonEmpty vertex))
-> ((Point 2 r -> Const Any (Point 2 r))
    -> vertex -> Const Any vertex)
-> Getting
     Any (UnboundedConvexRegionF r NonEmpty vertex) (Point 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Const Any (Point 2 r)) -> vertex -> Const Any vertex
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' vertex (Point 2 r)
asPoint) (Point 2 r -> Triangle corner -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` Triangle corner
tri) UnboundedConvexRegionF r NonEmpty vertex
region
    Bool -> Bool -> Bool
|| Getting Any (Triangle corner) (Point 2 r)
-> (Point 2 r -> Bool) -> Triangle corner -> Bool
forall s a. Getting Any s a -> (a -> Bool) -> s -> Bool
anyOf ((corner -> Const Any corner)
-> Triangle corner -> Const Any (Triangle corner)
(Vertex (Triangle corner) -> Const Any (Vertex (Triangle corner)))
-> Triangle corner -> Const Any (Triangle corner)
forall graph graph'.
HasVertices graph graph' =>
IndexedTraversal1
  (VertexIx graph) graph graph' (Vertex graph) (Vertex graph')
IndexedTraversal1
  (VertexIx (Triangle corner))
  (Triangle corner)
  (Triangle corner)
  (Vertex (Triangle corner))
  (Vertex (Triangle corner))
vertices((corner -> Const Any corner)
 -> Triangle corner -> Const Any (Triangle corner))
-> ((Point 2 r -> Const Any (Point 2 r))
    -> corner -> Const Any corner)
-> Getting Any (Triangle corner) (Point 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Const Any (Point 2 r)) -> corner -> Const Any corner
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' corner (Point 2 r)
asPoint) (Point 2 r -> UnboundedConvexRegionF r NonEmpty vertex -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` UnboundedConvexRegionF r NonEmpty vertex
region) Triangle corner
tri
    Bool -> Bool -> Bool
|| Getting Any (Triangle (Point 2 r)) (ClosedLineSegment (Point 2 r))
-> (ClosedLineSegment (Point 2 r) -> Bool)
-> Triangle (Point 2 r)
-> Bool
forall s a. Getting Any s a -> (a -> Bool) -> s -> Bool
anyOf Getting Any (Triangle (Point 2 r)) (ClosedLineSegment (Point 2 r))
forall polygon point r.
(HasOuterBoundary polygon, Vertex polygon ~ point,
 Point_ point 2 r) =>
IndexedFold1
  (VertexIx polygon, VertexIx polygon)
  polygon
  (ClosedLineSegment point)
IndexedFold1
  (VertexIx (Triangle (Point 2 r)), VertexIx (Triangle (Point 2 r)))
  (Triangle (Point 2 r))
  (ClosedLineSegment (Point 2 r))
outerBoundaryEdgeSegments (ClosedLineSegment (Point 2 r)
-> UnboundedConvexRegionF r NonEmpty vertex -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` UnboundedConvexRegionF r NonEmpty vertex
region) (Getting (Point 2 r) corner (Point 2 r) -> corner -> Point 2 r
forall s (m :: * -> *) a. MonadReader s m => Getting a s a -> m a
view Getting (Point 2 r) corner (Point 2 r)
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' corner (Point 2 r)
asPoint (corner -> Point 2 r) -> Triangle corner -> Triangle (Point 2 r)
forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> Triangle corner
tri)



instance ( Point_ vertex 2 r, Point_ corner 2 r, Ord r, Fractional r
         ) => Triangle corner `IsIntersectableWith` UnboundedConvexRegionF r NonEmpty vertex where
  Triangle corner
tri intersect :: Triangle corner
-> UnboundedConvexRegionF r NonEmpty vertex
-> Intersection
     (Triangle corner) (UnboundedConvexRegionF r NonEmpty vertex)
`intersect` UnboundedConvexRegionF r NonEmpty vertex
region = Triangle corner
tri Triangle corner
-> ConvexPolygonF (Cyclic NonEmpty) vertex
-> Intersection
     (Triangle corner) (ConvexPolygonF (Cyclic NonEmpty) vertex)
forall g h. IsIntersectableWith g h => g -> h -> Intersection g h
`intersect` Triangle corner
-> UnboundedConvexRegionF r NonEmpty vertex
-> ConvexPolygonF (Cyclic NonEmpty) vertex
forall (nonEmpty :: * -> *) point r vertex.
(Foldable nonEmpty, Point_ point 2 r, Point_ vertex 2 r, Ord r,
 Fractional r) =>
nonEmpty point
-> UnboundedConvexRegionF r NonEmpty vertex
-> ConvexPolygonF (Cyclic NonEmpty) vertex
toBoundedFrom Triangle corner
tri UnboundedConvexRegionF r NonEmpty vertex
region

-- | Given some convex shape S, construct some "big enough" convex polygon B out of the
-- unbounded convex polygon U so that the intersection \(U \cap S\) is the same as \(B
-- \cap S\)
--
-- note: this creates some new vertices; which are "copies" from the extremal vertices.
-- this is to avoid having to introduce yet another level of 'OriginalOrExtra''s
toBoundedFrom :: (Foldable nonEmpty, Point_ point 2 r, Point_ vertex 2 r, Ord r, Fractional r)
              => nonEmpty point -> UnboundedConvexRegionF r NonEmpty vertex
              -> ConvexPolygonF (Cyclic NonEmpty) vertex
toBoundedFrom :: forall (nonEmpty :: * -> *) point r vertex.
(Foldable nonEmpty, Point_ point 2 r, Point_ vertex 2 r, Ord r,
 Fractional r) =>
nonEmpty point
-> UnboundedConvexRegionF r NonEmpty vertex
-> ConvexPolygonF (Cyclic NonEmpty) vertex
toBoundedFrom nonEmpty point
tri reg :: UnboundedConvexRegionF r NonEmpty vertex
reg@(Unbounded Vector 2 r
v NonEmpty vertex
pts Vector 2 r
w) = Vector 2 vertex -> ConvexPolygonF (Cyclic NonEmpty) vertex
go (Vector 2 vertex -> ConvexPolygonF (Cyclic NonEmpty) vertex)
-> Vector 2 vertex -> ConvexPolygonF (Cyclic NonEmpty) vertex
forall a b. (a -> b) -> a -> b
$ case UnboundedConvexRegionF r NonEmpty vertex
-> Either vertex (Vector 2 vertex)
forall r vertex.
UnboundedConvexRegionF r NonEmpty vertex
-> Either vertex (Vector 2 vertex)
extremalVertices UnboundedConvexRegionF r NonEmpty vertex
reg of
                                                   Left vertex
p    -> vertex -> vertex -> Vector 2 vertex
forall r. r -> r -> Vector 2 r
Vector2 vertex
p vertex
p
                                                   Right Vector 2 vertex
vec -> Vector 2 vertex
vec

  where
    -- the main idea is to compute the line through two points on the boundary of the of
    -- halflines bounding the region, and consider the halfplane h that is bounded by this
    -- line l and contains the vertices of the unbounded region. We now find the furthest
    -- point pt from h (among the points in tri), and construct a line l' through this
    -- furthest point. It follows all points in tri lie "right" of this line (on the same
    -- side as the vertices of our unbounded region). Hence, we can safely clip the region
    -- using this line l'. (So we compute the intersection point between the two bounding
    -- rays and l') to find the two additional vertices a and b that we have to insert.

    go :: Vector 2 vertex -> ConvexPolygonF (Cyclic NonEmpty) vertex
go (Vector2 vertex
p vertex
q) = NonEmpty vertex -> ConvexPolygonF (Cyclic NonEmpty) vertex
forall simplePolygon point r (f :: * -> *).
(SimplePolygon_ simplePolygon point r, Foldable1 f) =>
f point -> simplePolygon
forall (f :: * -> *).
Foldable1 f =>
f vertex -> ConvexPolygonF (Cyclic NonEmpty) vertex
uncheckedFromCCWPoints (NonEmpty vertex -> ConvexPolygonF (Cyclic NonEmpty) vertex)
-> NonEmpty vertex -> ConvexPolygonF (Cyclic NonEmpty) vertex
forall a b. (a -> b) -> a -> b
$ vertex
b vertex -> NonEmpty vertex -> NonEmpty vertex
forall a. a -> NonEmpty a -> NonEmpty a
NonEmpty.<| vertex
a vertex -> NonEmpty vertex -> NonEmpty vertex
forall a. a -> NonEmpty a -> NonEmpty a
NonEmpty.<| NonEmpty vertex
pts
      where
        l :: LinePV 2 r
l  = vertex -> vertex -> LinePV 2 r
forall line point (d :: Nat) r.
(Line_ line d r, Point_ point d r, Num r) =>
point -> point -> line
lineThrough (vertex
p vertex -> Vector 2 r -> vertex
forall point (d :: Nat) r.
(Affine_ point d r, Num r) =>
point -> Vector d r -> point
.-^ Vector 2 r
v) (vertex
q vertex -> Vector 2 r -> vertex
forall point (d :: Nat) r.
(Affine_ point d r, Num r) =>
point -> Vector d r -> point
.+^ Vector 2 r
w) :: LinePV 2 _
        h' :: HalfSpaceF (LinePV 2 r)
h' = Sign -> LinePV 2 r -> HalfSpaceF (LinePV 2 r)
forall boundingHyperPlane.
Sign -> boundingHyperPlane -> HalfSpaceF boundingHyperPlane
HalfSpace Sign
Negative LinePV 2 r
l
        h :: HalfSpaceF (LinePV 2 r)
h  = if Point 2 r
q' Point 2 r -> HalfSpaceF (LinePV 2 r) -> Bool
forall g h. HasIntersectionWith g h => g -> h -> Bool
`intersects` HalfSpaceF (LinePV 2 r)
h' then HalfSpaceF (LinePV 2 r)
h'HalfSpaceF (LinePV 2 r)
-> (HalfSpaceF (LinePV 2 r) -> HalfSpaceF (LinePV 2 r))
-> HalfSpaceF (LinePV 2 r)
forall a b. a -> (a -> b) -> b
&(Sign -> Identity Sign)
-> HalfSpaceF (LinePV 2 r) -> Identity (HalfSpaceF (LinePV 2 r))
forall halfSpace (d :: Nat) r.
HalfSpace_ halfSpace d r =>
Lens' halfSpace Sign
Lens' (HalfSpaceF (LinePV 2 r)) Sign
halfSpaceSign ((Sign -> Identity Sign)
 -> HalfSpaceF (LinePV 2 r) -> Identity (HalfSpaceF (LinePV 2 r)))
-> Sign -> HalfSpaceF (LinePV 2 r) -> HalfSpaceF (LinePV 2 r)
forall s t a b. ASetter s t a b -> b -> s -> t
.~ Sign
Positive else HalfSpaceF (LinePV 2 r)
h'
        q' :: Point 2 r
q' = (vertex
q vertex -> Vector 2 r -> vertex
forall point (d :: Nat) r.
(Affine_ point d r, Num r) =>
point -> Vector d r -> point
.+^ (Vector 2 r
w Vector 2 r -> Vector 2 r -> Vector 2 r
forall r vector (d :: Nat).
(Num r, Additive_ vector d r) =>
vector -> vector -> vector
^+^ Vector 2 r
w))vertex -> Getting (Point 2 r) vertex (Point 2 r) -> Point 2 r
forall s a. s -> Getting a s a -> a
^.Getting (Point 2 r) vertex (Point 2 r)
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' vertex (Point 2 r)
asPoint
          -- make sure that there is at least one point outside the halfplane
        pt :: Point 2 r
pt = (Point 2 r -> r) -> NonEmpty (Point 2 r) -> Point 2 r
forall {t :: * -> *} {a} {a}.
(Foldable1 t, Ord a) =>
(a -> a) -> t a -> a
maximumOn (Point 2 r -> HalfSpaceF (LinePV 2 r) -> r
forall g r (d :: Nat) point.
(HasSquaredEuclideanDistance g, r ~ NumType g, d ~ Dimension g,
 Num r, Point_ point d r) =>
point -> g -> r
forall r (d :: Nat) point.
(r ~ NumType (HalfSpaceF (LinePV 2 r)),
 d ~ Dimension (HalfSpaceF (LinePV 2 r)), Num r,
 Point_ point d r) =>
point -> HalfSpaceF (LinePV 2 r) -> r
`squaredEuclideanDistTo` HalfSpaceF (LinePV 2 r)
h) (Point 2 r
q' Point 2 r -> [Point 2 r] -> NonEmpty (Point 2 r)
forall a. a -> [a] -> NonEmpty a
:| nonEmpty point
trinonEmpty point
-> Getting (Endo [Point 2 r]) (nonEmpty point) (Point 2 r)
-> [Point 2 r]
forall s a. s -> Getting (Endo [a]) s a -> [a]
^..(point -> Const (Endo [Point 2 r]) point)
-> nonEmpty point -> Const (Endo [Point 2 r]) (nonEmpty point)
forall (f :: * -> *) a. Foldable f => IndexedFold Int (f a) a
IndexedFold Int (nonEmpty point) point
folded((point -> Const (Endo [Point 2 r]) point)
 -> nonEmpty point -> Const (Endo [Point 2 r]) (nonEmpty point))
-> ((Point 2 r -> Const (Endo [Point 2 r]) (Point 2 r))
    -> point -> Const (Endo [Point 2 r]) point)
-> Getting (Endo [Point 2 r]) (nonEmpty point) (Point 2 r)
forall b c a. (b -> c) -> (a -> b) -> a -> c
.(Point 2 r -> Const (Endo [Point 2 r]) (Point 2 r))
-> point -> Const (Endo [Point 2 r]) point
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' point (Point 2 r)
asPoint)
          -- the furthest point in the direction perpendicular to the halfplane
        l' :: LinePV 2 r
l' = LinePV 2 r
lLinePV 2 r -> (LinePV 2 r -> LinePV 2 r) -> LinePV 2 r
forall a b. a -> (a -> b) -> b
&(Point 2 r -> Identity (Point 2 r))
-> LinePV 2 r -> Identity (LinePV 2 r)
forall (d :: Nat) r (f :: * -> *).
Functor f =>
(Point d r -> f (Point d r)) -> LinePV d r -> f (LinePV d r)
anchorPoint ((Point 2 r -> Identity (Point 2 r))
 -> LinePV 2 r -> Identity (LinePV 2 r))
-> Point 2 r -> LinePV 2 r -> LinePV 2 r
forall s t a b. ASetter s t a b -> b -> s -> t
.~ (Point 2 r
pt Point 2 r -> Vector 2 r -> Point 2 r
forall point (d :: Nat) r.
(Affine_ point d r, Num r) =>
point -> Vector d r -> point
.+^ Vector 2 r
w) -- move even a bit further to make sure
                                         -- that the new vertices (a,b) we get are strictly
                                         -- outside the input triangle tri
        a :: vertex
a  = vertex
-> Vector (Dimension vertex) (NumType vertex)
-> LinePV 2 r
-> vertex
forall {b} {h} {line}.
(Intersection (LinePV (Dimension b) (NumType b)) h
 ~ Maybe (LineLineIntersectionG (NumType b) line),
 Assert
   (OrdCond (CmpNat 1 (Dimension b)) 'True 'True 'False)
   (TypeError ...),
 Assert
   (OrdCond (CmpNat 2 (Dimension b)) 'True 'True 'False)
   (TypeError ...),
 IsIntersectableWith (LinePV (Dimension b) (NumType b)) h,
 Point_ b (Dimension b) (NumType b)) =>
b -> Vector (Dimension b) (NumType b) -> h -> b
intersectionPoint vertex
p Vector 2 r
Vector (Dimension vertex) (NumType vertex)
v LinePV 2 r
l' -- no need to negate v here
        b :: vertex
b  = vertex
-> Vector (Dimension vertex) (NumType vertex)
-> LinePV 2 r
-> vertex
forall {b} {h} {line}.
(Intersection (LinePV (Dimension b) (NumType b)) h
 ~ Maybe (LineLineIntersectionG (NumType b) line),
 Assert
   (OrdCond (CmpNat 1 (Dimension b)) 'True 'True 'False)
   (TypeError ...),
 Assert
   (OrdCond (CmpNat 2 (Dimension b)) 'True 'True 'False)
   (TypeError ...),
 IsIntersectableWith (LinePV (Dimension b) (NumType b)) h,
 Point_ b (Dimension b) (NumType b)) =>
b -> Vector (Dimension b) (NumType b) -> h -> b
intersectionPoint vertex
q Vector 2 r
Vector (Dimension vertex) (NumType vertex)
w LinePV 2 r
l'


    maximumOn :: (a -> a) -> t a -> a
maximumOn a -> a
f = (a -> a -> Ordering) -> t a -> a
forall (t :: * -> *) a.
Foldable1 t =>
(a -> a -> Ordering) -> t a -> a
maximumBy ((a -> a) -> a -> a -> Ordering
forall a b. Ord a => (b -> a) -> b -> b -> Ordering
comparing a -> a
f)

    intersectionPoint :: b -> Vector (Dimension b) (NumType b) -> h -> b
intersectionPoint b
p Vector (Dimension b) (NumType b)
v' h
l = case Point (Dimension b) (NumType b)
-> Vector (Dimension b) (NumType b)
-> LinePV (Dimension b) (NumType b)
forall (d :: Nat) r. Point d r -> Vector d r -> LinePV d r
LinePV (b
pb
-> Getting
     (Point (Dimension b) (NumType b))
     b
     (Point (Dimension b) (NumType b))
-> Point (Dimension b) (NumType b)
forall s a. s -> Getting a s a -> a
^.Getting
  (Point (Dimension b) (NumType b))
  b
  (Point (Dimension b) (NumType b))
forall point (d :: Nat) r.
Point_ point d r =>
Lens' point (Point d r)
Lens' b (Point (Dimension b) (NumType b))
asPoint) Vector (Dimension b) (NumType b)
v' LinePV (Dimension b) (NumType b)
-> h -> Intersection (LinePV (Dimension b) (NumType b)) h
forall g h. IsIntersectableWith g h => g -> h -> Intersection g h
`intersect` h
l of
      Just (Line_x_Line_Point Point 2 (NumType b)
a) -> b
pb -> (b -> b) -> b
forall a b. a -> (a -> b) -> b
&(NumType b -> Identity (NumType b)) -> b -> Identity b
forall (d :: Nat) point r.
(1 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens' Int b (NumType b)
xCoord ((NumType b -> Identity (NumType b)) -> b -> Identity b)
-> NumType b -> b -> b
forall s t a b. ASetter s t a b -> b -> s -> t
.~ Point 2 (NumType b)
aPoint 2 (NumType b)
-> Getting (NumType b) (Point 2 (NumType b)) (NumType b)
-> NumType b
forall s a. s -> Getting a s a -> a
^.Getting (NumType b) (Point 2 (NumType b)) (NumType b)
forall (d :: Nat) point r.
(1 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens' Int (Point 2 (NumType b)) (NumType b)
xCoord
                                     b -> (b -> b) -> b
forall a b. a -> (a -> b) -> b
&(NumType b -> Identity (NumType b)) -> b -> Identity b
forall (d :: Nat) point r.
(2 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens' Int b (NumType b)
yCoord ((NumType b -> Identity (NumType b)) -> b -> Identity b)
-> NumType b -> b -> b
forall s t a b. ASetter s t a b -> b -> s -> t
.~ Point 2 (NumType b)
aPoint 2 (NumType b)
-> Getting (NumType b) (Point 2 (NumType b)) (NumType b)
-> NumType b
forall s a. s -> Getting a s a -> a
^.Getting (NumType b) (Point 2 (NumType b)) (NumType b)
forall (d :: Nat) point r.
(2 <= d, Point_ point d r) =>
IndexedLens' Int point r
IndexedLens' Int (Point 2 (NumType b)) (NumType b)
yCoord
      Intersection (LinePV (Dimension b) (NumType b)) h
_                          -> String -> b
forall a. HasCallStack => String -> a
error String
"intersectionPoint: absurd'"

-- -- TODO: this would make for a good property test: test if the points all lie inside the reegion


--------------------------------------------------------------------------------
-- * Intersection of a Rectangle with an Unbounded Convex Polygon

type instance Intersection (Rectangle corner) (UnboundedConvexRegionF r nonEmpty vertex)
  = Intersection (Rectangle corner) (ConvexPolygonF (Cyclic nonEmpty) vertex)

instance (Point_ vertex 2 r, Point_ corner 2 r, Ord r, Fractional r
         ) => Rectangle corner `HasIntersectionWith` UnboundedConvexRegionF r NonEmpty vertex

instance ( Point_ vertex 2 r, Point_ corner 2 r, Ord r, Fractional r
         ) => Rectangle corner `IsIntersectableWith` UnboundedConvexRegionF r NonEmpty vertex where
  Rectangle corner
rect intersect :: Rectangle corner
-> UnboundedConvexRegionF r NonEmpty vertex
-> Intersection
     (Rectangle corner) (UnboundedConvexRegionF r NonEmpty vertex)
`intersect` UnboundedConvexRegionF r NonEmpty vertex
region = Rectangle corner
rect Rectangle corner
-> ConvexPolygonF (Cyclic NonEmpty) vertex
-> Intersection
     (Rectangle corner) (ConvexPolygonF (Cyclic NonEmpty) vertex)
forall g h. IsIntersectableWith g h => g -> h -> Intersection g h
`intersect` Corners corner
-> UnboundedConvexRegionF r NonEmpty vertex
-> ConvexPolygonF (Cyclic NonEmpty) vertex
forall (nonEmpty :: * -> *) point r vertex.
(Foldable nonEmpty, Point_ point 2 r, Point_ vertex 2 r, Ord r,
 Fractional r) =>
nonEmpty point
-> UnboundedConvexRegionF r NonEmpty vertex
-> ConvexPolygonF (Cyclic NonEmpty) vertex
toBoundedFrom (Rectangle corner -> Corners corner
forall r rectangle point.
(Num r, Rectangle_ rectangle point, Point_ point 2 r) =>
rectangle -> Corners point
Box.corners Rectangle corner
rect) UnboundedConvexRegionF r NonEmpty vertex
region



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



  -- case traverse (`intersect` box) rays of
  --   Just (Vector2 (HalfLine_x_Box_LineSegment s1)
  --                 (HalfLine_x_Box_LineSegment s2)) -> f (s1^.end) (s2^.end)
  --   _ -> error "toBoundedFrom: absurd"
  -- where
  --   (a,qSide) = intersectionPoint r1
  --   (b,pSide) = intersectionPoint r2


  --   box = boundingBox $ boxRay r1 <> boxRay r2 <> toNonEmptyOf folded tri
  --   rays@(Vector2 r1 r2) = boundingRays reg

  --   boxRay r = NonEmpty.fromList [ r^.start, r^.start .+^ r^.direction ]

  --   f a b = uncheckedFromCCWPoints $ case cornerInBetween b a box of
  --             Nothing -> b NonEmpty.<|               a NonEmpty.<| pts
  --             Just c  -> b NonEmpty.<| c NonEmpty.<| a NonEmpty.<| pts





-- -- | Given a ray that starts inside the box box, compute the edge (and its index) on
-- -- which the ray intersects (and thus exits) the box
-- --
-- -- pre: the ray starts in the rectangle!
-- intersectionPoint       :: (Point_ corner 2 r, Fractional r, Ord r)
--                         => HalfLine line -> Rectangle corner
--                         -> (Point 2 r :+ VertexIx (Rectangle corner))
-- intersectionPoint r box = case getFirst $ intersectionPoint' r of
--                             Nothing -> error "intersectionPoint: precondititon failed "
--                             Just x  -> x
--   where
--     intersectionPoint' r = flip (ifoldMapOf outerBoundaryEdgeSegments) box $ \(side,_) seg ->
--       case r `intersect` seg of
--         Just (HalfLine_x_LineSegment_Point x) -> First $ Just (x :+ side)
--         _                                     -> First   Nothing


-- -- | Given two vertex indices, computes the list of vertices in between them.
-- cornersInBetween         :: ( HasVertices triangle triangle, Eq (VertexIx triangle)
--                             , Point_ (Vertex triangle) 2 r
--                             )
--                          => VertexIx triangle -> VertexIx triangle
--                          -> triangle -> [Point 2 r]
-- cornersInBetween s e tri = map (^._2.asPoint)
--                          . takeWhile ((/= e) . fst) . dropWhile ((/= s) . fst)
--                          $ cycle (itoListOf vertices tri)


-- -- | Given two points a and b on the sides of the box, computes the first CCW corner in
-- -- between a and b on the box (considered from a)
-- cornerInBetween a b box = case


--   case extremalVertices reg of
--     Right (Vector2 p q) -> compute p q
--     Left p              -> compute p p
--   where
--     box =










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