public final class LineIntersection
extends java.lang.Object
Modifier and Type | Field and Description |
---|---|
LineLocation |
first
The location of the
shared point relative to the first line segment. |
LineRelation |
relation
The spatial relationship between the two line segments.
|
LineLocation |
second
The location of the
shared point relative to the second line segment. |
PointD |
shared
The
PointD coordinates shared by the two line segments or their infinite extensions. |
Modifier and Type | Method and Description |
---|---|
boolean |
equals(java.lang.Object obj)
Compares the specified
Object to this LineIntersection instance. |
boolean |
exists()
Determines whether both line segments contain the
shared coordinates. |
boolean |
existsBetween()
Determines whether both line segments contain the
shared coordinates,
excluding the end points of at least one line segment. |
static LineIntersection |
find(PointD startA,
PointD endA,
PointD startB,
PointD endB)
Finds the intersection of the specified line segments, using exact coordinate comparisons.
|
static LineIntersection |
find(PointD startA,
PointD endA,
PointD startB,
PointD endB,
double epsilon)
Finds the intersection of the specified line segments,
given the specified epsilon for coordinate comparisons.
|
int |
hashCode()
Returns a hash code for the
LineI . |
static LineLocation |
locateCollinear(PointD start,
PointD end,
PointD q)
Determines the location of the specified
PointD coordinates relative to the
specified line segment, assuming they are collinear and using exact coordinate comparisons. |
static LineLocation |
locateCollinear(PointD start,
PointD end,
PointD q,
double epsilon)
Determines the location of the specified
PointD coordinates relative to the
specified line segment, assuming they are collinear and given the specified epsilon
for coordinate comparisons. |
PointD |
startOrEnd(LineD a,
LineD b)
Returns the
LineD.start or LineD.end point of either specified
LineD for a matching first or second location. |
java.lang.String |
toString()
Returns a
String representation of the LineIntersection . |
public final LineLocation first
shared
point relative to the first line segment.
Holds null
if no intersection was found.public final LineLocation second
shared
point relative to the second line segment.
Holds null
if no intersection was found.public final LineRelation relation
null
.public final PointD shared
PointD
coordinates shared by the two line segments or their infinite extensions.
Holds null
if no intersection was found.
Valid shared
coordinates are generally computed, but may be copied from the
start or end point of an intersecting line if first
or second
equals
LineLocation.START
or LineLocation.END
.
If relation
equals LineRelation.COLLINEAR
, shared
holds the
following special values. If the two line segments overlap, shared
is not computed
but set directly to the start or end point of the second line segment, whichever is contained
by the first line segment and is lexicographically smaller, according to PointDComparatorY
.
Otherwise, shared
is set to null
, even though the infinite extensions
of the two line segments share all their points.
public boolean exists()
shared
coordinates.
Requires that both first
and second
equal one of the indicated
LineLocation
values, but not necessarily the same value.
exists
indicates whether the two line segments themselves intersect.
shared
may be a valid point even if exists
returns false
,
indicating an intersection of the infinite extensions of either or both line segments.
true
if both first
and second
equal either
LineLocation.START
, LineLocation.BETWEEN
, or LineLocation.END
,
else false
public boolean existsBetween()
shared
coordinates,
excluding the end points of at least one line segment.
Indicates whether the two line segments themselves intersect. Unlike exists()
, at least
one line segment must be properly intersected, i.e. not just touched at one end point.true
if either first
or second
equals LineLocation.BETWEEN
,
and the other location equals either LineLocation.START
, LineLocation.BETWEEN
,
or LineLocation.END
, else false
public static LineIntersection find(PointD startA, PointD endA, PointD startB, PointD endB)
Segments-Intersect
algorithm by Thomas H. Cormen et al.,
Introduction to Algorithms (3rd ed.), The MIT Press 2009, p.1018, for intersection
testing; and from the SegSegInt
and ParallelInt
algorithms by Joseph O’Rourke,
Computational Geometry in C (2nd ed.), Cambridge University Press 1998, p.224f,
for line relationships and shared coordinates.
Cormen’s intersection testing first examines the PointD.crossProductLength(org.kynosarges.tektosyne.geometry.PointD)
for each
triplet of specified points. If that is insufficient, O’Rourke’s algorithm then examines the
parameters of both line equations. This is mathematically redundant since O’Rourke’s algorithm
alone should produce all desired information, but the combination of both algorithms proved
much more resilient against misjudging line relationships due to floating-point inaccuracies.
Although most comparisons in this overload are exact, cross-product testing is always
performed with a minimum epsilon of 1e-10. Moreover, find
will return the result
of the epsilon overload with an epsilon of 2e-10 if cross-product testing contradicts line
equation testing. Subsequent contradictions result in further recursive calls, each time with
a doubled epsilon, until an intersection can be determined without contradictions.
startA
- the LineD.start
point of the first line segmentendA
- the LineD.end
point of the first line segmentstartB
- the LineD.start
point of the second line segmentendB
- the LineD.end
point of the second line segmentLineIntersection
instance that describes if and how the line segments
from startA
to endA
and from startB
to endB
intersectjava.lang.NullPointerException
- if any PointD
argument is null
public static LineIntersection find(PointD startA, PointD endA, PointD startB, PointD endB, double epsilon)
find(PointD, PointD, PointD, PointD)
overload but starts
with the specified epsilon
to compare coordinates and intermediate results.
epsilon
is always raised to a minimum of 1e-10 because the algorithm is otherwise
too unstable, and would initiate multiple recursions with a greater epsilon anyway.startA
- the LineD.start
point of the first line segmentendA
- the LineD.end
point of the first line segmentstartB
- the LineD.start
point of the second line segmentendB
- the LineD.end
point of the second line segmentepsilon
- the maximum absolute difference at which coordinates and intermediate results
should be considered equal. Always raised to a minium of 1e-10.LineIntersection
instance that describes if and how the line segments
from startA
to endA
and from startB
to endB
intersectjava.lang.NullPointerException
- if any PointD
argument is null
public static LineLocation locateCollinear(PointD start, PointD end, PointD q)
PointD
coordinates relative to the
specified line segment, assuming they are collinear and using exact coordinate comparisons.
Never returns null
, LineLocation.LEFT
, or LineLocation.RIGHT
due to the assumption of collinearity.start
- the LineD.start
point of the line segmentend
- the LineD.end
point of the line segmentq
- the PointD
coordinates to examineLineLocation
value indicating the location of q
relative to the line segment from start
to end
java.lang.NullPointerException
- if any PointD
argument is null
public static LineLocation locateCollinear(PointD start, PointD end, PointD q, double epsilon)
PointD
coordinates relative to the
specified line segment, assuming they are collinear and given the specified epsilon
for coordinate comparisons.
Never returns null
, LineLocation.LEFT
, or LineLocation.RIGHT
due to the assumption of collinearity.start
- the LineD.start
point of the line segmentend
- the LineD.end
point of the line segmentq
- the PointD
coordinates to examineepsilon
- the maximum absolute difference at which coordinates
and intermediate results should be considered equalLineLocation
value indicating the location of q
relative to the line segment from start
to end
java.lang.IllegalArgumentException
- if epsilon
is less than zerojava.lang.NullPointerException
- if any PointD
argument is null
public PointD startOrEnd(LineD a, LineD b)
LineD.start
or LineD.end
point of either specified
LineD
for a matching first
or second
location.
Call to obtain exact coordinates when first
or second
indicates
an exact match to avoid approximately computed shared
coordinates.a
- the LineD
to which first
appliesb
- the LineD
to which second
appliesLineD.start
or LineD.end
point of a
or b
if first
or second
equals LineLocation.START
or
LineLocation.END
, respectively, else shared
public boolean equals(java.lang.Object obj)
Object
to this LineIntersection
instance.equals
in class java.lang.Object
obj
- the Object
to compare to this instancetrue
if obj
is not null
and a LineIntersection
instance whose first
, second
, relation
, and
shared
fields equal those of this instance, else false
public int hashCode()
hashCode
in class java.lang.Object
Integer
hash code for the LineI
public java.lang.String toString()
String
representation of the LineIntersection
.