h$Y"      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~                                                                                                                                        !!!!!!!!!!!!!!!!!!!!!!!!!!!"##################$$$$$$$$$$$$$$$$$$$$$$$$$$%%%%%%%%%%%&&&&&&&&&&&&&&&&&&&&'''''''''''''''''''''''''''''''''''''(((((((((((((((((((((((((((()))))))))*********************************++++++++++++++++++++++++++++,,,- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . / / / / / / / / / / / / / / / / / / / / / 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 2 2 2 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 8 8 8 8 8     9 9 : : : : ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; < < < < < < < < 2 2 2 = = = = = = = = = = > > ? ? ? ? @ @ @ A A A A A A A A A A B B C C C C C C   D E E E E E E E F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F F G G G G G G G G G H H H H H H I I J J J J J J J K K K K K K L L L L L M M M M M M M N N N O O O O O O O O O O O O O O O O O O             P P P P P P P P P P P P P P P P P                                                                                      Q Q Q Q Q Q Q Q Q Q R R R R R R R R R R R R R R R R R R R R R R R R R R R RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSSTTTTTUUUUUVVVVVVVVVVVVVVVVVVVVVVVVVVVVWWWWXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYZZZZZZZZZZZZZ[[[[[[\\\\]]]]]]]]]]]]]]]]^^^^^^__________________`````abccccccccccccccccccccddddeNone&'(-./25678>?( hgeometry)Test if the expression has any variables.fNone&'(-./25678>?*P hgeometryThe sign of an expressionS hgeometryFlip Positive  = Negative.T hgeometryGiven the terms, in decreasing order of significance, computes the signi.e. expects a list of terms, we base the sign on the sign of the first non-zero term.0pre: the list contains at least one such a term.PRQST(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?0 U hgeometry:Represents a Sum of terms, i.e. a value that has the form:! \sum c \Pi_i \varepsilon(i) >The terms are represented in order of decreasing significance.The main idea in this type is that, if symbolic values contains \varepsilon(i) terms we can always order them. That is, two Symbolic terms will be equal only if:3they contain *only* a constant term (that is equal)they contain the exact same  \varepsilon-fold.V hgeometry%A term 'Term c es' represents a term:" c \Pi_{i \in es} \varepsilon(i) 0for a constant c and an arbitrarily small value  \varepsilon, parameterized by i.Y hgeometryGets the factorsZ hgeometryCreates the term \varepsilon(i)\ hgeometrycomputes a base d that can be used as:$ \varepsilon(i) = \varepsilon^{d^i} ] hgeometry=Test if the epsfold has no pertubation at all (i.e. if it is \Pi_{\emptyset}^ hgeometryLens to access the constant c in the term._ hgeometryCreates a singleton term` hgeometry=Produces a list of terms, in decreasing order of significancea hgeometry>Computing the Sign of an expression. (Nothing represents zero)b hgeometry!Creates a constant symbolic valuec hgeometryCreates a symbolic vlaue with a single indexed term. If you just need a constant (i.e. non-indexed), use bd hgeometrygiven the value c and the index i, creates the perturbed value c + \varepsilon(i)UVWXYZ[\]^_`abcdXZ[]Y\VW_^Ubcd`a(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?2x} hgeometryIntercardinal directions hgeometryThe four cardinal directions. hgeometry1Computes the direction opposite to the given one. hgeometryGet the two intercardinal directions, in increasing order, corresponding to the cardinal direction. }~ }~(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?3 hgeometry,Open on left endpoint; so Closed before open hgeometry.Order on right endpoint; so Open before Closed (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?5 hgeometry=A type family for types that have an associated numeric type. hgeometryA type family for types that are associated with a dimension. The dimension is the dimension of the geometry they are embedded in. (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?8 hgeometryAn Interval is essentially a gh but with possible payload-We can think of an interval being defined as:data Interval a r = Interval (EndPoint (r :+ a)) (EndPoint (r :+ a)) hgeometryCast an interval to a range. hgeometry$Intervals and ranges are isomorphic. hgeometry!Constrct an interval from a Range hgeometryTest if a value lies in an interval. Note that the difference between inInterval and inRange is that the extra value is *not* used in the comparison with inInterval, whereas it is in inRange. hgeometry(Shifts the interval to the left by delta hgeometryMakes sure the start and endpoint are oriented such that the starting value is smaller than the ending value. hgeometry-Flips the start and endpoint of the interval.-  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?<  hgeometry1Information stored in a node of the Interval Tree hgeometry.IntervalTree type, storing intervals of type i hgeometry$Anything that looks like an interval hgeometry8Given an ordered list of points, create an interval treeO(n) hgeometryBuild an interval tree O(n \log n) hgeometryLists the intervals. We don't guarantee anything about the orderrunning time: O(n). hgeometryFind all intervals that stab x O(\log n + k), where k is the output size hgeometryFind all intervals that stab x O(\log n + k), where k is the output size hgeometryInsert : pre: the interval intersects some midpoint in the tree O(\log n) hgeometry Delete an interval from the Tree O(\log n)) (under some general position assumption) (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?=   (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?A  hgeometryA generic (1D) range tree. The r parameter indicates the type of the coordinates of the points. The q represents any associated data values with those points (stored in the leaves), and the v5 types represents the data stored at internal nodes. hgeometryCreates a range tree hgeometry+pre: input is sorted and grouped by x-coord hgeometry$Lists all points in increasing orderrunning time: O(n) hgeometry Range searchrunning time:  O(\log n) hgeometry>Range search, report the (associated data structures of the)  O(\log n) nodes that form the disjoint union of the range we are querying with.running time:  O(\log n) hgeometryThe actual search hgeometry7Helper function to get the range of a binary leaf tree hgeometryGet the range of a node hgeometryPerform a counting queryImplementation of SegmentTrees(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?FI  hgeometryInternal nodes store a split point, the range, and an associated data structure hgeometryLeaf nodes store an atomic range, and an associated data structure. hgeometry(Segment tree on a Fixed set of endpoints hgeometryInterval hgeometry%Class for associcated data structures hgeometryGiven a sorted list of endpoints, without duplicates, construct a segment treeO(n) time hgeometryBuild a SegmentTree O(n \log n) hgeometry'Search for all intervals intersecting x O(\log n + k) where k is the output size hgeometryReturns the associated values of the nodes on the search path to x O(\log n) hgeometryPre: the interval should have one of the endpoints on which the tree is built. hgeometry Delete an interval from the tree pre: The segment is in the tree!""i(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?GK"(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?L hgeometryDatatype representing d dimensional vectors. Our implementation wraps the implementation provided by fixed-vector. hgeometry.A proxy which can be used for the coordinates. hgeometry-Pattern synonym for two and three dim vectors hgeometryLens into the i th element hgeometry Similar to  above. Except that we don't have a static guarantee that the index is in bounds. Hence, we can only return a Traversal hgeometry!Get the head and tail of a vector hgeometry.Cross product of two three-dimensional vectors hgeometryVonversion to a Linear.V2 hgeometryConversion to a Linear.V3 hgeometryConversion from a Linear.V3 hgeometry(Add an element at the back of the vector hgeometry)Get a vector of the first d - 1 elements. hgeometry&Get a prefix of i elements of a vector hgeometry Construct a 2 dimensional vector hgeometry Construct a 3 dimensional vector hgeometry#Destruct a 2 dim vector into a pair(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?N hgeometryMapping between the implementation type, and the actual implementation. hgeometryDatatype representing d dimensional vectors. The default implementation is based n VectorFixed. However, for small vectors we automatically select a more efficient representation.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?T3 hgeometryDatatype representing d dimensional vectors. The default implementation is based n VectorFixed. However, for small vectors we automatically select a more efficient representation. hgeometry&Constant sized vector with 4 elements. hgeometry&Constant sized vector with 3 elements. hgeometry&Constant sized vector with 2 elements. hgeometry%Constant sized vector with 1 element. hgeometry&Constant sized vector with d elements. hgeometry5Vectors are isomorphic to a definition determined by . hgeometry O(n) + Convert from a list to a non-empty vector. hgeometry O(n) + Convert from a list to a non-empty vector. hgeometry O(n) $ Pop the first element off a vector. hgeometry O(1)  First element. Since arity is at least 1, this function is total. hgeometryLens into the i th element hgeometry Similar to  above. Except that we don't have a static guarantee that the index is in bounds. Hence, we can only return a Traversal hgeometry O(n)  Prepend an element. hgeometry(Add an element at the back of the vector hgeometry)Get a vector of the first d - 1 elements. hgeometry O(1)  Last element. Since the vector is non-empty, runtime bounds checks are bypassed. hgeometry&Get a prefix of i elements of a vector hgeometry.Cross product of two three-dimensional vectors(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?Z hgeometry='isScalarmultipleof u v' test if v is a scalar multiple of u. .Vector2 1 1 `isScalarMultipleOf` Vector2 10 10True3Vector3 1 1 2 `isScalarMultipleOf` Vector3 10 10 20True-Vector2 1 1 `isScalarMultipleOf` Vector2 10 1False2Vector2 1 1 `isScalarMultipleOf` Vector2 (-1) (-1)True2Vector2 1 1 `isScalarMultipleOf` Vector2 11.1 11.1True2Vector2 1 1 `isScalarMultipleOf` Vector2 11.1 11.2False2Vector2 2 1 `isScalarMultipleOf` Vector2 11.1 11.2False,Vector2 2 1 `isScalarMultipleOf` Vector2 4 2True,Vector2 2 1 `isScalarMultipleOf` Vector2 4 0False0Vector3 2 1 0 `isScalarMultipleOf` Vector3 4 0 5False0Vector3 0 0 0 `isScalarMultipleOf` Vector3 4 0 5True hgeometryscalarMultiple u v computes the scalar labmda s.t. v = lambda * u (if it exists) hgeometryGiven two colinar vectors, u and v, test if they point in the same direction, i.e. iff scalarMultiple' u v == Just lambda, with lambda > 0/pre: u and v are colinear, u and v are non-zero hgeometry'Shorthand to access the first componentVector3 1 2 3 ^. xComponent1Vector2 1 2 & xComponent .~ 10 Vector2 10 2 hgeometry(Shorthand to access the second componentVector3 1 2 3 ^. yComponent2Vector2 1 2 & yComponent .~ 10 Vector2 1 10 hgeometry'Shorthand to access the third componentVector3 1 2 3 ^. zComponent3 Vector3 1 2 3 & zComponent .~ 10Vector3 1 2 10;45:9876;<=>?@ABCDEFGHOIJKLNM%?@ABCDEFGHOIJKLNM:9876=54><;j(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?b hgeometryTypes that we can transform by mapping a function on each point in the structure hgeometryA d-dimensional point.There are convenience pattern synonyms for 1, 2 and 3 dimensional points.$let f (Point1 x) = x in f (Point1 1)1(let f (Point2 x y) = x in f (Point2 1 2)1,let f (Point3 x y z) = z in f (Point3 1 2 3)35let f (Point3 x y z) = z in f (Point $ Vector3 1 2 3)3 hgeometry9A bidirectional pattern synonym for 3 dimensional points. hgeometry9A bidirectional pattern synonym for 2 dimensional points. hgeometry9A bidirectional pattern synonym for 1 dimensional points. hgeometry-Point representing the origin in d dimensionsorigin :: Point 4 IntPoint4 0 0 0 0 hgeometry6Lens to access the vector corresponding to this point.(Point3 1 2 3) ^. vector Vector3 1 2 3 origin & vector .~ Vector3 1 2 3 Point3 1 2 3 hgeometryGet the coordinate in a given dimension. This operation is unsafe in the sense that no bounds are checked. Consider using  instead.Point3 1 2 3 ^. unsafeCoord 22 hgeometry'Get the coordinate in a given dimension Point3 1 2 3 ^. coord (C :: C 2)2%Point3 1 2 3 & coord (C :: C 1) .~ 10 Point3 10 2 3'Point3 1 2 3 & coord (C :: C 3) %~ (+1) Point3 1 2 4 hgeometryConstructs a point from a list of coordinates. The length of the list has to match the dimension exactly.,pointFromList [1,2,3] :: Maybe (Point 3 Int)Just (Point3 1 2 3)(pointFromList [1] :: Maybe (Point 3 Int)Nothing.pointFromList [1,2,3,4] :: Maybe (Point 3 Int)Nothing hgeometry,Project a point down into a lower dimension. hgeometry)Compare by distance to the first argument hgeometry)Compare by distance to the first argument hgeometry-Squared Euclidean distance between two points hgeometry%Euclidean distance between two pointskNone&'(-./25678>?o  hgeometryData type for expressing the orientation of three points, with the option of allowing Colinearities. hgeometry2CoLinear orientation. Also called a straight line. hgeometry0Clockwise orientation. Also called a right-turn. hgeometry6CounterClockwise orientation. Also called a left-turn. hgeometryGiven three points p q and r determine the orientation when going from p to r via q.Be vary of numerical instability: >>> ccw (Point2 0 0.3) (Point2 1 0.6) (Point2 2 (0.9::Double)) CCW>> ccw (Point2 0 0.3) (Point2 1 0.6) (Point2 2 (0.9::SafeDouble)) CoLinear hgeometryGiven three points p q and r determine if the line from p to r via q is straight/colinear.This is identical to `ccw p q r == CoLinear` but doesn't have the  constraint. hgeometryGiven three points p q and r determine the orientation when going from p to r via q. hgeometry O(n log n)  Sort the points arround the given point p in counter clockwise order with respect to the rightward horizontal ray starting from p. If two points q and r are colinear with p, the closest one to p is reported first. hgeometry O(n log n)  Sort the points arround the given point p in counter clockwise order with respect to the rightward horizontal ray starting from p. If two points q and r are colinear with p, the closest one to p is reported first. hgeometryGiven a zero vector z, a center c, and two points p and q, compute the ccw ordering of p and q around c with this vector as zero direction.pre: the points p,q /= c hgeometryGiven a zero vector z, a center c, and two points p and q, compute the ccw ordering of p and q around c with this vector as zero direction.pre: the points p,q /= c hgeometryGiven a zero vector z, a center c, and two points p and q, compute the cw ordering of p and q around c with this vector as zero direction.pre: the points p,q /= c hgeometryGiven a zero vector z, a center c, and two points p and q, compute the cw ordering of p and q around c with this vector as zero direction.pre: the points p,q /= c hgeometryCounter clockwise ordering of the points around c. Points are ordered with respect to the positive x-axis. hgeometryCounter clockwise ordering of the points around c. Points are ordered with respect to the positive x-axis. hgeometryClockwise ordering of the points around c. Points are ordered with respect to the positive x-axis. hgeometryClockwise ordering of the points around c. Points are ordered with respect to the positive x-axis. hgeometry O(n)  Given a center c, a new point p, and a list of points ps, sorted in counter clockwise order around c. Insert p into the cyclic order. The focus of the returned cyclic list is the new point p.lNone&'(-./25678>?s6 hgeometry6Lens to access the vector corresponding to this point.(Point3 1 2 3) ^. vector' Vector3 1 2 3!origin & vector' .~ Vector3 1 2 3 Point3 1 2 3 hgeometry'Get the coordinate in a given dimension Point3 1 2 3 ^. coord (C :: C 2)2%Point3 1 2 3 & coord (C :: C 1) .~ 10 Point3 10 2 3'Point3 1 2 3 & coord (C :: C 3) %~ (+1) Point3 1 2 4 hgeometryGet the coordinate in a given dimension. This operation is unsafe in the sense that no bounds are checked. Consider using  instead.Point3 1 2 3 ^. unsafeCoord 22 hgeometry,Shorthand to access the first coordinate C 1Point3 1 2 3 ^. xCoord1Point2 1 2 & xCoord .~ 10 Point2 10 2 hgeometry-Shorthand to access the second coordinate C 2Point2 1 2 ^. yCoord2Point3 1 2 3 & yCoord %~ (+1) Point3 1 3 3 hgeometry,Shorthand to access the third coordinate C 3Point3 1 2 3 ^. zCoord3Point3 1 2 3 & zCoord %~ (+1) Point3 1 2 4 m(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?v hgeometry1Quadrants of two dimensional points. in CCW order hgeometryQuadrants around point c; quadrants are closed on their "previous" boundary (i..e the boundary with the previous quadrant in the CCW order), open on next boundary. The origin itself is assigned the topRight quadrant hgeometry$Quadrants with respect to the origin hgeometryGiven a center point c, and a set of points, partition the points into quadrants around c (based on their x and y coordinates). The quadrants are reported in the order topLeft, topRight, bottomLeft, bottomRight. The points are in the same order as they were in the original input lists. Points with the same x-or y coordinate as p, are "rounded" to above.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?w,/2(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?x hgeometry!Gets all points in the range tree(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?{ hgeometryA priority search tree storing points in (mathbb{R}^2) that have an additional payload of type p. hgeometryCreates a Priority Search Tree for 3-sided range queries of the form _l,x_r] \times [y,\infty).the base tree will be static.)pre: all points have unique x-coordinatesrunning time:  O(n\log n) hgeometryGiven a three sided range  [x_l,x_r],y! report all points in the range _l,x_r] \times [y,\infty)2. The points are reported in decreasing order of y -coordinate.running time:  O(\log n + k), where k" is the number of reported points.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?~ hgeometryReturns the discrete frechet distance between two point sequences using the squared Euclidean distance. In other words, returns the square of the (Euclidean) frechet distance.running time: O((nm)), where n and m# are the lengths of the sequences. hgeometryReturns the discrete frechet distance between two point sequences using the given distance measure.running time: O((nm)), where n and m are the lengths of the sequences (and assuming that a distance calculation takes constant time). hgeometrydistance function(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?V hgeometryType used in the closest pair computation. The fields represent the points ordered on increasing y-order and the closest pair (if we know it) hgeometry+the closest pair and its (squared) distance hgeometryClassical divide and conquer algorithm to compute the closest pair among n points.running time:  O(n \log n) hgeometry*Function that does the actual merging work hgeometry!current closest pair and its dist hgeometrypts on the left hgeometrypts on the rightn(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?oUnsafe&'(-./25678>? hgeometryCreates a row with zeroes everywhere, except at position i, where the value is the supplied value.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?] hgeometry*Class of matrices that have a determinant. hgeometry&Class of matrices that are invertible. hgeometryA matrix of n rows, each of m columns, storing values of type r. hgeometryMatrix product. hgeometryMatrix * column vector. hgeometryProduces the Identity Matrix.  p(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometryA class representing types that can be transformed using a transformation hgeometry>A type representing a Transformation for d dimensional objects hgeometry,Transformations and Matrices are isomorphic. hgeometry'Compose transformations (right to left) hgeometryIdentity transformation; i.e. the transformation which does not change anything. hgeometry"Compute the inverse transformation.inverseOf $ translation (Vector2 (10.0) (5.0))Transformation {_transformationMatrix = Matrix (Vector3 (Vector3 1.0 0.0 (-10.0)) (Vector3 0.0 1.0 (-5.0)) (Vector3 0.0 0.0 1.0))} hgeometry2Apply a transformation to a collection of objects.transformAllBy (uniformScaling 2) [Point1 1, Point1 2, Point1 3]"[Point1 2.0,Point1 4.0,Point1 6.0] hgeometryApply transformation to a PointFunctor, ie something that contains points. Polygons, triangles, line segments, etc, are all PointFunctors.transformPointFunctor (uniformScaling 2) $ OpenLineSegment (Point1 1 :+ ()) (Point1 2 :+ ())5OpenLineSegment (Point1 2.0 :+ ()) (Point1 4.0 :+ ()) hgeometry0Create translation transformation from a vector.4transformBy (translation $ Vector2 1 2) $ Point2 2 3Point2 3.0 5.0 hgeometry,Create scaling transformation from a vector.3transformBy (scaling $ Vector2 2 (-1)) $ Point2 2 3Point2 4.0 (-3.0) hgeometryCreate scaling transformation from a scalar that is applied to all dimensions.+transformBy (uniformScaling 5) $ Point2 2 3Point2 10.0 15.0)uniformScaling 5 == scaling (Vector2 5 5)True+uniformScaling 5 == scaling (Vector3 5 5 5)True hgeometryTranslate a given point.&translateBy (Vector2 1 2) $ Point2 2 3Point2 3.0 5.0 hgeometryScale a given point.%scaleBy (Vector2 2 (-1)) $ Point2 2 3Point2 4.0 (-3.0) hgeometry0Scale a given point uniformly in all dimensions.scaleUniformlyBy 5 $ Point2 2 3Point2 10.0 15.0 hgeometryRow in a translation matrix transRow :: forall n r. ( Arity n, Arity (n- 1), ((n - 1) + 1) ~ n , Num r) => Int -> r -> Vector n r transRow i x = set (V.element (Proxy :: Proxy (n-1))) x $ mkRow i 1 hgeometryGiven three new unit-length basis vectors (u,v,w) that map to (x,y,z), construct the appropriate rotation that does this. hgeometrySkew transformation that keeps the y-coordinates fixed and shifts the x coordinates. hgeometry2Create a matrix that corresponds to a rotation by a0 radians counter-clockwise around the origin. hgeometryCreate a matrix that corresponds to a reflection in a line through the origin which makes an angle of a radians with the positive x+-asis, in counter-clockwise orientation. hgeometryVertical reflection hgeometryHorizontal reflectionqNone&'(-./25678>? hgeometry)pre: computes the sign of the determinant(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678:>? hgeometryResult of a side test hgeometryResult of a side test hgeometryTypes for which we can compute a supporting line, i.e. a line that contains the thing of type t. hgeometryA line is given by an anchor point and a vector indicating the direction. hgeometryLine anchor point. hgeometryLine direction. hgeometry*A line may be constructed from two points. hgeometry(Vertical line with a given X-coordinate. hgeometry*Horizontal line with a given Y-coordinate. hgeometryGiven a line l with anchor point p and vector v, get the line perpendicular to l that also goes through p. The resulting line m is oriented such that v points into the left halfplane of m.4perpendicularTo $ Line (Point2 3 4) (Vector2 (-1) 2)%Line (Point2 3 4) (Vector2 (-2) (-1)) hgeometry.Test if a vector is perpendicular to the line. hgeometryTest if two lines are identical, meaning; if they have exactly the same anchor point and directional vector. hgeometry#Test if the two lines are parallel.lineThrough origin (Point2 1 0) `isParallelTo` lineThrough (Point2 1 1) (Point2 2 1)TruelineThrough origin (Point2 1 0) `isParallelTo` lineThrough (Point2 1 1) (Point2 2 2)False hgeometryTest if point p lies on line l/origin `onLine` lineThrough origin (Point2 1 0)True5Point2 10 10 `onLine` lineThrough origin (Point2 2 2)True4Point2 10 5 `onLine` lineThrough origin (Point2 2 2)False hgeometry8Specific 2d version of testing if apoint lies on a line. hgeometryGet the point at the given position along line, where 0 corresponds to the anchorPoint of the line, and 1 to the point anchorPoint .+^ directionVector hgeometryGiven point p and a line (Line q v), Get the scalar lambda s.t. p = q + lambda v. If p does not lie on the line this returns a Nothing. hgeometryGiven point p near a line (Line q v), get the scalar lambda s.t. the distance between p! and 'q + lambda v' is minimized.:toOffset' (Point2 1 1) (lineThrough origin $ Point2 10 10)0.1:toOffset' (Point2 5 5) (lineThrough origin $ Point2 10 10)0.5<6,4> is not on the line but we can still point closest to it. >>> toOffset' (Point2 6 4) (lineThrough origin $ Point2 10 10) 0.5 hgeometry'Squared distance from point p to line l hgeometryThe squared distance between the point p and the line l, and the point m realizing this distance. hgeometry-Create a line from the linear function ax + b hgeometryget values a,b s.t. the input line is described by y = ax + b. returns Nothing if the line is vertical hgeometryGiven a point p and a line l, computes the point q on l closest to p. hgeometryGiven a point q and a line l, compute to which side of l q lies. For vertical lines the left side of the line is interpeted as below.8Point2 10 10 `onSide` (lineThrough origin $ Point2 10 5)LeftSide;Point2 10 10 `onSide` (lineThrough origin $ Point2 (-10) 5) RightSide%Point2 5 5 `onSide` (verticalLine 10)LeftSide;Point2 5 5 `onSide` (lineThrough origin $ Point2 (-3) (-3))OnLine hgeometry6Test if the query point q lies (strictly) above line l hgeometry6Test if the query point q lies (strictly) above line l hgeometry#Get the bisector between two points hgeometryCompares the lines on slope. Vertical lines are considered larger than anything else.(Line origin (Vector2 5 1)) `cmpSlope` (Line origin (Vector2 3 3))LT(Line origin (Vector2 5 1)) `cmpSlope` (Line origin (Vector2 (-3) 3))GT(Line origin (Vector2 5 1)) `cmpSlope` (Line origin (Vector2 0 1))LT hgeometryThe intersection of two lines is either: NoIntersection, a point or a line.(((C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometryPart of a line. The interval is ranged based on the vector of the line l, and s.t.t zero is the anchorPoint of l. hgeometryLine part of SubLine. hgeometryInterval part of SubLine. hgeometry3Annotate the subRange with the actual ending points hgeometryforget the extra information stored at the endpoints of the subline. hgeometry8Prism for downcasting an unbounded subline to a subline. hgeometry?Transform into an subline with a potentially unbounded interval hgeometry?Try to make a potentially unbounded subline into a bounded one. hgeometrygiven point p, and a Subline l r such that p lies on line l, test if it lies on the subline, i.e. in the interval r hgeometrygiven point p, and a Subline l r such that p lies on line l, test if it lies on the subline, i.e. in the interval r hgeometrygiven point p, and a Subline l r such that p lies on line l, test if it lies on the subline, i.e. in the interval r hgeometrygiven point p, and a Subline l r such that p lies on line l, test if it lies on the subline, i.e. in the interval r hgeometry*Get the endpoints of an unbounded interval hgeometryCreate a SubLine that covers the original line from -infinity to +infinity.(C) Frank Staalssee the LICENSE file Frank StaalsNone!&'(-./025678>? hgeometryCoordinate wize minimum hgeometryCoordinate wize maximum hgeometryGiven the point with the lowest coordinates and the point with highest coordinates, create a box. hgeometrygrows the box by x on all sides hgeometry)Build a d dimensional Box given d ranges. hgeometryGiven a center point and a vector specifying the box width's, construct a box. hgeometryCenter of the box hgeometryCheck if a point lies a boxorigin `inBox` (boundingBoxList' [Point3 1 2 3, Point3 10 20 30] :: Box 3 () Int)Falseorigin `inBox` (boundingBoxList' [Point3 (-1) (-2) (-3), Point3 10 20 30] :: Box 3 () Int)True hgeometryCheck if a point lies strictly inside a box (i.e. not on its boundary)origin `inBox` (boundingBoxList' [Point3 1 2 3, Point3 10 20 30] :: Box 3 () Int)Falseorigin `inBox` (boundingBoxList' [Point3 (-1) (-2) (-3), Point3 10 20 30] :: Box 3 () Int)True hgeometryGet a vector with the extent of the box in each dimension. Note that the resulting vector is 0 indexed whereas one would normally count dimensions starting at zero.extent (boundingBoxList' [Point3 1 2 3, Point3 10 20 30] :: Box 3 () Int)Vector3 (Range (Closed 1) (Closed 10)) (Range (Closed 2) (Closed 20)) (Range (Closed 3) (Closed 30)) hgeometryGet the size of the box (in all dimensions). Note that the resulting vector is 0 indexed whereas one would normally count dimensions starting at zero.>size (boundingBoxList' [origin, Point3 1 2 3] :: Box 3 () Int) Vector3 1 2 3 hgeometryGiven a dimension, get the width of the box in that dimension. Dimensions are 1 indexed.widthIn (C :: C 1) (boundingBoxList' [origin, Point3 1 2 3] :: Box 3 () Int)1widthIn (C :: C 3) (boundingBoxList' [origin, Point3 1 2 3] :: Box 3 () Int)3 hgeometrySame as 6 but with a runtime int instead of a static dimension.widthIn' 1 (boundingBoxList' [origin, Point3 1 2 3] :: Box 3 () Int)Just 1widthIn' 3 (boundingBoxList' [origin, Point3 1 2 3] :: Box 3 () Int)Just 3widthIn' 10 (boundingBoxList' [origin, Point3 1 2 3] :: Box 3 () Int)Nothing hgeometrywidth (boundingBoxList' [origin, Point2 1 2] :: Rectangle () Int)15width (boundingBoxList' [origin] :: Rectangle () Int)0 hgeometryheight (boundingBoxList' [origin, Point2 1 2] :: Rectangle () Int)26height (boundingBoxList' [origin] :: Rectangle () Int)0 hgeometry:Create a bounding box that encapsulates a list of objects. hgeometryUnsafe version of boundingBoxList, that does not check if the list is non-empty""(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678>?  hgeometryLine segments. LineSegments have a start and end point, both of which may contain additional data of type p. We can think of a Line-Segment being defined asdata LineSegment d p r = LineSegment (EndPoint (Point d r :+ p)) (EndPoint (Point d r :+ p))it is assumed that the two endpoints of the line segment are disjoint. This is not checked. hgeometryGets the start and end point, but forgetting if they are open or closed. hgeometryTraversal to access the endpoints. Note that this traversal allows you to change more or less everything, even the dimension and the numeric type used, but it preservers if the segment is open or closed. hgeometry,Directly convert a line into a line segment. hgeometry'Test if a point lies on a line segment.)As a user, you should typically just use  instead. hgeometry'Test if a point lies on a line segment.(Point2 1 0) `onSegment2` (ClosedLineSegment (origin :+ ()) (Point2 2 0 :+ ()))True(Point2 1 1) `onSegment2` (ClosedLineSegment (origin :+ ()) (Point2 2 0 :+ ()))False(Point2 5 0) `onSegment2` (ClosedLineSegment (origin :+ ()) (Point2 2 0 :+ ()))False(Point2 (-1) 0) `onSegment2` (ClosedLineSegment (origin :+ ()) (Point2 2 0 :+ ()))False(Point2 1 1) `onSegment2` (ClosedLineSegment (origin :+ ()) (Point2 3 3 :+ ()))True(Point2 2 0) `onSegment2` (ClosedLineSegment (origin :+ ()) (Point2 2 0 :+ ()))Trueorigin `onSegment2` (ClosedLineSegment (origin :+ ()) (Point2 2 0 :+ ()))True hgeometryThe left and right end point (or left below right if they have equal x-coords) hgeometryLength of the line segment hgeometrySquared distance from the point to the Segment s. The same remark as for the  applies here. hgeometrySquared distance from the point to the Segment s, and the point on s realizing it. Note that if the segment is *open*, the closest point returned may be one of the (open) end points, even though technically the end point does not lie on the segment. (The true closest point then lies arbitrarily close to the end point). hgeometry,flips the start and end point of the segment hgeometryLinearly interpolate the two endpoints with a value in the range [0,1]interpolate 0.5 $ ClosedLineSegment (ext $ origin) (ext $ Point2 10.0 10.0)Point2 5.0 5.0interpolate 0.1 $ ClosedLineSegment (ext $ origin) (ext $ Point2 10.0 10.0)Point2 1.0 1.0interpolate 0 $ ClosedLineSegment (ext $ origin) (ext $ Point2 10.0 10.0)Point2 0.0 0.0interpolate 1 $ ClosedLineSegment (ext $ origin) (ext $ Point2 10.0 10.0)Point2 10.0 10.0 hgeometrysmart constructor that creates a valid segment, i.e. it validates that the endpoints are disjoint.  r(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678>?O?  s(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometryreports true if there is at least one segment for which this intersection point is interior.O(1)None&'(-./25678>? hgeometry#Compute all intersections (naively)O(n^2)(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?ù hgeometryCompute all intersectionsO((n+k)\log n), where k is the number of intersections. hgeometryComputes all intersection points p s.t. p lies in the interior of at least one of the segments.O((n+k)\log n), where k is the number of intersections. hgeometryCompare based on the x-coordinate of the intersection with the horizontal line through y hgeometryGiven a y coord and a line segment that intersects the horizontal line through y, compute the x-coordinate of this intersection point.note that we will pretend that the line segment is closed, even if it is not(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?7 hgeometryA data type rperesenting the corners of a box. the order of the Corners is 'northWest, northEast, southEast, southWest', i.e. in clockwise order starting from the topleft. hgeometryGet the corners of a rectangle, the order is: (TopLeft, TopRight, BottomRight, BottomLeft). The extra values in the Top points are taken from the Top point, the extra values in the Bottom points are taken from the Bottom point hgeometry*Gets the corners in a particular direction (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? !(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometryThe four sides of a rectangle hgeometryConstructs a Sides value that indicates the appropriate direction. hgeometryOriented from *left to right* hgeometry-The right side, oriented from *bottom* to top hgeometryThe sides of the rectangle, in order (Top, Right, Bottom, Left). The sides themselves are also oriented in clockwise order. If, you want them in the same order as the functions , , , and , use  ` instead. hgeometryThe sides of the rectangle. The order of the segments is (Top, Right, Bottom, Left). Note that the segments themselves, are oriented as described by the functions topSide, bottomSide, leftSide, rightSide (basically: from left to right, and from bottom to top). If you want the segments oriented along the boundary of the rectangle, use the  function instead.  "(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678:>?ˑ7(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?V hgeometryGiven a rectangle r and a geometry g with its boundingbox, transform the g to fit r. hgeometryGiven a rectangle r and a geometry g with its boundingbox, compute a transformation can fit g to r.#(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?2 hgeometryResult of a query that asks if something is Inside a g, *on* the boundary of the g, or outside. hgeometry#The boundary of a geometric object. hgeometryIso for converting between things with a boundary and without its boundary$(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometry.A Cell corresponding to a node in the QuadTree hgeometry+side lengths will be 2^i for some integer i hgeometry1Computes a cell that contains the given rectangle hgeometrySides are open hgeometry*Partitions the points into quadrants. See  for the precise rules. hgeometryComputes the quadrant of the cell corresponding to the current point. Note that we decide the quadrant solely based on the midpoint. If the query point lies outside the cell, it is still assigned a quadrant.9The northEast quadrants includes its bottom and left side9The southEast quadrant includes its left side9The northWest quadrant includes its bottom side:The southWest quadrants does not include any of its sides.'quadrantOf (Point2 9 9) (Cell 4 origin) NorthEast'quadrantOf (Point2 8 9) (Cell 4 origin) NorthEast'quadrantOf (Point2 8 8) (Cell 4 origin) NorthEast'quadrantOf (Point2 8 7) (Cell 4 origin) SouthEast'quadrantOf (Point2 4 7) (Cell 4 origin) SouthWest(quadrantOf (Point2 4 10) (Cell 4 origin) NorthWest(quadrantOf (Point2 4 40) (Cell 4 origin) NorthEast(quadrantOf (Point2 4 40) (Cell 4 origin) NorthWest hgeometry3Given two cells c and me, compute on which side of me the cell c is.!pre: c and me are non-overlapping%(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?q hgeometryData Type to Decide if we should continue splitting the current cell hgeometry/Transformer that limits the depth of a splitter hgeometryA splitter is a function that determines weather or not we should the given cell corresponding to the given input (i). hgeometry/Split only when the Cell-width is at least wMin hgeometry7smallest allowed width of a cell (i.e. width of a leaf)&(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometryOur cells use Rational numbers as their numeric type type CellR = Cell (RealNumber 10),The Actual Tree type representing a quadTree hgeometryFold on the Tree type. hgeometry+Produce a list of all leaves of a quad tree hgeometryConverts into a RoseTree hgeometry#Computes the height of the quadtree hgeometryBuilds a QuadTree hgeometry-Annotate the tree with its corresponing cells hgeometry'Build a QuadtTree from a set of points.2pre: the points lie inside the initial given cell.running time: O(nh), where n is the number of points and h) is the height of the resulting quadTree. hgeometry2The function that can be used to build a quadTree   '(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?K hgeometryQuadTree on the starting cell hgeometryGiven a starting cell, a Tree builder, and some input required by the builder, constructs a quadTree. hgeometry8The Equivalent of Tree.build for constructing a QuadTree hgeometry'Build a QuadtTree from a set of points.2pre: the points lie inside the initial given cell.running time: O(nh), where n is the number of points and h) is the height of the resulting quadTree. hgeometry:Locates the cell containing the given point, if it exists.running time: O(h), where h is the height of the quadTree hgeometry&Interpret an ordering result as a Sign hgeometrySplitter that determines if we should split a cell based on the sign of the corners. hgeometry9Constructs an empty/complete tree from the starting width hgeometryThe function we are evaluating hgeometrythe zero value((C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?-  hgeometry*A Poly line in R^d has at least 2 vertices hgeometryPolyLines are isomorphic to a sequence of points with at least 2 members. hgeometryBuilds a Polyline from a list of points, if there are sufficiently many points hgeometry0pre: The input list contains at least two points hgeometrypre: The input list contains at least two points. All extra vields are initialized with mempty. hgeometry'We consider the line-segment as closed. hgeometryConvert to a closed line segment by taking the first two points. hgeometryStricter version of asLineSegment that fails if the Polyline contains more than two points. hgeometry/Computes the edges, as linesegments, of an LSeq hgeometry=Linearly interpolate the polyline with a value in the range [0,n-1], where n+ is the number of vertices of the polyline.running time:  O(\log n)interpolatePoly 0.5 myPolyLinePoint2 5.0 5.0interpolatePoly 1.5 myPolyLinePoint2 10.0 15.0  )(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometry*Lines are transformable, via line segments(*(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometryThe two bounding lines of the slab, first the lower one, then the higher one: hgeometry0Smart consturctor for creating a horizontal slab hgeometry.Smart consturctor for creating a vertical slab  +(C) Frank Staalssee the LICENSE file Frank StaalsNone!&'(-./25678:>?E hgeometryHyperplanes embedded in a d dimensional space. hgeometryTypes for which we can compute a supporting hyperplane, i.e. a hyperplane that contains the thing of type t. hgeometryProduces a plane. If r lies counter clockwise of q w.r.t. p then the normal vector of the resulting plane is pointing "upwards".0from3Points origin (Point3 1 0 0) (Point3 0 1 0)HyperPlane {_inPlane = Point3 0 0 0, _normalVec = Vector3 0 0 1} hgeometry%Convert between lines and hyperplanes hgeometryGiven * a plane, * a unit vector in the plane that will represent the y-axis (i.e. the "view up" vector), and * a point in the plane,computes the plane coordinates of the given point, using the inPlane point as the origin, the normal vector of the plane as the unit vector in the "z-direction" and the view up vector as the y-axis.planeCoordinatesWith (Plane origin (Vector3 0 0 1)) (Vector3 0 1 0) (Point3 10 10 0)Point2 10.0 10.0,(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? hgeometry1Maps a line point (px,py) to a line (y=px*x - py) hgeometryReturns Nothing if the input line is vertical Maps a line l: y = ax + b to a point (a,-b) hgeometry#Pre: the input line is not vertical-(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?Y  hgeometry1Expects the input to be a set, i.e. no duplicatesrunning time:  O(n \log n)  hgeometryNub by sorting first  hgeometrySearches in a KDTreerunning time: O(n^{(d-1)/d} + k)  hgeometryrunning time: O(n)   .(C) Frank Staalssee the LICENSE file Frank StaalsNone!&'(-./25678:>?  hgeometryd-dimensional Half-Lines  hgeometryTransform a LineSegment into a half-line, by forgetting the second endpoint. Note that this also forgets about if the starting point was open or closed.  /(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678>?  hgeometryA Halfspace in d dimensions. Note that the intended side of the halfspace is already indicated by the normal vector of the bounding plane.  hgeometry6Get the halfplane left of a line (i.e. "above") a lineleftOf $ horizontalLine 4HalfSpace {_boundingPlane = HyperPlane {_inPlane = Point2 0 4, _normalVec = Vector2 0 1}}  hgeometry7Get the halfplane right of a line (i.e. "below") a linerightOf $ horizontalLine 4HalfSpace {_boundingPlane = HyperPlane {_inPlane = Point2 0 4, _normalVec = Vector2 0 (-1)}}  hgeometry#Test if a point lies in a halfspace 0(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678>?  hgeometryA d-dimensional ball.  hgeometry%Spheres, i.e. the boundary of a ball.  hgeometry?  hgeometryA triangle in d-dimensional space.  hgeometryconvenience function to construct a triangle without associated data.  hgeometryA d3-dimensional triangle is isomorphic to a triple of d-dimensional points.  hgeometryGet the three line-segments that make up the sides of a triangle.  hgeometryCompute the area of a triangle  hgeometry2*the area of a triangle.  hgeometry9Checks if the triangle is degenerate, i.e. has zero area.  hgeometryGet the inscribed disk. Returns Nothing if the triangle is degenerate, i.e. if the points are colinear.  hgeometryGiven a point q and a triangle, q inside the triangle, get the baricentric cordinates of q  hgeometryGiven a vector of barricentric coordinates and a triangle, get the corresponding point in the same coordinate sytsem as the vertices of the triangle.  hgeometryTests if a point lies inside a triangle, on its boundary, or outside the triangle  hgeometry? T8  hgeometryEither a simple or multipolygon  hgeometry Polygon with zero or more holes.  hgeometryPolygon without holes.  hgeometryPolygons are sequences of points and may or may not contain holes.Degenerate polygons (polygons with self-intersections or fewer than 3 points) are only possible if you use functions marked as unsafe.  hgeometryWe distinguish between simple polygons (without holes) and polygons with holes.  hgeometry Prism to test if we are a simple polygonis _SimplePolygon simplePolyTrue  hgeometry Prism to test if we are a Multi polygonis _MultiPolygon multiPolyTrue  hgeometry8Getter access to the outer boundary vector of a polygon..toList (simpleTriangle ^. outerBoundaryVector)4[Point2 0 0 :+ (),Point2 2 0 :+ (),Point2 1 1 :+ ()]  hgeometry=Unsafe lens access to the outer boundary vector of a polygon.4toList (simpleTriangle ^. unsafeOuterBoundaryVector)4[Point2 0 0 :+ (),Point2 2 0 :+ (),Point2 1 1 :+ ()]simpleTriangle & unsafeOuterBoundaryVector .~ CV.singleton (Point2 0 0 :+ ()) SimplePolygon [Point2 0 0 :+ ()]  hgeometry O(1) 0 Lens access to the outer boundary of a polygon.  hgeometryLens access for polygon holes.multiPoly ^. polygonHoles[SimplePolygon [Point2 0 0 :+ (),Point2 2 0 :+ (),Point2 1 1 :+ ()]]  hgeometry O(1) . Traversal lens for polygon holes. Does nothing for simple polygons.  hgeometryO(1) Access the i^th vertex on the outer boundary. Indices are modulo n.simplePoly ^. outerVertex 0Point2 0 0 :+ () hgeometry O(1)  read and  O(n) 4 write. Access the i^th vertex on the outer boundary!simplePoly ^. unsafeOuterVertex 0Point2 0 0 :+ ()8simplePoly & unsafeOuterVertex 0 .~ (Point2 10 10 :+ ())SimplePolygon [Point2 10 10 :+ (),Point2 10 0 :+ (),Point2 10 10 :+ (),Point2 5 15 :+ (),Point2 1 11 :+ ()]  hgeometry O(1)  Get the n^th edge along the outer boundary of the polygon. The edge is half open.  hgeometryGet all holes in a polygon  hgeometry O(1) . Vertex count. Includes the vertices of holes.  hgeometry O(n)  The vertices in the polygon. No guarantees are given on the order in which they appear!  hgeometry O(n \log n)  Check if a polygon has any holes, duplicate points, or self-intersections.  hgeometry O(n) 3 Creates a polygon from the given list of vertices.The points are placed in CCW order if they are not already. Overlapping edges and repeated vertices are allowed.  hgeometry O(n) 5 Creates a polygon from the given vector of vertices.The points are placed in CCW order if they are not already. Overlapping edges and repeated vertices are allowed.  hgeometry O(n \log n) : Creates a simple polygon from the given list of vertices.The points are placed in CCW order if they are not already. Overlapping edges and repeated vertices are not' allowed and will trigger an exception.  hgeometry O(n \log n) < Creates a simple polygon from the given vector of vertices.The points are placed in CCW order if they are not already. Overlapping edges and repeated vertices are not' allowed and will trigger an exception.  hgeometry O(n) : Creates a simple polygon from the given list of vertices.3pre: the input list constains no repeated vertices.  hgeometry O(1) < Creates a simple polygon from the given vector of vertices.3pre: the input list constains no repeated vertices.  hgeometry O(1) < Creates a simple polygon from the given vector of vertices.3pre: the input list constains no repeated vertices.  hgeometry O(n) ' Polygon points, from left to right.  hgeometry O(n) ' Polygon points, from left to right.  hgeometry O(n)  The edges along the outer boundary of the polygon. The edges are half open.  hgeometry O(n)  Lists all edges. The edges on the outer boundary are given before the ones on the holes. However, no other guarantees are given on the order.  hgeometryPairs every vertex with its incident edges. The first one is its predecessor edge, the second one its successor edge (in terms of the ordering along the boundary). findRotateTo (== (Point2 1 0 :+ ())) (unsafeFromPoints [Point2 0 0 :+ (), Point2 1 0 :+ (), Point2 1 1 :+ ()])9Just [Point2 1 0 :+ (),Point2 1 1 :+ (),Point2 0 0 :+ ()]findRotateTo (== (Point2 7 0 :+ ())) $ unsafeFromPoints [Point2 0 0 :+ (), Point2 1 0 :+ (), Point2 1 1 :+ ()]Nothing  hgeometry O(1) 6 Rotate the polygon to the left by n number of points.  hgeometry O(1) 7 Rotate the polygon to the right by n number of points. hgeometry*Test if a given vertex is a reflex vertex.O(1) hgeometryTest if a given vertex is a convex vertex (i.e. not a reflex vertex).O(1) hgeometry3Test if a given vertex is a strictly convex vertex.O(1) hgeometry,Computes all reflex vertices of the polygon.O(n) hgeometry>Computes all convex (i.e. non-reflex) vertices of the polygon.O(n) hgeometry5Computes all strictly convex vertices of the polygon.O(n) hgeometry)Polygons are per definition 2 dimensional<   u(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?"$  hgeometry(Comparison that compares which point is larger) in the direction given by the vector u.  hgeometryFinds the extreme points, minimum and maximum, in a given directionrunning time: O(n) 3(C) 1ndysee the LICENSE fileDavid HimmelstrupNone&'(-./25678>?$  hgeometry O(n \log n)  A polygon is monotone if a straight line in a given direction cannot have more than two intersections.  hgeometry O(n \log n)  Generate a random N-sided polygon that is monotone in a random direction.  hgeometry O(n \log n)  Generate a random N-sided polygon that is monotone in the given direction.  hgeometry O(n \log n)  Assemble a given set of points in a polygon that is monotone in the given direction.  hgeometry O(1) = Create a random 2D vector which has a non-zero magnitude.  v(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?)R  hgeometry O(n) / Test if q lies on the boundary of the polygon."Point2 1 1 `onBoundary` simplePolyFalse"Point2 0 0 `onBoundary` simplePolyTrue#Point2 10 0 `onBoundary` simplePolyTrue#Point2 5 13 `onBoundary` simplePolyFalse#Point2 5 10 `onBoundary` simplePolyFalse#Point2 10 5 `onBoundary` simplePolyTrue#Point2 20 5 `onBoundary` simplePolyFalseTODO: testcases multipolygon  hgeometryCheck if a point lies inside a polygon, on the boundary, or outside of the polygon. Running time: O(n).!Point2 1 1 `inPolygon` simplePolyInside!Point2 0 0 `inPolygon` simplePoly OnBoundary"Point2 10 0 `inPolygon` simplePoly OnBoundary"Point2 5 13 `inPolygon` simplePolyInside"Point2 5 10 `inPolygon` simplePolyInside"Point2 10 5 `inPolygon` simplePoly OnBoundary"Point2 20 5 `inPolygon` simplePolyOutsideTODO: Add some testcases with multiPolygons TODO: Add some more onBoundary testcases  hgeometry1Test if a point lies strictly inside the polgyon. 4(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?<  hgeometry'Data Type representing a convex polygon  hgeometryConvexPolygons are isomorphic to SimplePolygons with the added constraint that they have no reflex vertices.  hgeometry O(n) ! Convex hull of a simple polygon.For algorithmic details see: =https://en.wikipedia.org/wiki/Convex_hull_of_a_simple_polygon  hgeometry O(n) ' Check if a polygon is strictly convex.  hgeometry O(n) 1 Verify that a convex polygon is strictly convex.  hgeometryFinds the extreme points, minimum and maximum, in a given direction*pre: The input polygon is strictly convex.running time:  O(\log n)  hgeometryFinds the extreme maximum point in the given direction. Based on /http://geomalgorithms.com/a14-_extreme_pts.html*pre: The input polygon is strictly convex.running time:  O(\log n)  hgeometryGiven a convex polygon poly, and a point outside the polygon, find the left tangent of q and the polygon, i.e. the vertex v of the convex polygon s.t. the polygon lies completely to the right of the line from q to v.running time:  O(\log n).  hgeometryGiven a convex polygon poly, and a point outside the polygon, find the right tangent of q and the polygon, i.e. the vertex v of the convex polygon s.t. the polygon lies completely to the left of the line from q to v.running time:  O(\log n).  hgeometryRotating Right  - rotate clockwise-Merging two convex hulls, based on the paper:Two Algorithms for Constructing a Delaunay Triangulation Lee and Schachter International Journal of Computer and Information Sciences, Vol 9, No. 3, 1980: (combined hull, lower tangent that was added, upper tangent thtat was added)  hgeometry-Compute the lower tangent of the two polgyonspre: - polygons lp and rp have at least 1 vertex - lp and rp are disjoint, and there is a vertical line separating the two polygons. - The vertices of the polygons are given in clockwise orderRunning time: O(n+m), where n and m are the sizes of the two polygons respectively  hgeometry, where n and m are the sizes of the two polygons respectively  hgeometry?=  hgeometry%Tests if there are any intersections. O(n\log n)  6(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?>  hgeometry#A type representing planar ellipses  hgeometry$Ellipse representing the unit circle  hgeometry'Converting between ellipses and circles  w(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678>??  hgeometry$Data that we store in the split tree  hgeometryNon-empty sequence of points. 7(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678>?@  8(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?E  hgeometryConstruct a split treerunning time:  O(n \log n)  hgeometry5Given a split tree, generate the Well separated pairsrunning time: O(s^d n)  hgeometry2Assign the points to their the correct class. The $ class is considered the last class  hgeometry2Assign the points to their the correct class. The $ class is considered the last class  hgeometryGiven a sequence of points, whose index is increasing in the first dimension, i.e. if idx p < idx q, then p[0] < q[0]. Reindex the points so that they again have an index in the range [0,..,n'], where n' is the new number of points.running time: O(n' * d) (more or less; we are actually using an intmap for the lookups)alternatively: I can unsafe freeze and thaw an existing vector to pass it along to use as mapping. Except then I would have to force the evaluation order, i.e. we cannot be in  ( for two of the nodes at the same time.0so, basically, run reIndex points in ST as well.  hgeometrynumber of classes hgeometrylevel assignment hgeometry input points  x(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?F yNone&'(-./25678>?L~  hgeometryA dimension d has support for SoS when we can: compute a dterminant of a d+1 by d+1 dimensional matrix.  hgeometryGiven a query point q, and a vector of d points defining a hyperplane test if q lies above or below the hyperplane. Each point is assumed to have an unique index of type i that can be used to disambiguate it in case of degeneracies.some 1D examples:2sideTest (Point1 0 :+ 0) (Vector1 $ Point1 2 :+ 1)Negative3sideTest (Point1 10 :+ 0) (Vector1 $ Point1 2 :+ 1)Positive2sideTest (Point1 2 :+ 0) (Vector1 $ Point1 2 :+ 1)Positive2sideTest (Point1 2 :+ 3) (Vector1 $ Point1 2 :+ 1)Negativesome 2D examples:sideTest (Point2 1 2 :+ 0) $ Vector2 (Point2 0 0 :+ 1) (Point2 2 2 :+ 3)PositivesideTest (Point2 1 (-2) :+ 0) $ Vector2 (Point2 0 0 :+ 1) (Point2 2 2 :+ 3)NegativesideTest (Point2 1 1 :+ 0) $ Vector2 (Point2 0 0 :+ 1) (Point2 2 2 :+ 3)PositivesideTest (Point2 1 1 :+ 10) $ Vector2 (Point2 0 0 :+ 1) (Point2 2 2 :+ 3)NegativesideTest (Point2 1 1 :+ 10) $ Vector2 (Point2 0 0 :+ 3) (Point2 2 2 :+ 1)Negative  hgeometryGiven an input point, transform its number type to include symbolic $varepsilon$ expressions so that we can use SoS.  hgeometryGiven a point q and a vector of d points defining a hyperplane, test on which side of the hyperplane q lies.!TODO: Specify what the sign means zNone&'(-./25678>?M4 hgeometryGiven three points p q and r determine the orientation when going from p to r via q.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?M PQRST PRQST {None&'(-./25678>?N hgeometry(Indxec type that can disambiguate points hgeometry*a P is a 'read only' point in d dimensions|None&'(-./25678>?O hgeometry The actual implementation of SoS9(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?Q  hgeometryLine simplification with the Imai-Iri alogrithm. Given a distance value eps and a polyline pl, constructs a simplification of pl (i.e. with vertices from pl) s.t. all other vertices are within dist eps to the original polyline.Running time:  O(n^2)  time.  hgeometryGiven a function that tests if the shortcut is valid, compute a simplification using the Imai-Iri algorithm.Running time:  O(Tn^2  time, where T( is the time to evaluate the predicate.  :(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?T  hgeometryLine simplification with the well-known Douglas Peucker alogrithm. Given a distance value eps and a polyline pl, constructs a simplification of pl (i.e. with vertices from pl) s.t. all other vertices are within dist eps to the original polyline.Running time:  O(n^2)  worst case,  O(n log n)  on average.  hgeometry;Concatenate the two polylines, dropping their shared vertex  hgeometrySplit the polyline at the given vertex. Both polylines contain this vertex  hgeometryGiven a sequence of points, find the index of the point that has the Furthest distance to the LineSegment. The result is the index of the point and this distance.  ;(C) Frank Staalssee the LICENSE file Frank StaalsNone &'(-./25678>?U  hgeometry7Data type representing the solution to a linear program <(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?^  hgeometrySolves a bounded linear program in 2d. Returns Nothing if there is no solution.pre: The linear program is bounded, meaning that *the first two constraints* m1,m2 make sure th the there is no arbitrarily large/good solution. I..e. these halfspaces bound the solution in the c direction.(note that if there is only one constraint, m1, the assumption that the LP is bounded means that the contraint must be perpendicular to the objective direction. Hence, any point on the bounding plane is a solution, and they are all equally good.)O(n) expected time  hgeometry&Solves a bounded linear program (like  ) assuming that the first two constraints [m1,m2] make sure the solutions is bounded, and the other constraints already have been shuffled.  hgeometryGiven a vector v and two points a and b, determine which is smaller in direction v.  hgeometryComputes the common intersection of a nonempty list of halfines that are all colinear with the given line l.We return either the two halflines that prove that there is no counter example or we return one or two points that form form the boundary points of the range in which all halflines intersect.  hgeometry8One dimensional linear programming on lines embedded in  \mathbb{R}^d.Given an objective vector c, a line l, and a collection of half-lines hls that are all sublines of l (i.e. halfspaces *on* l), compute if there is a point inside all these halflines. If so, we actually return the one that maximizes c.running time: O(n)  hgeometryLet l be the boundary of h, and assume that we know that the new point in the common intersection must lie on h, try to find this point. In partiuclar, we find the  point in the s^.direction vector. The funtion returns Nothing if no such point exists, i.e. if there is no point on l that is contained in all halfspaces..Note that this is essentially one dinsional LP  2(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?_D  hgeometryTest if a Simple polygon is star-shaped. Returns a point in the kernel (i.e. from which the entire polygon is visible), if it exists.O(n) expected time: : }(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?` 459:6798;<>=?@ABCDEFGHOIJKLNM 459:6798;<>=?@ABCDEFGHOIJKLNM ~(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?e;  hgeometryThe result of a smallest enclosing disk computation: The smallest ball and the points defining it  hgeometryList of two or three elements  hgeometryConstruct datatype from list with exactly two or three elements. >(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?f  hgeometry Horrible  O(n^4)  implementation that simply tries all disks, checks if they enclose all points, and takes the largest one. Basically, this is only useful to check correctness of the other algorithm(s)  hgeometry#check if a disk encloses all points  =(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?gc ?(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?i  hgeometryCompute the smallest enclosing disk of a set of points, implemented using randomized incremental construction.'pre: the input has at least two points.running time: expected O(n) time, where n is the number of input points.  hgeometrySmallest enclosing disk.  hgeometry6Smallest enclosing disk, given that p should be on it.  hgeometry;Smallest enclosing disk, given that p and q should be on itrunning time: O(n)  @(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?k  hgeometry?rf  hgeometryVertices of the visibility polgyon are either original vertices or defined by some vertex and an edge  hgeometryComputes the visibility polygon of a point q in a polygon with n vertices.'pre: q lies strictly inside the polygonrunning time:  O(n\log n)  hgeometry4computes a (partial) visibility polygon of a set of n disjoint segments. The input segments are allowed to share endpoints, but no intersections or no endpoints in the interior of other segments. The input vector indicates the starting direction, the Maybe point indicates up to which point/dicrection (CCW) of the starting vector we should compute the visibility polygon.pre : - all line segments are considered closed. - no singleton linesegments exactly pointing away from q. - for every orientattion the visibility is blocked somewhere, i.e. no rays starting in the query point q that are disjoint from all segments. - no vertices at staring direction svrunning time:  O(n\log n)  hgeometryGiven two segments that share an endpoint, order them by their order around this common endpoint. I.e. if uv and uw share endpoint u we uv is considered smaller iff v is smaller than w in the counterclockwise order around u (treating the direction from q to the common endpoint as zero).  hgeometrystarting direction of the sweep hgeometry-- point indicating the last point to sweep to hgeometry6the point form which we compute the visibility polgyon  B(C) David Himmelstrupsee the LICENSE fileDavid HimmelstrupNone&'(-./25678>?s  hgeometry O(n^3)  Single-Source Shortest Path.  hgeometry O(n^3) / Single-Source Shortest Path from all vertices.  C(C) David Himmelstrupsee the LICENSE fileDavid HimmelstrupNone#$&'(-./25678>?v&  hgeometry O(n^2) >Returns triangular faces using absolute polygon point indices.  hgeometry O(n^2) >Returns triangular faces using absolute polygon point indices.  hgeometry O(n \log n)  expected time.>Returns triangular faces using absolute polygon point indices.  hgeometry O(n \log n)  expected time.>Returns triangular faces using absolute polygon point indices.  hgeometry:O(1) Z-Order hash the first half-world of each coordinate.  hgeometryO(1) Reverse z-order hash.  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?v  hgeometry O(n \log n)  hgeometry O(n \log n)  D(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?x  hgeometryConvexHull using Quickhull. The resulting polygon is given in clockwise order.running time: O(n^2)  E(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?i  hgeometry O(n \log n) time ConvexHull using Graham-Scan. The resulting polygon is given in clockwise order.  hgeometryComputes the upper hull. The upper hull is given from left to right.Specifically. A pair of points defines an edge of the upper hull iff all other points are strictly to the right of its supporting line.Note that this definition implies that the segment may be vertical. Use  ( if such an edge should not be reported.running time:  O(n\log n)  hgeometryComputes the upper hull, making sure that there are no vertical segments.*The upper hull is given from left to right  hgeometryComputes the upper hull. The upper hull is given from left to right.Specifically. A pair of points defines an edge of the lower hull iff all other points are strictly to the left of its supporting line.Note that this definition implies that the segment may be vertical. Use  ( if such an edge should not be reported.running time:  O(n\log n)  hgeometryComputes the lower hull, making sure there are no vertical segments. (Note that the only such segment could be the first segment).  hgeometryGiven a sequence of points that is sorted on increasing x-coordinate and decreasing y-coordinate, computes the upper hull, in *right to left order*.Specifically. A pair of points defines an edge of the upper hull iff all other points are strictly to the right of its supporting line.Note that In constrast to the  ; function, the result is returned *from right to left* !!!running time: O(n).  hgeometryComputes the upper hull from a sorted input. Removes the last vertical segment.running time: O(n).  F(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometry/Datatype representing a Bezier curve of degree n in d-dimensional space.  hgeometryCubic Bezier Spline  hgeometryQuadratic Bezier Spline  hgeometryBezier control points. With n degrees, there are n+1 control points.  hgeometry=Constructs the Bezier Spline from a given sequence of points.  hgeometry-Convert a quadratic bezier to a cubic bezier.  hgeometryReverse a BezierSpline  hgeometry1Evaluate a BezierSpline curve at time t in [0, 1]pre:  t \in [0,1]  hgeometryExtract a tangent vector from the first to the second control point.  hgeometry*Return the endpoints of the Bezier spline.  hgeometryRestrict a Bezier curve to the piece between parameters t < u in [0, 1].  hgeometry9Split a Bezier curve at time t in [0, 1] into two pieces.  hgeometrySplit a Bezier curve into many pieces. Todo: filter out duplicate parameter values!  hgeometryCut a Bezier curve into $x_i$-monotone pieces. Can only be solved exactly for degree 4 or smaller. Only gives rational result for degree 2 or smaller. Currentlly implemented for degree 3.  hgeometrySubdivide a curve based on a sequence of points. Assumes these points are all supposed to lie on the curve, and snaps endpoints of pieces to these points. (higher dimensions would work, but depends on convex hull)  hgeometryExtend a Bezier curve to a parameter value t outside the interval [0,1]. For t < 0, returns a Bezier representation of the section of the underlying curve from parameter value t until paramater value 0. For t > 1, the same from 1 to t.pre: t outside [0,1]  hgeometryExtend a Bezier curve to a parameter value t outside the interval [0,1]. For t < 0, returns a Bezier representation of the section of the underlying curve from parameter value t until paramater value 1. For t > 1, the same from 0 to t.pre: t outside [0,1]  hgeometryExtend a Bezier curve to a point not on the curve, but on / close to the extended underlying curve.  hgeometryMerge two Bezier pieces. Assumes they can be merged into a single piece of the same degree (as would e.g. be the case for the result of a  7 operation). Does not test whether this is the case!  hgeometryApproximate Bezier curve by Polyline with given resolution. That is, every point on the approximation will have distance at most res to the Bezier curve.  hgeometryReturn True if the curve is definitely completely covered by a line of thickness twice the given tolerance. May return false negatives but not false positives.  hgeometryGiven a point on (or within distance treshold to) a Bezier curve, return the parameter value of some point on the curve within distance treshold from p. For points farther than treshold from the curve, the function will attempt to return the parameter value of an approximate locally closest point to the input point, but no guarantees.  hgeometryGiven two Bezier curves, list all intersection points. Not exact, since for degree >= 3 there is no closed form. (In principle, this algorithm works in any dimension but this requires convexHull, area/volume, and intersect.)  hgeometry2Snap a point close to a Bezier curve to the curve.  GNone&'(-./25678>?9  hgeometryConstruct a polygon from a closed set of bezier curves. Each curve must be connected to its neighbours.  H(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometryGiven a list of non-vertical lines, computes the lower envelope using duality. The lines are given in left to right order. O(n\log n)  hgeometryGiven a list of non-vertical lines, computes the lower envelope by computing the upper convex hull. It uses the given algorithm to do sorunning time: O(time required by the given upper hull algorithm)  hgeometry=Computes the vertices of the envelope, in left to right order  hgeometryGiven two non-parallel lines, compute the intersection point and return the pair of a's associated with the lines  I(C) David Himmelstrupsee the LICENSE fileFrank Staals, David HimmelstrupNone&'(-./25678>?  hgeometryComputes the Euclidean diameter by first finding the convex hull.running time:  O(n \log n)  hgeometryComputes the Euclidean diameter by first finding the convex hull.running time:  O(n \log n)  (C) David Himmelstrupsee the LICENSE fileFrank Staals, David HimmelstrupNone&'(-./25678>?B  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  J(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometry O(n \log n) time ConvexHull using divide and conquer. The resulting polygon is given in clockwise order.  hgeometry O(n \log n) time LowerHull using divide and conquer. The resulting Hull is given from left to right, i.e. in counter clockwise order.  hgeometry O(n \log n) time UpperHull using divide and conquer. The resulting Hull is given from left to right, i.e. in clockwise order.  K(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?a  hgeometry6Given a set of red points and a set of blue points in  \mathbb{R}^2 finds a separating line (if it exists). The result is non-strict in the sense that there may be points *on* the line.running time: O(n) expected time, where n is the total number of points.  hgeometry6Given a set of red points and a set of blue points in  \mathbb{R}^2 finds a separating line (if it exists) that has all red points *right* (or on) the line, and all blue points left (or on) the line.running time: O(n) expected time, where n is the total number of points.  hgeometrygiven a red and blue point that are *NOT* vertically alligned, and all red and all blue points, try to find a non-vertical separating line.running time: O(n) expected time, where n is the total number of points.  hgeometry9Computes a strict vertical separating line, if one exists  hgeometryTest if there is a vertical separating line that has all red points to its right (or on it) and all blue points to its left (or on it). This function also returns the two extremal points; in case a line is returned, the line actually goes through the blue (second) point, if there is no line, this pair provides evidence that there is no vertical separating line.8The line we return actually goes through one blue point.  hgeometry?  hgeometry7Computes the lower hull without its vertical triangles.pre: The points are in general position. In particular, no four points should be coplanar.running time: O(n^4)  hgeometryGenerates a set of triangles to be used to construct a complete convex hull. In particular, it may contain vertical triangles.pre: The points are in general position. In particular, no four points should be coplanar.running time: O(n^4)  hgeometryTests if this is a valid triangle for the lower envelope. That is, if all point lie above the plane through these points. Returns a Maybe; if the result is a Nothing the triangle is valid, if not it returns a counter example.let t = (Triangle (ext origin) (ext $ Point3 1 0 0) (ext $ Point3 0 1 0))&isValidTriangle t [ext $ Point3 5 5 0]Nothinglet t = (Triangle (ext origin) (ext $ Point3 1 0 0) (ext $ Point3 0 1 0))*isValidTriangle t [ext $ Point3 5 5 (-10)]Just (Point3 5 5 (-10) :+ ())  hgeometry*Computes the halfspace above the triangle.upperHalfSpaceOf (Triangle (ext $ origin) (ext $ Point3 10 0 0) (ext $ Point3 0 10 0))HalfSpace {_boundingPlane = HyperPlane {_inPlane = Point3 0 0 0, _normalVec = Vector3 0 0 100}}  M(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometryCompute the convexhull using JarvisMarch. The resulting polygon is given in clockwise order.running time: O(nh), where n$ is the number of input points and h is the complexity of the hull.  hgeometry=Upepr hull from left to right, without any vertical segments.  hgeometryComputes the lower hull, from left to right. Includes vertical segments at the start.running time: O(nh), where h is the complexity of the hull.  hgeometryJarvis March to compute the lower hull, without any vertical segments.running time: O(nh), where h is the complexity of the hull.  hgeometryFind the next point in counter clockwise order, i.e. the point with minimum slope w.r.t. the given point.  hgeometryFind the next point in clockwise order, i.e. the point with maximum slope w.r.t. the given point.  N(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometryNaive algorithm to compute the closest pair according to the (squared) Euclidean distance in d dimensions. Note that we need at least two elements for there to be a closest pair.running time: O(dn^2) time.  hgeometryNaive algorithm to compute the closest pair of points (and the distance realized by those points) given a distance function. Note that we need at least two elements for there to be a closest pair.running time:  O(T(d)n^2), where T(d) is the time required to evaluate the distance between two points in  \mathbb{R}^d.  O(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometry(The vertical ray shooting data structure  hgeometryGiven a set of n interiorly pairwise disjoint *closed* segments, compute a vertical ray shooting data structure. (i.e. the endpoints of the segments may coincide).pre: no vertical segmentsrunning time:  O(n\log n) . space:  O(n\log n).  hgeometryFind the segment vertically strictly above query point q, if it exists. O(\log n)  hgeometry8Find the segment vertically query point q, if it exists. O(\log n)  hgeometryGiven a query point, find the (data structure of the) slab containing the query point O(\log n)  hgeometry6Finds the segment containing or above the query point q O(\log n)  hgeometry(Finds the first segment strictly above q O(\log n)  hgeometrygeneric searching function  hgeometryCompare based on the y-coordinate of the intersection with the horizontal line through y  hgeometryGiven an x-coordinate and a line segment that intersects the vertical line through x, compute the y-coordinate of this intersection point.note that we will pretend that the line segment is closed, even if it is not  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometryA vertex, represented by an id, location, its adjacencies, and its data.  hgeometryadjacent vertices + data on the edge. Adjacencies are given in arbitrary order/.-,3210 /.-, 3210P(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometry5Specify the planar subdivison as a tree of components  hgeometry outer face  hgeometryThis represents the following Planar subdivision. Note that the graph is undirected, the arrows are just to indicate what the Positive direction of the darts is. 1docs/Data/Geometry/PlanarSubdivision/mySubDiv.jpgmySubDiv (C) Frank Staalssee the LICENSE file Frank StaalsNone  &'(-./25678>?=  hgeometry&Note that the functor instance is in v  hgeometry#Embedded, *connected*, planar graph  hgeometryConvert to an Ext  hgeometryConstruct a plane graph from a simple polygon. It is assumed that the polygon is given in counterclockwise order..the interior of the polygon will have faceId 0pre: the input polygon is given in counterclockwise order running time: O(n).  hgeometry"Constructs a connected plane graph3pre: The segments form a single connected componentrunning time:  O(n\log n)  hgeometryGet the number of verticesnumVertices smallG4numVertices myPlaneGraph15  hgeometryGet the number of DartsnumDarts smallG10  hgeometryGet the number of EdgesnumEdges smallG5  hgeometryGet the number of facesnumFaces smallG3numFaces myPlaneGraph7  hgeometryEnumerate all verticesvertices' smallG-[VertexId 0,VertexId 1,VertexId 2,VertexId 3]  hgeometry7Enumerate all vertices, together with their vertex datamapM_ print $ vertices smallG<(VertexId 0,VertexData {_location = Point2 0 0, _vData = 0})<(VertexId 1,VertexData {_location = Point2 2 2, _vData = 1})<(VertexId 2,VertexData {_location = Point2 2 0, _vData = 2})?(VertexId 3,VertexData {_location = Point2 (-1) 4, _vData = 3})  hgeometryEnumerate all darts  hgeometry&Get all darts together with their data  hgeometry6Enumerate all edges. We report only the Positive darts  hgeometry6Lens to access the raw dart data, use at your own risk  hgeometrylens to access the Dart Data  hgeometryLens to access face data  hgeometryEnumerate all edges with their edge data. We report only the Positive darts.mapM_ print $ edges smallG(Dart (Arc 0) +1,"0->2")(Dart (Arc 1) +1,"0->1")(Dart (Arc 2) +1,"0->3")(Dart (Arc 4) +1,"1->2")(Dart (Arc 3) +1,"1->3")  hgeometry&Enumerate all faces in the plane graph  hgeometry1face Ids of all internal faces in the plane graphrunning time: O(n)  hgeometryAll faces with their face data.mapM_ print $ faces smallG(FaceId 0,"OuterFace")(FaceId 1,"A")(FaceId 2,"B") mapM_ print $ faces myPlaneGraph(FaceId 0,"OuterFace")(FaceId 1,"A")(FaceId 2,"B")(FaceId 3,"C")(FaceId 4,"E")(FaceId 5,"F")(FaceId 6,"D")  hgeometryReports the outerface and all internal faces separately. running time: O(n)  hgeometry+Reports all internal faces. running time: O(n)  hgeometry=The tail of a dart, i.e. the vertex this dart is leaving fromrunning time: O(1)tailOf (dart 0 "+1") smallG VertexId 0  hgeometry%The vertex this dart is heading in torunning time: O(1)headOf (dart 0 "+1") smallG VertexId 2  hgeometry(endPoints d g = (tailOf d g, headOf d g)running time: O(1)endPoints (dart 0 "+1") smallG(VertexId 0,VertexId 2)  hgeometryAll edges incident to vertex v, in counterclockwise order around v.running time: O(k), where k is the output size!incidentEdges (VertexId 1) smallG1[Dart (Arc 1) -1,Dart (Arc 4) +1,Dart (Arc 3) +1]5mapM_ print $ incidentEdges (VertexId 5) myPlaneGraphDart (Arc 1) -1Dart (Arc 7) +1Dart (Arc 10) +1Dart (Arc 4) -1  hgeometryAll edges incident to vertex v in incoming direction (i.e. pointing into v) in counterclockwise order around v.running time: O(k)6, where (k) is the total number of incident edges of v!incomingEdges (VertexId 1) smallG1[Dart (Arc 1) +1,Dart (Arc 4) -1,Dart (Arc 3) -1]  hgeometryAll edges incident to vertex v in incoming direction (i.e. pointing into v) in counterclockwise order around v.running time: O(k)6, where (k) is the total number of incident edges of v!outgoingEdges (VertexId 1) smallG1[Dart (Arc 1) -1,Dart (Arc 4) +1,Dart (Arc 3) +1]  hgeometryGets the neighbours of a particular vertex, in counterclockwise order around the vertex.running time: O(k), where k is the output size neighboursOf (VertexId 1) smallG"[VertexId 0,VertexId 2,VertexId 3]&neighboursOf (VertexId 5) myPlaneGraph-[VertexId 0,VertexId 6,VertexId 8,VertexId 1]  hgeometryGiven a dart d that points into some vertex v, report the next dart in the cyclic (counterclockwise) order around v.running time: O(1)%nextIncidentEdge (dart 1 "+1") smallGDart (Arc 4) +1+nextIncidentEdge (dart 1 "+1") myPlaneGraphDart (Arc 7) +1,nextIncidentEdge (dart 17 "-1") myPlaneGraphDart (Arc 15) -1  hgeometryGiven a dart d that points into some vertex v, report the previous dart in the cyclic (counterclockwise) order around v.running time: O(1)%prevIncidentEdge (dart 1 "+1") smallGDart (Arc 3) +1+prevIncidentEdge (dart 1 "+1") myPlaneGraphDart (Arc 4) -1+prevIncidentEdge (dart 7 "-1") myPlaneGraphDart (Arc 1) -1  hgeometryGiven a dart d that points away from some vertex v, report the next dart in the cyclic (counterclockwise) order around v.running time: O(1))nextIncidentEdgeFrom (dart 1 "+1") smallGDart (Arc 2) +1/nextIncidentEdgeFrom (dart 1 "+1") myPlaneGraphDart (Arc 2) +1/nextIncidentEdgeFrom (dart 4 "+1") myPlaneGraphDart (Arc 15) +1  hgeometryGiven a dart d that points into away from vertex v, report the previous dart in the cyclic (counterclockwise) order around v.running time: O(1))prevIncidentEdgeFrom (dart 1 "+1") smallGDart (Arc 0) +1/prevIncidentEdgeFrom (dart 4 "+1") myPlaneGraphDart (Arc 2) -1  hgeometry The face to the left of the dartrunning time: O(1).leftFace (dart 1 "+1") smallGFaceId 2leftFace (dart 1 "-1") smallGFaceId 1leftFace (dart 2 "+1") smallGFaceId 0leftFace (dart 2 "-1") smallGFaceId 2  hgeometry!The face to the right of the dartrunning time: O(1).rightFace (dart 1 "+1") smallGFaceId 1rightFace (dart 1 "-1") smallGFaceId 2rightFace (dart 2 "+1") smallGFaceId 2rightFace (dart 2 "-1") smallGFaceId 0  hgeometry Get the next edge along the facerunning time: O(1).nextEdge (dart 1 "+1") smallGDart (Arc 4) +1  hgeometry$Get the previous edge along the facerunning time: O(1).prevEdge (dart 1 "+1") smallGDart (Arc 0) -1  hgeometryThe darts bounding this face. The darts are reported in order along the face. This means that for internal faces the darts are reported in *clockwise* order along the boundary, whereas for the outer face the darts are reported in counter clockwise order.running time: O(k), where k is the output size.6boundary (FaceId $ VertexId 2) smallG -- around face B1[Dart (Arc 2) +1,Dart (Arc 3) -1,Dart (Arc 1) -1]:boundary (FaceId $ VertexId 0) smallG -- around outer face[Dart (Arc 0) +1,Dart (Arc 4) -1,Dart (Arc 3) +1,Dart (Arc 2) -1]  hgeometryGiven a dart d, generates the darts bounding the face that is to the right of the given dart. The darts are reported in order along the face. This means that for internal faces the darts are reported in *clockwise* order along the boundary, whereas for the outer face the darts are reported in counter clockwise order.running time: O(k), where k is the number of darts reported/boundary' (dart 2 "+1") smallG -- around face B1[Dart (Arc 2) +1,Dart (Arc 3) -1,Dart (Arc 1) -1]3boundary' (dart 0 "+1") smallG -- around outer face[Dart (Arc 0) +1,Dart (Arc 4) -1,Dart (Arc 3) +1,Dart (Arc 2) -1]  hgeometryGets a dart bounding this face. I.e. a dart d such that the face lies to the right of the dart.  hgeometryThe vertices bounding this face, for internal faces in clockwise order, for the outer face in counter clockwise order.running time: O(k), where k is the output size.9boundaryVertices (FaceId $ VertexId 2) smallG -- around B"[VertexId 0,VertexId 3,VertexId 1]boundaryVertices (FaceId $ VertexId 0) smallG -- around outerface-[VertexId 0,VertexId 2,VertexId 1,VertexId 3]mapM_ print $ boundaryVertices (FaceId $ VertexId 0) myPlaneGraph VertexId 0 VertexId 9 VertexId 10 VertexId 11 VertexId 7 VertexId 8 VertexId 12 VertexId 13 VertexId 4 VertexId 3 VertexId 2  hgeometryLens to access the vertex dataNote that using the setting part of this lens may be very expensive!! (O(n))  hgeometry/Get the location of a vertex in the plane graphNote that the setting part of this lens may be very expensive! Moreover, use with care (as this may destroy planarity etc.)  hgeometryTraverse the vertices(^.vertexData)  $ traverseVertices (i x -> Just (i,x)) smallG Just [(VertexId 0,0),(VertexId 1,1),(VertexId 2,2),(VertexId 3,3)] >>> traverseVertices (i x -> print (i,x)) smallG >> pure () (VertexId 0,0) (VertexId 1,1) (VertexId 2,2) (VertexId 3,3)  hgeometryTraverses the darts5traverseDarts (\d x -> print (d,x)) smallG >> pure () (Dart (Arc 0) +1,"0->2")(Dart (Arc 0) -1,"2->0")(Dart (Arc 1) +1,"0->1")(Dart (Arc 1) -1,"1->0")(Dart (Arc 2) +1,"0->3")(Dart (Arc 2) -1,"3->0")(Dart (Arc 3) +1,"1->3")(Dart (Arc 3) -1,"3->1")(Dart (Arc 4) +1,"1->2")(Dart (Arc 4) -1,"2->1")  hgeometryTraverses the faces5traverseFaces (\i x -> print (i,x)) smallG >> pure ()(FaceId 0,"OuterFace")(FaceId 1,"A")(FaceId 2,"B")  hgeometry.Getter for the data at the endpoints of a dartrunning time: O(1)  hgeometry/Data corresponding to the endpoints of the dartrunning time: O(1)  hgeometrygets the id of the outer facerunning time: O(n)  hgeometrygets a dart incident to the outer face (in particular, that has the outerface on its left)running time: O(n)  hgeometry"Reports all edges as line segments!mapM_ print $ edgeSegments smallG(Dart (Arc 0) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 2 0 :+ 2) :+ "0->2")(Dart (Arc 1) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 2 2 :+ 1) :+ "0->1")(Dart (Arc 2) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 (-1) 4 :+ 3) :+ "0->3")(Dart (Arc 4) +1,ClosedLineSegment (Point2 2 2 :+ 1) (Point2 2 0 :+ 2) :+ "1->2")(Dart (Arc 3) +1,ClosedLineSegment (Point2 2 2 :+ 1) (Point2 (-1) 4 :+ 3) :+ "1->3")'mapM_ print $ edgeSegments myPlaneGraph(Dart (Arc 0) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 8 (-5) :+ 9) :+ ())(Dart (Arc 1) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 8 1 :+ 5) :+ ())(Dart (Arc 2) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 4 4 :+ 1) :+ ())(Dart (Arc 3) +1,ClosedLineSegment (Point2 0 0 :+ 0) (Point2 3 7 :+ 2) :+ ())(Dart (Arc 4) +1,ClosedLineSegment (Point2 4 4 :+ 1) (Point2 8 1 :+ 5) :+ ())(Dart (Arc 15) +1,ClosedLineSegment (Point2 4 4 :+ 1) (Point2 10 4 :+ 12) :+ ())(Dart (Arc 5) +1,ClosedLineSegment (Point2 3 7 :+ 2) (Point2 0 5 :+ 3) :+ ())(Dart (Arc 6) +1,ClosedLineSegment (Point2 0 5 :+ 3) (Point2 3 8 :+ 4) :+ ())(Dart (Arc 18) +1,ClosedLineSegment (Point2 3 8 :+ 4) (Point2 9 6 :+ 13) :+ ())(Dart (Arc 7) +1,ClosedLineSegment (Point2 8 1 :+ 5) (Point2 6 (-1) :+ 6) :+ ())(Dart (Arc 10) +1,ClosedLineSegment (Point2 8 1 :+ 5) (Point2 12 1 :+ 8) :+ ())(Dart (Arc 12) +1,ClosedLineSegment (Point2 6 (-1) :+ 6) (Point2 8 (-5) :+ 9) :+ ())(Dart (Arc 8) +1,ClosedLineSegment (Point2 9 (-1) :+ 7) (Point2 12 1 :+ 8) :+ ())(Dart (Arc 14) +1,ClosedLineSegment (Point2 9 (-1) :+ 7) (Point2 14 (-1) :+ 11) :+ ())(Dart (Arc 9) +1,ClosedLineSegment (Point2 12 1 :+ 8) (Point2 10 4 :+ 12) :+ ())(Dart (Arc 11) +1,ClosedLineSegment (Point2 8 (-5) :+ 9) (Point2 12 (-3) :+ 10) :+ ())(Dart (Arc 13) +1,ClosedLineSegment (Point2 12 (-3) :+ 10) (Point2 14 (-1) :+ 11) :+ ())(Dart (Arc 16) +1,ClosedLineSegment (Point2 10 4 :+ 12) (Point2 9 6 :+ 13) :+ ())(Dart (Arc 17) +1,ClosedLineSegment (Point2 10 4 :+ 12) (Point2 8 5 :+ 14) :+ ())(Dart (Arc 19) +1,ClosedLineSegment (Point2 9 6 :+ 13) (Point2 8 5 :+ 14) :+ ())  hgeometryGiven a dart and the graph constructs the line segment representing the dart. The segment \overline{uv}) is has u as its tail and v as its head.O(1)  hgeometryThe boundary of the face as a simple polygon. For internal faces the polygon that is reported has its vertices stored in CCW order (as expected).'pre: FaceId refers to an internal face.For the other face this prodcuces a polygon in CW order (this may lead to unexpected results.) runningtime: O(k), where k is the size of the face.  hgeometryThe boundary of the face as a simple polygon. For internal faces the polygon that is reported has its vertices stored in CCW order (as expected).'pre: FaceId refers to an internal face.For the other face this prodcuces a polygon in CW order (this may lead to unexpected results.) runningtime: O(k), where k is the size of the face.  hgeometryGiven the outerFaceId and the graph, construct a sufficiently large rectangular multipolygon ith a hole containing the boundary of the outer face.  hgeometryGiven the outerface id, and a sufficiently large outer boundary, draw the outerface as a polygon with a hole.  hgeometryGiven the outerFace Id, construct polygons for all faces. We construct a polygon with a hole for the outer face.  hgeometryGiven the outerFace Id, lists all internal faces of the plane graph with their boundaries.  hgeometrylists all internal faces of the plane graph with their boundaries.  hgeometryLabels the edges of a plane graph with their distances, as specified by the distance function.  hgeometry data inside hgeometrydata outside the polygon !$#"%&)('*+ &   * )(' $#"+!% Q(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?X  hgeometry%Reads a plane graph from a bytestring  hgeometry$Writes a plane graph to a bytestring  hgeometryTransforms the plane graph into adjacency lists. For every vertex, the adjacent vertices are given in counter clockwise order.See toAdjacencyLists' for notes on how we handle self-loops.running time: O(n)  hgeometryGiven the AdjacencyList representation of a plane graph, construct the plane graph representing it. All the adjacencylists should be in counter clockwise order.running time: O(n)  hgeometry1Orders the adjacencylists of a plane graph (with n vertices) (in Adj repr) so that they are all counter-clockwise around the vertices.running time:  O(n \log n)  (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>? !$#"%&)('*+ &  * )(' $#"+!% RThe  , building block used in a Planar Subdivision(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?  hgeometry=The Face data consists of the data itself and a list of holes  hgeometry>Helper type for the data that we store in a planar subdivision  hgeometryComponentId type  hgeometry6Helper data type and type family to Wrap a proxy type.  hgeometryget the dataVal of a Raw hgeometryFace data, if the face is an inner face, store the component and faceId of it. If not, this face must be the outer face (and thus we can find all the face id's it correponds to through the FaceData).  S1Basic data types to represent a PlanarSubdivision(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?$ hgeometryA planarsubdivision is essentially a bunch of plane-graphs; one for every connected component. These graphs store the global ID's (darts, vertexId's, faceId's) in their data values. This essentially gives us a mapping between the two.note that a face may actually occur in multiple graphs, hence when we store the edges to the the holes, we store the global edgeId's rather than the local edgeId (dart)'s.%invariant: the outerface has faceId 0 hgeometryA connected component.For every face f, and every hole in this face, the facedata points to a dart d on the hole s.t. this dart has the face f on its left. i.e. leftFace d = f hgeometryA class for describing which features (vertex, edge, face) of a planar subdivision can be incident to each other. hgeometryData type that expresses whether or not we are inside or outside the polygon. hgeometryLens to access a particular component of the planar subdivision. hgeometry0Constructs a planarsubdivision from a PlaneGraph runningTime: O(n) hgeometryGiven a (connected) PlaneGraph and a dart that has the outerface on its left | Constructs a planarsubdivision runningTime: O(n) hgeometryConstruct a plane graph from a simple polygon. It is assumed that the polygon is given in counterclockwise order..the interior of the polygon will have faceId 0pre: the input polygon is given in counterclockwise order running time: O(n). hgeometry*Constructs a connected planar subdivision.pre: the segments form a single connected component running time:  O(n\log n) hgeometryGet the number of verticesnumVertices myGraph1 hgeometryGet the number of verticesnumVertices myGraph4 hgeometryGet the number of DartsnumDarts myGraph12 hgeometryGet the number of EdgesnumEdges myGraph6 hgeometry O(1) . Get the number of facesnumFaces myGraph4 hgeometryEnumerate all verticesvertices' myGraph-[VertexId 0,VertexId 1,VertexId 2,VertexId 3] hgeometry7Enumerate all vertices, together with their vertex data hgeometryEnumerate all darts hgeometry6Enumerate all edges. We report only the Positive darts hgeometryEnumerate all edges with their edge data. We report only the Positive darts.mapM_ print $ edges myGraph(Dart (Arc 2) +1,"c+")(Dart (Arc 1) +1,"b+")(Dart (Arc 0) +1,"a+")(Dart (Arc 5) +1,"g+")(Dart (Arc 4) +1,"e+")(Dart (Arc 3) +1,"d+") hgeometry O(n) . Vector of all primal faces. hgeometry O(n) . Vector of all primal faces. hgeometry O(n) 2. Vector of all primal faces with associated data. hgeometryEnumerates all faces with their face data exlcluding the outer face hgeometrylens to access the Dart Data hgeometryLens to the facedata of the faces themselves. The indices correspond to the faceIds hgeometryLens to the facedata of the vertexdata themselves. The indices correspond to the vertexId's hgeometry=The tail of a dart, i.e. the vertex this dart is leaving fromrunning time: O(1) hgeometry%The vertex this dart is heading in torunning time: O(1) hgeometry(endPoints d g = (tailOf d g, headOf d g)running time: O(1) hgeometryAll edges incident to vertex v, in counterclockwise order around v.running time: O(k), where k! is the number of edges reported. hgeometryGiven a dart d that points into some vertex v, report the next dart in the cyclic (counterclockwise) order around v.running time: O(1) hgeometryGiven a dart d that points into some vertex v, report the previous dart in the cyclic (counterclockwise) order around v.running time: O(1)%prevIncidentEdge (dart 1 "+1") smallGDart (Arc 3) +1 hgeometryGiven a dart d that points away from some vertex v, report the next dart in the cyclic (counterclockwise) order around v.running time: O(1) hgeometryGiven a dart d that points into away from vertex v, report the previous dart in the cyclic (counterclockwise) order around v.running time: O(1) hgeometryAll edges incident to vertex v in incoming direction (i.e. pointing into v) in counterclockwise order around v.running time: O(k)6, where (k) is the total number of incident edges of v hgeometryAll edges incident to vertex v in outgoing direction (i.e. pointing away from v) in counterclockwise order around v.running time: O(k)6, where (k) is the total number of incident edges of v hgeometryGets the neighbours of a particular vertex, in counterclockwise order around the vertex.running time: O(k), where k is the output size hgeometry The face to the left of the dartrunning time: O(1). hgeometry!The face to the right of the dartrunning time: O(1). hgeometryThe darts on the outer boundary of this face. The darts are reported in order along the face. This means that for internal faces the darts are reported in *clockwise* order along the boundary, whereas for the outer face the darts are reported in counter clockwise order.running time: O(k), where k is the output size. hgeometry3Get the local face and component from a given face. hgeometryThe vertices of the outer boundary of the face, for internal faces in clockwise order, for the outer face in counter clockwise order.running time: O(k), where k is the output size. hgeometryLists the holes in this face, given as a list of darts to arbitrary darts on those faces. The returned darts are on the outside of the hole, i.e. they are incident to the given input face:/all (\d -> leftFace d ps == fi) $ holesOf fi psrunning time: O(k), where k! is the number of darts returned. hgeometry7Get the location of a vertex in the planar subdivision.Note that the setting part of this lens may be very expensive! Moreover, use with care (as this may destroy planarity etc.) hgeometryLens to get the face data of a particular face. Note that the setting part of this lens may be very expensive! (O(n)) hgeometry/Traverse the vertices of the planar subdivision hgeometry,Traverse the darts of the Planar subdivision hgeometry-Traverse the faces of the planar subdivision. hgeometryMap with index over all faces hgeometry Map with index over all vertices hgeometryMap with index over all darts hgeometry.Getter for the data at the endpoints of a dartrunning time: O(1) hgeometry/data corresponding to the endpoints of the dartrunning time: O(1) hgeometrygets the id of the outer facerunning time: O(1) hgeometry"Reports all edges as line segments hgeometryGiven a dart and the subdivision constructs the line segment representing it. The segment \overline{uv}) is has u as its tail and v as its head.O(1) hgeometryGiven a dart d, generates the darts on (the current component of) the boundary of the the face that is to the right of the given dart. The darts are reported in order along the face. This means that for(the outer boundary of an) internal faces the darts are reported in *clockwise* order along the boundary,the "inner" boundary of a face, i.e. the boundary of ahole, the darts are reported in *counter clockwise* order.Note that this latter case means that in the darts of a a component of the outer face are reported in counter clockwise order.O(k), where k is the number of darts reported hgeometryThe outerboundary of the face as a simple polygon. For internal faces the polygon that is reported has its vertices stored in CCW order (as expected).'pre: FaceId refers to an internal face.O(k), where k5 is the complexity of the outer boundary of the face hgeometry*Constructs the boundary of the given face.O(k), where k is the complexity of the face hgeometryReturns a sufficiently large, rectangular, polygon that contains the entire planar subdivision. Each component corresponds to a hole in this polygon. hgeometryGiven a sufficiently large outer boundary, draw the outerface as a polygon with a hole. hgeometryProcuces a polygon for each *internal* face of the planar subdivision. hgeometry;Procuces a polygon for each face of the planar subdivision. hgeometry/Mapping between the internal and extenral darts hgeometryGiven two features (vertex, edge, or face) of a subdivision, report all features of a given type that are incident to both. hgeometryGiven two features (edge or face) of a subdivision, report all vertices that are incident to both. hgeometryGiven two features (vertex or face) of a subdivision, report all edges that are incident to both. Returns both darts of each qualifying edge. hgeometryGiven two features (vertex or edge) of a subdivision, report all faces that are incident to both. hgeometry data inside hgeometrydata outside the polygon !$#"%&)('*+ !%   & *)(' $#"+  T-Functions for merging two planar subdivisions(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?9 hgeometryMerge a pair of *disjoint* planar subdivisions, unifying their outer face. The given function is used to merge the data corresponding to the outer face. The subdivisions are merged pairwise, no guarantees are given about the order in which they are merged. Hence, it is expected that f is commutative.running time:  O(n\log n), where n( is the total size of the subdivisions. hgeometryMerge a pair of *disjoint* planar subdivisions, unifying their outer face. For the outerface data it simply takes the data of the first subdivision. runningtime: O(n) hgeometryMerge a pair of *disjoint* planar subdivisions. In particular, this function unifies the structure assuming that the two subdivisions share the outer face. runningtime: O(n) hgeometryThe disjoint "holes" hgeometryHow to merge the face data hgeometry-Face in which to embed the given subdivisions hgeometrythe outer subdivision hgeometryThe hole hgeometry-How to merge the face data (hole value first) hgeometry-Face in which to embed the given subdivisions hgeometrythe outer subdivision hgeometry'how to merge the data of the outer faceU(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?! hgeometry5Constructs a planar subdivision from a collection of k( disjoint polygons of total complexity O(n).pre: The boundary of the polygons is given in counterclockwise orientation runningtime: O(n\log n\log k)& in case of polygons with holes, and  O(n\log k) in case of simple polygons. hgeometry Version of  that accepts   s as input. hgeometryConstruct a planar subdivision from a polygon. Since our PlanarSubdivision models only connected planar subdivisions, this may add dummy/invisible edges.pre: The outer boundary of the polygons is given in counterclockwise orientationrunning time: O(n) for a simple polygon,  O(n\log n) for a polygon with holes. hgeometryouter face data hgeometrythe disjoint polygons hgeometryouter face data hgeometrythe disjoint polygons hgeometry data inside hgeometrydata outside the polygon !$#"%&()('*+ V(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?' hgeometry$Planar Point Location Data structure hgeometryData structure for fast InPolygon Queries newtype InPolygonDS v r = InPolygonDS (VRS.VerticalRayShootingStructure (Vertex v r) () r) deriving (Show,Eq) hgeometryBuilds a pointlocation data structure on the planar subdivision with n vertices.running time:  O(n\log n) . space:  O(n\log n). hgeometryLocates the first edge (dart) strictly above the query point. returns Nothing if the query point lies in the outer face and there is no dart above it.running time:  O(\log n) hgeometry,Locates the face containing the query point.running time:  O(\log n) hgeometry:Locates the faceId of the face containing the query point.If the query point lies *on* an edge, an arbitrary face incident to the edge is returned.running time:  O(\log n) hgeometry8Finds the edge on or above the query point, if it exists hgeometryReturns if a query point lies in (or on the boundary of) the polygon. O(\log n)(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?'WNone&'(-./25678>?*d hgeometrySplits a given edge of a planar subdivision by inserting a new vertex on the edges. Increases  vertices and  edges by 1. hgeometrySprouts a new edge from a given vertex into the interior of a given (incident) face. Increases  vertices and  edges by 1. hgeometryInserts a new edge between two given vertices, adjacent to a common face. Increases  edges and  faces by 1. hgeometrySplits a given edge of a planar subdivision by inserting a new vertex on the edges. Increases  vertices and  edges by 1.X(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?2 hgeometry;Data type representing a two dimensional planar arrangement hgeometryBuilds an arrangement of n linesrunning time:  O(n^2\log n hgeometryConstructs the arrangemnet inside the box. note that the resulting box may be larger than the given box to make sure that all vertices of the arrangement actually fit.running time:  O(n^2\log n hgeometryConstructs the arrangemnet inside the box. (for parts to be useful, it is assumed this boxfits at least the boundingbox of the intersections in the Arrangement) hgeometry5Constructs a boundingbox containing all intersectionsrunning time: O(n^2), where n is the number of input lines hgeometryComputes all intersections hgeometry1Computes the intersections with a particular side hgeometryConstructs the unbounded intersections. Reported in clockwise direction. hgeometryLinks the vertices of the outer boundary with those in the subdivision hgeometryGiven a predicate that tests if two elements of a CSeq match, find a rotation of the seqs such at they match.Running time: O(n) hgeometryGiven an Arrangement and a line in the arrangement, follow the line through he arrangement. hgeometry4Find the starting point of the line the arrangement hgeometryGiven a point on the boundary of the boundedArea box; find the vertex this point corresponds to.running time:  O(\log n)basically; maps every point to a tuple of the point and the side the point occurs on. We then binary search to find the point we are looking for. hgeometryFind the starting dart of the given vertex v. Reports a dart s.t. tailOf d = v running me: O(k) where k is the degree of the vertex hgeometryGiven a dart d that incoming to v (headOf d == v), find the outgoing dart colinear with the incoming one. Again reports dart d' s.t. tailOf d' = vrunning time: O(k)1, where k is the degree of the vertex d points to(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?3Y(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?7 hgeometryAfter triangulation, edges are either from the original polygon or a new diagonal. hgeometryGiven a list of original edges and a list of diagonals, creates a planar-subdivisionrunning time:  O(n\log n) hgeometryGiven a list of original edges and a list of diagonals, creates a planar-subdivisionrunning time:  O(n\log n) hgeometry3A counter-clockwise edge along the outer boundary hgeometryremaining original edges hgeometry diagonals hgeometry3A counter-clockwise edge along the outer boundary hgeometryremaining original edges hgeometry diagonalsZ(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?9 hgeometry$assigns a vertex type to each vertexpre: Both the outer boundary and the inner boundary of the polygon are given in CCW order.running time: O(n). hgeometryGiven a polygon, find a set of non-intersecting diagonals that partition the polygon into y-monotone pieces.running time:  O(n\log n) hgeometryComputes a set of diagionals that decompose the polygon into y-monotone pieces.=pre: the polygon boundary is given in counterClockwise order.running time:  O(n\log n)  [(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>???- hgeometryTriangulates a polygon of n verticesrunning time:  O(n \log n) hgeometryTriangulates a polygon of n verticesrunning time:  O(n \log n) hgeometryComputes a set of diagaonals that together triangulate the input polygon of n vertices.running time:  O(n \log n) hgeometryComputes 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)](C) David Himmelstrupsee the LICENSE fileDavid HimmelstrupNone#$&'(-./25678>?@ hgeometrySingle-source shortest paths tree. Both keys and values are vertex offset ints. parentOf(i) = sssp[i] hgeometry O(n \log n)  hgeometry O(n)  Single-Source shortest path.^(C) David Himmelstrupsee the LICENSE fileDavid HimmelstrupNone&'(-./25678>?B hgeometryPoints annotated with an  indicate that the edge from this point to the next should not be a straight line but instead an arc with a given center and a given border edge. hgeometry O(n \log n) (C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?B_(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?Gz  hgeometry3Bidirectional mapping between points and VertexIDs. hgeometryNeighbours are stored in clockwise order: i.e. rotating right moves to the next clockwise neighbour. hgeometryNeighbours indexed by VertexID. hgeometryRotating Right  - rotate clockwise hgeometryVertex identifier. hgeometryMapping between triangulated points and their internal VertexID. hgeometry$Point positions indexed by VertexID. hgeometry%Point neighbours indexed by VertexID. hgeometryList add edges as point pairs. hgeometry!List add edges as VertexID pairs. hgeometry*ST' is a strict triple (m,a,x) containing:m: a Map, mapping edges, represented by a pair of vertexId's (u,v) with u < v, to arcId's."a: the next available unused arcIDx: the data value we are interested in computing type ST' a = ST (SM.Map (VertexID,VertexID) ArcID) ArcID a2convert the triangulation into a planarsubdivisionrunning time: O(n). hgeometry,convert the triangulation into a plane graphrunning time: O(n).`(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?K hgeometryNaive  O(n^4)  time implementation of the delaunay triangulation. Simply tries each triple (p,q,r) and tests if it is delaunay, i.e. if there are no other points in the circle defined by p, q, and r.pre: the input is a *SET*, i.e. contains no duplicate points. (If the input does contain duplicate points, the implementation throws them away) hgeometryGiven a list of edges, as vertexId pairs, construct a vector with the adjacency lists, each in CW sorted order. hgeometryGiven a particular point u and a list of points vs, sort the points vs in CW order around u. running time:  O(m log m) 1, where m=|vs| is the number of vertices to sort. hgeometry0Given a list of faces, construct a list of edges hgeometry O(n)  Test if the given three points form a triangle in the delaunay triangulation.a(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?M~ hgeometry7Computes the delaunay triangulation of a set of points.Running time:  O(n \log n) (note: We use an IntMap in the implementation. So maybe actually  O(n \log^2 n))pre: the input is a *SET*, i.e. contains no duplicate points. (If the input does contain duplicate points, the implementation throws them away)b(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?Ok hgeometryComputes the Euclidean Minimum Spanning Tree. We compute the Delaunay Triangulation (DT), and then extract the EMST. Hence, the same restrictions apply as for the DT:pre: the input is a *SET*, i.e. contains no duplicate points. (If the input does contain duplicate points, the implementation throws them away)running time:  O(n \log n)(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?OcData type to represent a camera and some functions for working with it.(C) Frank Staalssee the LICENSE file Frank StaalsNone&'(-./25678>?V hgeometry0A basic camera data type. The fields stored are:the camera position,the raw camera normal, i.e. a unit vector into the center of the screen,the raw view up vector indicating which side points "upwards" in the scene,the viewplane depth (i.e. the distance from the camera position to the plane on which we project),;the near distance (everything closer than this is clipped),the far distance (everything further away than this is clipped), andthe screen dimensions. hgeometryCamera position. hgeometryRaw camera normal, i.e. a unit vector into the center of the screen. hgeometryRaw view up vector indicating which side points "upwards" in the scene. hgeometryViewplane depth (i.e. the distance from the camera position to the plane on which we project). hgeometry7Near distance (everything closer than this is clipped). hgeometry?Y hgeometry"Rendering function for a triangle. hgeometryRender a point hgeometryRenders a line segment hgeometryGeneric Rendering Function hgeometryProjection function hgeometryThe camera transform hgeometryThe thing we wish to transformhhfffff                                                                                                                                      jjjjjjjjjjjjjjjjkkkkkkkkkkkkkkkkkklllllmmmmmmmmppppppppppppppppppppppqssssssssssss  !!!!!!!!!!!!!!!!!!!!!!!!!!!"##################$$$$$$$$$$$$$$$$$$$$$$$$$$%%%%%%%%%%%&&&&&&&&&&&&&&&&&&&&'''''''''''''''''''''''''''''''''''''(((((((((((((((((((((((((((()))))))))*********************************+++++++++++++++++++++ + + + + + + + , , , - - - -- - - - --- - - - - - - - - -- - - - - - - - - - - - - - --. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . / / / / / / / / / / / / / / / / / / / / / 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 00 0 00 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 t t t t t t t t t t t t t t t t t t t tt t tt t t t t t t t t t t t t t t t t t t t t t t t t t t t t u u 3 3 3 3 3 v v v 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 www w w w w w w w w w w w w w w w w w w w www w w w w w w 8 8 8 8 8 y y y y 9 9 : : : : ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; < < < < < < < < 2 2 2 ~ ~ ~ ~ ~ ~~ ~ ~ ~ > > ? ? ? ? @ @ @ A A A AA A A A A A B B C C C C C C   D E E E E E E E F F F F F F F F F F FF F F F F F F F F F F F F F F F F F F F F F G G G G G G G G G H H H H H H I I J J J J J J J K K K K K K L L L L L M M M M M M M N NN O O O O O O O O O O O O O O OO O O             P P P P P P P P P P P P P P P P P                                                                                   Q Q Q Q Q Q Q Q Q Q R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R R RR R R R R R R R R R R R S S S S S S S S S S SSS S S S S S S S S S S S S S S S S S S S S SS S S S S S SS S S S S S S S S S S S S S S S S S S S S S S S S S S SS S S S S S S S S S S S S S S S SSSSSSSSSSTTTT TUUUUUVVVVVVVVV VV VVVVVVVVVVVVVVVVVWWWWXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXYYYYYYYYZZZZZZZZZZZZZ[[[[[[\\\\]]] ]]]]]]]]]]]]]^^^^^^__________________`````abccccccccccccccccccccddddeeeeeeeeeeeeee ejjkllllloppssssss00ttttttttt4zzzzz{{{{{|%hgeometry-0.13-8qLvB9JVk1yDS01KUXpxiUData.Geometry.Vector"Data.Geometry.LineSegment.InternalData.PlaneGraph.CoreData.PlaneGraph.AdjRepAlgorithms.Geometry.SoS Algorithms.Geometry.SoS.SymbolicData.Geometry.DirectionsData.Geometry.Interval.UtilData.Geometry.PropertiesData.Geometry.IntervalData.Geometry.IntervalTreeData.Geometry.RangeTree.MeasureData.Geometry.RangeTree.Generic!Data.Geometry.SegmentTree.Generic Data.Geometry.Vector.VectorFixed&Data.Geometry.Vector.VectorFamilyPeano!Data.Geometry.Vector.VectorFamilyData.Geometry.PointData.Geometry.RangeTree Data.Geometry.PrioritySearchTree,Algorithms.Geometry.FrechetDistance.Discrete0Algorithms.Geometry.ClosestPair.DivideAndConquerData.Geometry.MatrixData.Geometry.TransformationData.Geometry.Line.InternalData.Geometry.SubLineData.Geometry.Box.Internal+Algorithms.Geometry.LineSegmentIntersection1Algorithms.Geometry.LineSegmentIntersection.Naive:Algorithms.Geometry.LineSegmentIntersection.BentleyOttmannData.Geometry.Box.Corners Data.Geometry.QuadTree.QuadrantsData.Geometry.Box.SidesData.Geometry.BoxData.Geometry.BoundaryData.Geometry.QuadTree.CellData.Geometry.QuadTree.SplitData.Geometry.QuadTree.TreeData.Geometry.QuadTreeData.Geometry.PolyLineData.Geometry.LineData.Geometry.SlabData.Geometry.HyperPlaneData.Geometry.DualityData.Geometry.KDTreeData.Geometry.HalfLineData.Geometry.HalfSpaceData.Geometry.BallData.Geometry.TriangleData.Geometry.PolygonData.Geometry.Polygon.MonotoneData.Geometry.Polygon.Convex8Algorithms.Geometry.LineSegmentIntersection.BooleanSweepData.Geometry.Ellipse8Algorithms.Geometry.WellSeparatedPairDecomposition.TypesAlgorithms.Geometry.WSPD2Algorithms.Geometry.PolyLineSimplification.ImaiIri9Algorithms.Geometry.PolyLineSimplification.DouglasPeucker+Algorithms.Geometry.LinearProgramming.Types-Algorithms.Geometry.LinearProgramming.LP2DRIC)Algorithms.Geometry.SmallestEnclosingBall/Algorithms.Geometry.SmallestEnclosingBall.Naive-Algorithms.Geometry.SmallestEnclosingBall.RIC"Algorithms.Geometry.Diameter.Naive)Algorithms.Geometry.VisibilityPolygon.LeeAlgorithms.Geometry.SSSP.Naive0Algorithms.Geometry.PolygonTriangulation.EarClip(Algorithms.Geometry.ConvexHull.QuickHull)Algorithms.Geometry.ConvexHull.GrahamScanData.Geometry.BezierSplineData.Geometry.Polygon.Bezier(Algorithms.Geometry.LowerEnvelope.DualCH'Algorithms.Geometry.Diameter.ConvexHull/Algorithms.Geometry.ConvexHull.DivideAndConquer(Algorithms.Geometry.RedBlueSeparator.RIC$Algorithms.Geometry.ConvexHull.Naive*Algorithms.Geometry.ConvexHull.JarvisMarch%Algorithms.Geometry.ClosestPair.Naive1Data.Geometry.VerticalRayShooting.PersistentSweep'Data.Geometry.PlanarSubdivision.TreeRepData.PlaneGraph.IO#Data.Geometry.PlanarSubdivision.Raw%Data.Geometry.PlanarSubdivision.Basic%Data.Geometry.PlanarSubdivision.MergeData.Geometry.PlanarSubdivision+Data.Geometry.PointLocation.PersistentSweep'Data.Geometry.PlanarSubdivision.Dynamic"Data.Geometry.Arrangement.Internal.Algorithms.Geometry.PolygonTriangulation.Types5Algorithms.Geometry.PolygonTriangulation.MakeMonotone