hgeometry-0.5.0.0: Geometric Algorithms, Data structures, and Data types.

Data.Geometry.Polygon.Convex

Description

Synopsis

# Documentation

merge :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> (ConvexPolygon p r, LineSegment 2 p r, LineSegment 2 p r) Source

Rotating 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)

lowerTangent :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> LineSegment 2 p r Source

Compute the lower tangent of the two polgyons

pre: - 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 order

Running time: O(n+m), where n and m are the sizes of the two polygons respectively

upperTangent :: (Num r, Ord r) => ConvexPolygon p r -> ConvexPolygon p r -> LineSegment 2 p r Source

Compute the upper tangent of the two polgyons

pre: - 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 order

Running time: O(n+m), where n and m are the sizes of the two polygons respectively

isLeftOf :: (Num r, Ord r) => (Point 2 r :+ p) -> (Point 2 r :+ p', Point 2 r :+ p'') -> Bool Source

isRightOf :: (Num r, Ord r) => (Point 2 r :+ p) -> (Point 2 r :+ p', Point 2 r :+ p'') -> Bool Source

extremes :: (Num r, Ord r) => Vector 2 r -> ConvexPolygon p r -> (Point 2 r :+ p, Point 2 r :+ p) Source

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

pre: The input polygon is strictly convex.

running time: \$O(log n)\$

maxInDirection :: (Num r, Ord r) => Vector 2 r -> ConvexPolygon p r -> Point 2 r :+ p Source

Finds 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^2 n)\$