SegmentIntersections.jl

An implementation of the Bentley-Ottmann algorithm written in Julia.
Author arnauqb
Popularity
1 Star
Updated Last
3 Years Ago
Started In
March 2021

CI codecov

SegmentIntersections.jl

This package implements two algorithms for computing the intersection points between a set of finite segments.

  • A brute force algorithm, in which each segment is tested for intersection against all the other segments. The scaling of this algorithm is thus O(N^2).
  • The Bentley-Ottmann algorithm which should scale much better for a high number of points. However, in many situations the brute force performs better. This could also be because of the BO algorithm needs a bit of memory optimization.

image

The intersections for a complete K-graph need to be debugged, probably a toleranece error.

image

Limitations

The algorithm ignores purely horizontal and vertical segments. This will probably be implemented in the future.

Used By Packages

No packages found.