Package com.google.common.geometry
Class S2EdgeUtil.EdgeCrosser
java.lang.Object
com.google.common.geometry.S2EdgeUtil.EdgeCrosser
- Enclosing class:
S2EdgeUtil
Used to efficiently test a fixed edge AB against an edge chain. To use it,
initialize
with the edge AB, and call robustCrossing(S2Point, S2Point)
or edgeOrVertexCrossing(S2Point, S2Point)
with each edge of the chain.
This class is not thread-safe.
-
Field Summary
FieldsModifier and TypeFieldDescriptionprivate S2Point
private int
The orientation of the triangle ACB, i.e.private S2Point
private S2Point
Outward-facing tangent at A.private S2Point
(package private) int
The orientation of triangle BDA.private S2Point
Outward-facing tangent at B.private S2Point
Previous vertex in the vertex chain.private boolean
True if the tangents have been computed. -
Constructor Summary
ConstructorsConstructorDescriptionConstructs 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
Modifier and TypeMethodDescriptionboolean
This method is equivalent to theedgeOrVertexCrossing(com.google.common.geometry.S2Point)
method defined below.boolean
AsedgeOrVertexCrossing(S2Point)
, but restarts atc
if that is not the previous endpoint.void
void
Call this method when your chain 'jumps' to a new place.int
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
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
private static int
Helper that checks the sign of ABC, using a precomputed cross product for AxB.(package private) static int
Returns the sign of the determinant of the column matrix ABC, given the precomputed cross product AB.
-
Field Details
-
a
-
b
-
aCrossB
-
c
Previous vertex in the vertex chain. -
acb
private int acbThe orientation of the triangle ACB, i.e. the orientation around the current vertex. -
bdaReturn
int bdaReturnThe orientation of triangle BDA. This is used to return an extra value from robustCrossingInternal(). -
hasTangents
private boolean hasTangentsTrue 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
Outward-facing tangent at A. -
bTangent
Outward-facing tangent at B.
-
-
Constructor Details
-
EdgeCrosser
public EdgeCrosser()Constructs an uninitialized edge crosser. Invokeinit(S2Point, S2Point)
before calling the other methods. -
EdgeCrosser
Convenience constructor that calls init() with the given fixed edge AB. -
EdgeCrosser
AB is the given fixed edge, and C is the first vertex of the vertex chain. Equivalent to using the two-arg constructor and calling restartAt(c).
-
-
Method Details
-
init
-
restartAt
Call this method when your chain 'jumps' to a new place. -
triage
Returns the sign of the determinant of the column matrix ABC, given the precomputed cross product AB. -
robustCrossing
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
AsrobustCrossing(S2Point)
, but restarts atc
if that is not the previous endpoint. -
edgeOrVertexCrossing
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
AsedgeOrVertexCrossing(S2Point)
, but restarts atc
if that is not the previous endpoint. -
robustCrossingInternal
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
-
sign
Helper that checks the sign of ABC, using a precomputed cross product for AxB.
-