| Copyright | (C) Frank Staals |
|---|---|
| License | see the LICENSE file |
| Maintainer | Frank Staals |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.LinearProgramming.LP2DRIC
Description
2D Linear programming in expected linear time.
Synopsis
- solveBoundedLinearProgram :: (MonadRandom m, Ord r, Fractional r) => LinearProgram 2 r -> m (Maybe (Point 2 r))
- solveBoundedLinearProgram' :: (Ord r, Fractional r) => LinearProgram 2 r -> Maybe (Point 2 r)
- maximumOn :: (Ord r, Fractional r) => LPState 2 r -> Line 2 r -> Maybe (Point 2 r)
- oneDLinearProgramming :: (Ord r, Num r, Arity d) => Vector d r -> Line d r -> [HalfLine d r] -> Maybe (Point d r)
- commonIntersection :: (Ord r, Num r, Arity d) => Line d r -> NonEmpty (HalfLine d r :+ a) -> Either (Two (HalfLine d r :+ a)) (OneOrTwo (Point d r :+ a))
- cmpHalfPlane :: (Ord r, Num r, Arity d) => Vector d r -> Point d r -> Point d r -> Ordering
Documentation
solveBoundedLinearProgram :: (MonadRandom m, Ord r, Fractional r) => LinearProgram 2 r -> m (Maybe (Point 2 r)) Source #
Solves 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
solveBoundedLinearProgram' :: (Ord r, Fractional r) => LinearProgram 2 r -> Maybe (Point 2 r) Source #
Solves a bounded linear program (like solveBoundedLinearProgram)
assuming that the first two constraints [m1,m2] make sure the solutions is
bounded, and the other constraints already have been shuffled.
maximumOn :: (Ord r, Fractional r) => LPState 2 r -> Line 2 r -> Maybe (Point 2 r) Source #
Let 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 maximum 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
oneDLinearProgramming :: (Ord r, Num r, Arity d) => Vector d r -> Line d r -> [HalfLine d r] -> Maybe (Point d r) Source #
One 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)\)
commonIntersection :: (Ord r, Num r, Arity d) => Line d r -> NonEmpty (HalfLine d r :+ a) -> Either (Two (HalfLine d r :+ a)) (OneOrTwo (Point d r :+ a)) Source #
Computes 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.