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 call robustCrossing(S2Point, S2Point) or edgeOrVertexCrossing(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

Modifier and Type	Method	Description
boolean	edgeOrVertexCrossing(S2Point d)	This method is equivalent to the edgeOrVertexCrossing(com.google.common.geometry.S2Point) method defined below.
boolean	edgeOrVertexCrossing(S2Point c, S2Point d)	As edgeOrVertexCrossing(S2Point), but restarts at c 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 the robustCrossing(com.google.common.geometry.S2Point) function (defined below) on the edges AB and CD.
int	robustCrossing(S2Point c, S2Point d)	As robustCrossing(S2Point), but restarts at c 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.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 to S2Predicates.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. Invoke init(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.

EdgeCrosser

public EdgeCrosser(S2Point a,
                   S2Point b,
                   S2Point c)

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 Detail

init

public void init(S2Point a,
                 S2Point b)

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 the robustCrossing(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)

As robustCrossing(S2Point), but restarts at c if that is not the previous endpoint.

edgeOrVertexCrossing

public boolean edgeOrVertexCrossing(S2Point d)

This method is equivalent to the edgeOrVertexCrossing(com.google.common.geometry.S2Point) method defined below. It is similar to robustCrossing(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)

As edgeOrVertexCrossing(S2Point), but restarts at c 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)

sign

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.