Package com.google.common.geometry
Class S2EdgeUtil.EdgeCrosser
- java.lang.Object
-
- com.google.common.geometry.S2EdgeUtil.EdgeCrosser
-
- Enclosing class:
- S2EdgeUtil
public static final class S2EdgeUtil.EdgeCrosser extends java.lang.Object
Used to efficiently test a fixed edge AB against an edge chain. To use it,initialize
with the edge AB, and callrobustCrossing(S2Point, S2Point)
oredgeOrVertexCrossing(S2Point, S2Point)
with each edge of the chain.This class is not thread-safe.
-
-
Field Summary
Fields Modifier and Type Field Description private S2Point
a
private int
acb
The orientation of the triangle ACB, i.e.private S2Point
aCrossB
private S2Point
aTangent
Outward-facing tangent at A.private S2Point
b
(package private) int
bdaReturn
The orientation of triangle BDA.private S2Point
bTangent
Outward-facing tangent at B.private S2Point
c
Previous vertex in the vertex chain.private boolean
hasTangents
True if the tangents have been computed.
-
Constructor Summary
Constructors Constructor Description EdgeCrosser()
Constructs an uninitialized edge crosser.EdgeCrosser(S2Point a, S2Point b)
Convenience constructor that calls init() with the given fixed edge AB.EdgeCrosser(S2Point a, S2Point b, S2Point c)
AB is the given fixed edge, and C is the first vertex of the vertex chain.
-
Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
edgeOrVertexCrossing(S2Point d)
This method is equivalent to theedgeOrVertexCrossing(com.google.common.geometry.S2Point)
method defined below.boolean
edgeOrVertexCrossing(S2Point c, S2Point d)
AsedgeOrVertexCrossing(S2Point)
, but restarts atc
if that is not the previous endpoint.void
init(S2Point a, S2Point b)
void
restartAt(S2Point c)
Call this method when your chain 'jumps' to a new place.int
robustCrossing(S2Point d)
This method is equivalent to calling therobustCrossing(com.google.common.geometry.S2Point)
function (defined below) on the edges AB and CD.int
robustCrossing(S2Point c, S2Point d)
AsrobustCrossing(S2Point)
, but restarts atc
if that is not the previous endpoint.private int
robustCrossingInternal(S2Point d)
Compute the actual result, and then save the current vertex D as the next vertex C, and save the orientation of the next triangle ACB (which is opposite to the current triangle BDA).private int
robustCrossingInternal2(S2Point d)
private static int
sign(S2Point a, S2Point b, S2Point c, S2Point aCrossB)
Helper that checks the sign of ABC, using a precomputed cross product for AxB.(package private) static int
triage(S2Point ab, S2Point c)
Returns the sign of the determinant of the column matrix ABC, given the precomputed cross product AB.
-
-
-
Field Detail
-
a
private S2Point a
-
b
private S2Point b
-
aCrossB
private S2Point aCrossB
-
c
private S2Point c
Previous vertex in the vertex chain.
-
acb
private int acb
The orientation of the triangle ACB, i.e. the orientation around the current vertex.
-
bdaReturn
int bdaReturn
The orientation of triangle BDA. This is used to return an extra value from robustCrossingInternal().
-
hasTangents
private boolean hasTangents
True if the tangents have been computed. To reduce the number of calls toS2Predicates.Sign.expensive(com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, com.google.common.geometry.S2Point, boolean)
, we compute an outward-facing tangent at A and B if necessary. If the plane perpendicular to one of these tangents separates AB from CD (i.e., one edge on each side) then there is no intersection.
-
aTangent
private S2Point aTangent
Outward-facing tangent at A.
-
bTangent
private S2Point bTangent
Outward-facing tangent at B.
-
-
Constructor Detail
-
EdgeCrosser
public EdgeCrosser()
Constructs an uninitialized edge crosser. Invokeinit(S2Point, S2Point)
before calling the other methods.
-
EdgeCrosser
public EdgeCrosser(S2Point a, S2Point b)
Convenience constructor that calls init() with the given fixed edge AB.
-
-
Method Detail
-
restartAt
public void restartAt(S2Point c)
Call this method when your chain 'jumps' to a new place.
-
triage
static int triage(S2Point ab, S2Point c)
Returns the sign of the determinant of the column matrix ABC, given the precomputed cross product AB.
-
robustCrossing
public int robustCrossing(S2Point d)
This method is equivalent to calling therobustCrossing(com.google.common.geometry.S2Point)
function (defined below) on the edges AB and CD. It returns +1 if there is a crossing, -1 if there is no crossing, and 0 if two points from different edges are the same. Returns 0 or -1 if either edge is degenerate. As a side effect, it saves vertex D to be used as the next vertex C.
-
robustCrossing
public int robustCrossing(S2Point c, S2Point d)
AsrobustCrossing(S2Point)
, but restarts atc
if that is not the previous endpoint.
-
edgeOrVertexCrossing
public boolean edgeOrVertexCrossing(S2Point d)
This method is equivalent to theedgeOrVertexCrossing(com.google.common.geometry.S2Point)
method defined below. It is similar torobustCrossing(com.google.common.geometry.S2Point)
, but handles cases where two vertices are identical in a way that makes it easy to implement point-in-polygon containment tests.
-
edgeOrVertexCrossing
public boolean edgeOrVertexCrossing(S2Point c, S2Point d)
AsedgeOrVertexCrossing(S2Point)
, but restarts atc
if that is not the previous endpoint.
-
robustCrossingInternal
private int robustCrossingInternal(S2Point d)
Compute the actual result, and then save the current vertex D as the next vertex C, and save the orientation of the next triangle ACB (which is opposite to the current triangle BDA).
-
robustCrossingInternal2
private int robustCrossingInternal2(S2Point d)
-
-