This is a specialized method that is used to compute the intersection of an
edge X with the Voronoi diagram of a set of points, where each Voronoi
region is intersected with a disc of fixed radius "r".
Given two sites A and B and an edge (X0, X1) such that d(A,X0) < d(B,X0)
and both sites are within the given distance "r" of edge X, this method
intersects the Voronoi region of each site with a disc of radius r and
determines whether either region has an empty intersection with edge X. It
returns FIRST if site A has an empty intersection, SECOND if site B has an
empty intersection, NEITHER if neither site has an empty intersection, or
UNCERTAIN if A == B exactly. Note that it is not possible for both
intersections to be empty because of the requirement that both sites are
within distance r of edge X. (For example, the only reason that Voronoi
region A can have an empty intersection with X is that site B is closer to
all points on X that are within radius r of site A.)
The result is determined with respect to the positions of all points as
though they were projected to lie exactly on the surface of the unit
sphere. Furthermore this method uses symbolic perturbations to compute a
consistent non-zero result even when A and B lie on opposite sides of X
such that the Voronoi edge between them exactly coincides with edge X, or
when A and B are distinct but project to the same point on the sphere
(i.e., they are linearly dependent).
REQUIRES: r < S1ChordAngle::Right() (90 degrees)
REQUIRES: s2pred::CompareDistances(x0, a, b) < 0
REQUIRES: s2pred::CompareEdgeDistance(a, x0, x1, r) <= 0
REQUIRES: s2pred::CompareEdgeDistance(b, x0, x1, r) <= 0
REQUIRES: X0 and X1 do not project to antipodal points (e.g., X0 == -X1)
(see comments in CompareEdgeDistance).
This is a specialized method that is used to compute the intersection of an edge X with the Voronoi diagram of a set of points, where each Voronoi region is intersected with a disc of fixed radius "r".
Given two sites A and B and an edge (X0, X1) such that d(A,X0) < d(B,X0) and both sites are within the given distance "r" of edge X, this method intersects the Voronoi region of each site with a disc of radius r and determines whether either region has an empty intersection with edge X. It returns FIRST if site A has an empty intersection, SECOND if site B has an empty intersection, NEITHER if neither site has an empty intersection, or UNCERTAIN if A == B exactly. Note that it is not possible for both intersections to be empty because of the requirement that both sites are within distance r of edge X. (For example, the only reason that Voronoi region A can have an empty intersection with X is that site B is closer to all points on X that are within radius r of site A.)
The result is determined with respect to the positions of all points as though they were projected to lie exactly on the surface of the unit sphere. Furthermore this method uses symbolic perturbations to compute a consistent non-zero result even when A and B lie on opposite sides of X such that the Voronoi edge between them exactly coincides with edge X, or when A and B are distinct but project to the same point on the sphere (i.e., they are linearly dependent).
REQUIRES: r < S1ChordAngle::Right() (90 degrees) REQUIRES: s2pred::CompareDistances(x0, a, b) < 0 REQUIRES: s2pred::CompareEdgeDistance(a, x0, x1, r) <= 0 REQUIRES: s2pred::CompareEdgeDistance(b, x0, x1, r) <= 0 REQUIRES: X0 and X1 do not project to antipodal points (e.g., X0 == -X1) (see comments in CompareEdgeDistance).