public final class MultiLineIntersection
extends java.lang.Object
LineD
instances:
find(org.kynosarges.tektosyne.geometry.LineD[])
provides a sweep line algorithm which is very
efficient if the number of intersections is much smaller than the number of lines.
findSimple(org.kynosarges.tektosyne.geometry.LineD[])
provides a brute force algorithm which is
better suited for a small number of lines or a large number of intersections.
MultiLinePoint
instance created for each point identifies all line segments
that contain the point. Please refer to the two methods for further details.
The sweep line algorithm implemented by find(org.kynosarges.tektosyne.geometry.LineD[])
was first
described by J. L. Bentley and T. A. Ottmann, Algorithms for reporting and counting
geometric intersections, IEEE Transactions on Computers C-28 (1979), p.643-647.
An implementation outline is given by Mark de Berg et al., Computational Geometry
(3rd ed.), Springer-Verlag 2008, p.20-29, and a limited C++ implementation by Michael J. Laszlo,
Computational Geometry and Computer Graphics in C++, Prentice Hall 1996, p.173-181.
Our implementation supports an unlimited number of line segments meeting at any intersection point, and uses an improved sweep line comparer that raises the algorithm’s stability to the same level as that of the brute force algorithm. A comment block at the top of the source code file gives a detailed description of this comparer.
Modifier and Type | Method and Description |
---|---|
static MultiLinePoint[] |
find(LineD[] lines)
Finds all intersections between the specified line segments, using a sweep line algorithm.
|
static MultiLinePoint[] |
findSimple(LineD[] lines)
Finds all intersections between the specified line segments, using a brute force algorithm.
|
static MultiLinePoint[] |
findSimple(LineD[] lines,
double epsilon)
Finds all intersections between the specified line segments, using a brute force algorithm
with the specified epsilon for coordinate comparisons.
|
static LineD[] |
split(LineD[] lines,
MultiLinePoint[] crossings)
Splits the specified line segments on the specified intersection points.
|
public static MultiLinePoint[] find(LineD[] lines)
lines
, testing only those elements
for intersection which are adjacent along the sweep line. The runtime is O((n + k) log n)
where k is the number of discovered intersections.
find
is very efficient when there are no or few intersections, achieving its best
performance if the specified lines
are horizontal parallels. However, the event point
schedule and sweep line structure impose a large overhead if there are many candidate lines
to consider. The worst case of O(n^2) intersections is much slower than the brute force
algorithm implemented by findSimple(org.kynosarges.tektosyne.geometry.LineD[])
.
find
always uses exact coordinate comparisons. Epsilon comparisons would corrupt
the search structures due to the merging of nearby event points. Call findSimple(org.kynosarges.tektosyne.geometry.LineD[])
with an epsilon argument to use epsilon comparisons.
lines
- a LineD
array containing the line segments to intersectMultiLinePoint
array describing
all points of intersection between the specified lines
java.lang.IllegalArgumentException
- if lines
contains a LineD
whose LineD.start
and LineD.end
points are equaljava.lang.IllegalStateException
- if the search structure was corruptedjava.lang.NullPointerException
- if lines
or any of its elements is null
public static MultiLinePoint[] findSimple(LineD[] lines)
lines
element with every other element.
The runtime is therefore always O(n^2), regardless of the number of intersections found.
However, the constant factor is low and O(n^2) intersections are found in optimal time because
findSimple
performs no additional work to avoid testing for possible intersections.
For a small number of lines
(n < 50), findSimple
usually beats the sweep
line algorithm implemented by find(org.kynosarges.tektosyne.geometry.LineD[])
regardless of the number of intersections.
lines
- a LineD
array containing the line segments to intersectMultiLinePoint
array describing
all points of intersection between the specified lines
java.lang.NullPointerException
- if lines
or any of its elements is null
public static MultiLinePoint[] findSimple(LineD[] lines, double epsilon)
findSimple(LineD[])
overload, but uses the
specified epsilon
to determine intersections between the specified
lines
and to combine nearby intersections.lines
- a LineD
array containing the line segments to intersectepsilon
- the maximum absolute difference at which coordinates should be considered equalMultiLinePoint
array describing
all points of intersection between the specified lines
java.lang.IllegalArgumentException
- if epsilon
is less than zerojava.lang.NullPointerException
- if lines
or any of its elements is null
public static LineD[] split(LineD[] lines, MultiLinePoint[] crossings)
LineD
instances that are guaranteed not to intersect,
except at their LineD.start
or LineD.end
points. The specified
crossings
are usually the result of find(org.kynosarges.tektosyne.geometry.LineD[])
or findSimple(org.kynosarges.tektosyne.geometry.LineD[])
for the specified lines
.
split
sets the LineD.start
or LineD.end
point of any LineD
that participates in a LineLocation.START
or LineLocation.END
intersection
to the MultiLinePoint.shared
point of that intersection, so as to preserve
coordinate identities that were established by a positive comparison epsilon.
lines
- a LineD
array containing the line segements to splitcrossings
- a MultiLinePoint
array describing all points
of intersection between lines
LineD
array containing the line segments resulting from
splitting all lines
on the matching crossings
java.lang.ArrayIndexOutOfBoundsException
- if crossings
contains any
MultiLinePoint.Line.index
values that are invalid for lines
java.lang.IllegalArgumentException
- if crossings
contains any
MultiLinePoint.Line.location
other than LineLocation.START
,
LineLocation.BETWEEN
, or LineLocation.END
java.lang.NullPointerException
- if lines
or crossings
is null
or contains any null
elements