Copyright | (C) Frank Staals |
---|---|

License | see the LICENSE file |

Maintainer | Frank Staals |

Safe Haskell | None |

Language | Haskell2010 |

The \(O((n+k)\log n)\) time line segment intersection algorithm by Bentley and Ottmann.

## Synopsis

- intersections :: (Ord r, Fractional r) => [LineSegment 2 p r] -> Intersections p r
- interiorIntersections :: (Ord r, Fractional r) => [LineSegment 2 p r] -> Intersections p r
- ordAt :: (Fractional r, Ord r) => r -> Compare (LineSegment 2 p r)
- xCoordAt :: (Fractional r, Ord r) => r -> LineSegment 2 p r -> r

# Documentation

intersections :: (Ord r, Fractional r) => [LineSegment 2 p r] -> Intersections p r Source #

Compute all intersections

\(O((n+k)\log n)\), where \(k\) is the number of intersections.

interiorIntersections :: (Ord r, Fractional r) => [LineSegment 2 p r] -> Intersections p r Source #

Computes 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.

ordAt :: (Fractional r, Ord r) => r -> Compare (LineSegment 2 p r) Source #

Compare based on the x-coordinate of the intersection with the horizontal line through y

xCoordAt :: (Fractional r, Ord r) => r -> LineSegment 2 p r -> r Source #

Given 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