| Copyright | (C) David Himmelstrup |
|---|---|
| License | see the LICENSE file |
| Maintainer | David Himmelstrup |
| Safe Haskell | None |
| Language | Haskell2010 |
Algorithms.Geometry.SSSP
Description
Synopsis
- type SSSP = Vector Int
- triangulate :: (Ord r, Fractional r) => SimplePolygon p r -> PlaneGraph s Int PolygonEdgeType PolygonFaceData r
- sssp :: (Ord r, Fractional r) => PlaneGraph s Int PolygonEdgeType PolygonFaceData r -> SSSP
- visibilityDual :: forall s r. (Ord r, Fractional r) => PlaneGraph s Int PolygonEdgeType PolygonFaceData r -> Dual r
- visibilityFinger :: forall r. (Fractional r, Ord r, Show r) => Dual r -> [Either (Int, Int, Int) (Point 2 r)]
- visibilitySensitive :: forall s r. (Ord r, Fractional r, Show r) => PlaneGraph s Int PolygonEdgeType PolygonFaceData r -> SimplePolygon () r
Documentation
type SSSP = Vector Int Source #
Single-source shortest paths tree. Both keys and values are vertex offset ints.
parentOf(i) = sssp[i]
triangulate :: (Ord r, Fractional r) => SimplePolygon p r -> PlaneGraph s Int PolygonEdgeType PolygonFaceData r Source #
\( O(n \log n) \)
sssp :: (Ord r, Fractional r) => PlaneGraph s Int PolygonEdgeType PolygonFaceData r -> SSSP Source #
\( O(n) \) Single-Source shortest path.
visibilityDual :: forall s r. (Ord r, Fractional r) => PlaneGraph s Int PolygonEdgeType PolygonFaceData r -> Dual r Source #
visibilityFinger :: forall r. (Fractional r, Ord r, Show r) => Dual r -> [Either (Int, Int, Int) (Point 2 r)] Source #
visibilitySensitive :: forall s r. (Ord r, Fractional r, Show r) => PlaneGraph s Int PolygonEdgeType PolygonFaceData r -> SimplePolygon () r Source #