OverlayLabel.java
/*
* Copyright (c) 2019 Martin Davis.
*
* All rights reserved. This program and the accompanying materials
* are made available under the terms of the Eclipse Public License 2.0
* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
* and the Eclipse Distribution License is available at
*
* http://www.eclipse.org/org/documents/edl-v10.php.
*/
package org.locationtech.jts.operation.overlayng;
import org.locationtech.jts.geom.Location;
import org.locationtech.jts.geom.Position;
/**
* A structure recording the topological situation
* for an edge in a topology graph
* used during overlay processing.
* A label contains the topological {@link Location}s for
* one or two input geometries to an overlay operation.
* An input geometry may be either a Line or an Area.
* The label locations for each input geometry are populated
* with the {@Location}s for the edge {@link Position}s
* when they are created or once they are computed by topological evaluation.
* A label also records the (effective) dimension of each input geometry.
* For area edges the role (shell or hole)
* of the originating ring is recorded, to allow
* determination of edge handling in collapse cases.
* <p>
* In an {@link OverlayGraph} a single label is shared between
* the two oppositely-oriented {@ link OverlayEdge}s of a symmetric pair.
* Accessors for orientation-sensitive information
* are parameterized by the orientation of the containing edge.
* <p>
* For each input geometry (0 and 1), the label records
* that an edge is in one of the following states
* (identified by the <code>dim</code> field).
* Each state has additional information about the edge topology.
* <ul>
* <li>A <b>Boundary</b> edge of an Area (polygon)
* <ul>
* <li><code>dim</code> = DIM_BOUNDARY</li>
* <li><code>locLeft, locRight</code> : the locations of the edge sides for the Area</li>
* <li><code>locLine</code> : INTERIOR</li>
* <li><code>isHole</code> : whether the
* edge is in a shell or a hole (the ring role)</li>
* </ul>
* </li>
* <li>A <b>Collapsed</b> edge of an input Area
* (formed by merging two or more parent edges)
* <ul>
* <li><code>dim</code> = DIM_COLLAPSE</li>
* <li><code>locLine</code> : the location of the edge relative to the effective input Area
* (a collapsed spike is EXTERIOR, a collapsed gore or hole is INTERIOR)</li>
* <li><code>isHole</code> : <code>true</code> if all parent edges are in holes;
* <code>false</code> if some parent edge is in a shell
* </ul>
* </li>
* <li>A <b>Line</b> edge from an input line
* <ul>
* <li><code>dim</code> = DIM_LINE</li>
* <li><code>locLine</code> : the location of the edge relative to the Line.
* Initialized to LOC_UNKNOWN to simplify logic.</li>
* </ul>
* </li>
* <li>An edge which is <b>Not Part</b> of an input geometry
* (and thus must be part of the other geometry).
* <ul>
* <li><code>dim</code> = NOT_PART</li>
* </ul>
* </li>
* </ul>
* Note that:
* <ul>
* <li>an edge cannot be both a Collapse edge and a Line edge in the same input geometry,
* because input geometries must be homogeneous in dimension.
* <li>an edge may be an Boundary edge in one input geometry
* and a Line or Collapse edge in the other input.
* </ul>
*
* @author Martin Davis
*
*/
class OverlayLabel {
private static final char SYM_UNKNOWN = '#';
private static final char SYM_BOUNDARY = 'B';
private static final char SYM_COLLAPSE = 'C';
private static final char SYM_LINE = 'L';
/**
* The dimension of an input geometry which is not known
*/
public static final int DIM_UNKNOWN = -1;
/**
* The dimension of an edge which is not part of a specified input geometry.
*/
public static final int DIM_NOT_PART = DIM_UNKNOWN;
/**
* The dimension of an edge which is a line.
*/
public static final int DIM_LINE = 1;
/**
* The dimension for an edge which is part of an input Area geometry boundary.
*/
public static final int DIM_BOUNDARY = 2;
/**
* The dimension for an edge which is a collapsed part of an input Area geometry boundary.
* A collapsed edge represents two or more line segments which have the same endpoints.
* They usually are caused by edges in valid polygonal geometries
* having their endpoints become identical due to precision reduction.
*/
public static final int DIM_COLLAPSE = 3;
/**
* Indicates that the location is currently unknown
*/
public static int LOC_UNKNOWN = Location.NONE;
private int aDim = DIM_NOT_PART;
private boolean aIsHole = false;
private int aLocLeft = LOC_UNKNOWN;
private int aLocRight = LOC_UNKNOWN;
private int aLocLine = LOC_UNKNOWN;
private int bDim = DIM_NOT_PART;
private boolean bIsHole = false;
private int bLocLeft = LOC_UNKNOWN;
private int bLocRight = LOC_UNKNOWN;
private int bLocLine = LOC_UNKNOWN;
/**
* Creates a label for an Area edge.
*
* @param index the input index of the parent geometry
* @param locLeft the location of the left side of the edge
* @param locRight the location of the right side of the edge
* @param isHole whether the edge role is a hole or a shell
*/
public OverlayLabel(int index, int locLeft, int locRight, boolean isHole)
{
initBoundary(index, locLeft, locRight, isHole);
}
/**
* Creates a label for a Line edge.
*
* @param index the input index of the parent geometry
*/
public OverlayLabel(int index)
{
initLine(index);
}
/**
* Creates an uninitialized label.
*
*/
public OverlayLabel()
{
}
/**
* Creates a label which is a copy of another label.
*
* @param lbl
*/
public OverlayLabel(OverlayLabel lbl) {
this.aLocLeft = lbl.aLocLeft;
this.aLocRight = lbl.aLocRight;
this.aLocLine = lbl.aLocLine;
this.aDim = lbl.aDim;
this.aIsHole = lbl.aIsHole;
this.bLocLeft = lbl.bLocLeft;
this.bLocRight = lbl.bLocRight;
this.bLocLine = lbl.bLocLine;
this.bDim = lbl.bDim;
this.bIsHole = lbl.bIsHole;
}
/**
* Gets the effective dimension of the given input geometry.
*
* @param index the input geometry index
* @return the dimension
*
* @see #DIM_UNKNOWN
* @see #DIM_NOT_PART
* @see #DIM_LINE
* @see #DIM_BOUNDARY
* @see #DIM_COLLAPSE
*/
public int dimension(int index) {
if (index == 0)
return aDim;
return bDim;
}
/**
* Initializes the label for an input geometry which is an Area boundary.
*
* @param index the input index of the parent geometry
* @param locLeft the location of the left side of the edge
* @param locRight the location of the right side of the edge
* @param isHole whether the edge role is a hole or a shell
*/
public void initBoundary(int index, int locLeft, int locRight, boolean isHole) {
if (index == 0) {
aDim = DIM_BOUNDARY;
aIsHole = isHole;
aLocLeft = locLeft;
aLocRight = locRight;
aLocLine = Location.INTERIOR;
}
else {
bDim = DIM_BOUNDARY;
bIsHole = isHole;
bLocLeft = locLeft;
bLocRight = locRight;
bLocLine = Location.INTERIOR;
}
}
/**
* Initializes the label for an edge which is the collapse of
* part of the boundary of an Area input geometry.
* The location of the collapsed edge relative to the
* parent area geometry is initially unknown.
* It must be determined from the topology of the overlay graph
*
* @param index the index of the parent input geometry
* @param isHole whether the dominant edge role is a hole or a shell
*/
public void initCollapse(int index, boolean isHole) {
if (index == 0) {
aDim = DIM_COLLAPSE;
aIsHole = isHole;
}
else {
bDim = DIM_COLLAPSE;
bIsHole = isHole;
}
}
/**
* Initializes the label for an input geometry which is a Line.
*
* @param index the index of the parent input geometry
*/
public void initLine(int index) {
if (index == 0) {
aDim = DIM_LINE;
aLocLine = LOC_UNKNOWN;
}
else {
bDim = DIM_LINE;
bLocLine = LOC_UNKNOWN;
}
}
/**
* Initializes the label for an edge which is not part of an input geometry.
* @param index the index of the input geometry
*/
public void initNotPart(int index) {
// this assumes locations are initialized to UNKNOWN
if (index == 0) {
aDim = DIM_NOT_PART;
}
else {
bDim = DIM_NOT_PART;
}
}
/**
* Sets the line location.
*
* This is used to set the locations for linear edges
* encountered during area label propagation.
*
* @param index source to update
* @param loc location to set
*/
public void setLocationLine(int index, int loc) {
if (index == 0) {
aLocLine = loc;
}
else {
bLocLine = loc;
}
}
/**
* Sets the location of all postions for a given input.
*
* @param index the index of the input geometry
* @param loc the location to set
*/
public void setLocationAll(int index, int loc) {
if (index == 0) {
aLocLine = loc;
aLocLeft = loc;
aLocRight = loc;
}
else {
bLocLine = loc;
bLocLeft = loc;
bLocRight = loc;
}
}
/**
* Sets the location for a collapsed edge (the Line position)
* for an input geometry,
* depending on the ring role recorded in the label.
* If the input geometry edge is from a shell,
* the location is {@link Location#EXTERIOR}, if it is a hole
* it is {@link Location#INTERIOR}.
*
* @param index the index of the input geometry
*/
public void setLocationCollapse(int index) {
int loc = isHole(index) ? Location.INTERIOR : Location.EXTERIOR;
if (index == 0) {
aLocLine = loc;
}
else {
bLocLine = loc;
}
}
/**
* Tests whether at least one of the sources is a Line.
*
* @return true if at least one source is a line
*/
public boolean isLine() {
return aDim == DIM_LINE || bDim == DIM_LINE;
}
/**
* Tests whether a source is a Line.
*
* @param index the index of the input geometry
* @return true if the input is a Line
*/
public boolean isLine(int index) {
if (index == 0) {
return aDim == DIM_LINE;
}
return bDim == DIM_LINE;
}
/**
* Tests whether an edge is linear (a Line or a Collapse) in an input geometry.
*
* @param index the index of the input geometry
* @return true if the edge is linear
*/
public boolean isLinear(int index) {
if (index == 0) {
return aDim == DIM_LINE || aDim == DIM_COLLAPSE;
}
return bDim == DIM_LINE || bDim == DIM_COLLAPSE;
}
/**
* Tests whether a the source of a label is known.
*
* @param index the index of the source geometry
* @return true if the source is known
*/
public boolean isKnown(int index) {
if (index == 0) {
return aDim != DIM_UNKNOWN;
}
return bDim != DIM_UNKNOWN;
}
/**
* Tests whether a label is for an edge which is not part
* of a given input geometry.
*
* @param index the index of the source geometry
* @return true if the edge is not part of the geometry
*/
public boolean isNotPart(int index) {
if (index == 0) {
return aDim == DIM_NOT_PART;
}
return bDim == DIM_NOT_PART;
}
/**
* Tests if a label is for an edge which is in the boundary of either source geometry.
*
* @return true if the label is a boundary for either source
*/
public boolean isBoundaryEither() {
return aDim == DIM_BOUNDARY || bDim == DIM_BOUNDARY;
}
/**
* Tests if a label is for an edge which is in the boundary of both source geometries.
*
* @return true if the label is a boundary for both sources
*/
public boolean isBoundaryBoth() {
return aDim == DIM_BOUNDARY && bDim == DIM_BOUNDARY;
}
/**
* Tests if the label is a collapsed edge of one area
* and is a (non-collapsed) boundary edge of the other area.
*
* @return true if the label is for a collapse coincident with a boundary
*/
public boolean isBoundaryCollapse() {
if (isLine()) return false;
return ! isBoundaryBoth();
}
/**
* Tests if a label is for an edge where two
* area touch along their boundary.
*
* @return true if the edge is a boundary touch
*/
public boolean isBoundaryTouch() {
return isBoundaryBoth()
&& getLocation(0, Position.RIGHT, true) != getLocation(1, Position.RIGHT, true);
}
/**
* Tests if a label is for an edge which is in the boundary of a source geometry.
* Collapses are not reported as being in the boundary.
*
* @param index the index of the input geometry
* @return true if the label is a boundary for the source
*/
public boolean isBoundary(int index) {
if (index == 0) {
return aDim == DIM_BOUNDARY;
}
return bDim == DIM_BOUNDARY;
}
/**
* Tests whether a label is for an edge which is a boundary of one geometry
* and not part of the other.
*
* @return true if the edge is a boundary singleton
*/
public boolean isBoundarySingleton() {
if (aDim == DIM_BOUNDARY && bDim == DIM_NOT_PART) return true;
if (bDim == DIM_BOUNDARY && aDim == DIM_NOT_PART) return true;
return false;
}
/**
* Tests if the line location for a source is unknown.
*
* @param index the index of the input geometry
* @return true if the line location is unknown
*/
public boolean isLineLocationUnknown(int index) {
if (index == 0) {
return aLocLine == LOC_UNKNOWN;
}
else {
return bLocLine == LOC_UNKNOWN;
}
}
/**
* Tests if a line edge is inside a source geometry
* (i.e. it has location {@link Location#INTERIOR}).
*
* @param index the index of the input geometry
* @return true if the line is inside the source geometry
*/
public boolean isLineInArea(int index) {
if (index == 0) {
return aLocLine == Location.INTERIOR;
}
return bLocLine == Location.INTERIOR;
}
/**
* Tests if the ring role of an edge is a hole.
*
* @param index the index of the input geometry
* @return true if the ring role is a hole
*/
public boolean isHole(int index) {
if (index == 0) {
return aIsHole;
}
else {
return bIsHole;
}
}
/**
* Tests if an edge is a Collapse for a source geometry.
*
* @param index the index of the input geometry
* @return true if the label indicates the edge is a collapse for the source
*/
public boolean isCollapse(int index) {
return dimension(index) == DIM_COLLAPSE;
}
/**
* Tests if a label is a Collapse has location {@link Location#INTERIOR},
* to at least one source geometry.
*
* @return true if the label is an Interior Collapse to a source geometry
*/
public boolean isInteriorCollapse() {
if (aDim == DIM_COLLAPSE && aLocLine == Location.INTERIOR) return true;
if (bDim == DIM_COLLAPSE && bLocLine == Location.INTERIOR) return true;
return false;
}
/**
* Tests if a label is a Collapse
* and NotPart with location {@link Location#INTERIOR} for the other geometry.
*
* @return true if the label is a Collapse and a NotPart with Location Interior
*/
public boolean isCollapseAndNotPartInterior() {
if (aDim == DIM_COLLAPSE && bDim == DIM_NOT_PART && bLocLine == Location.INTERIOR) return true;
if (bDim == DIM_COLLAPSE && aDim == DIM_NOT_PART && aLocLine == Location.INTERIOR) return true;
return false;
}
/**
* Gets the line location for a source geometry.
*
* @param index the index of the input geometry
* @return the line location for the source
*/
public int getLineLocation(int index) {
if (index == 0) {
return aLocLine;
}
else {
return bLocLine;
}
}
/**
* Tests if a line is in the interior of a source geometry.
*
* @param index the index of the source geometry
* @return true if the label is a line and is interior
*/
public boolean isLineInterior(int index) {
if (index == 0) {
return aLocLine == Location.INTERIOR;
}
return bLocLine == Location.INTERIOR;
}
/**
* Gets the location for a {@link Position} of an edge of a source
* for an edge with given orientation.
*
* @param index the index of the source geometry
* @param position the position to get the location for
* @param isForward true if the orientation of the containing edge is forward
* @return the location of the oriented position in the source
*/
public int getLocation(int index, int position, boolean isForward) {
if (index == 0) {
switch (position) {
case Position.LEFT: return isForward ? aLocLeft : aLocRight;
case Position.RIGHT: return isForward ? aLocRight : aLocLeft;
case Position.ON: return aLocLine;
}
}
// index == 1
switch (position) {
case Position.LEFT: return isForward ? bLocLeft : bLocRight;
case Position.RIGHT: return isForward ? bLocRight : bLocLeft;
case Position.ON: return bLocLine;
}
return LOC_UNKNOWN;
}
/**
* Gets the location for this label for either
* a Boundary or a Line edge.
* This supports a simple determination of
* whether the edge should be included as a result edge.
*
* @param index the source index
* @param position the position for a boundary label
* @param isForward the direction for a boundary label
* @return the location for the specified position
*/
public int getLocationBoundaryOrLine(int index, int position, boolean isForward) {
if (isBoundary(index)) {
return getLocation(index, position, isForward);
}
return getLineLocation(index);
}
/**
* Gets the linear location for the given source.
*
* @param index the source geometry index
* @return the linear location for the source
*/
public int getLocation(int index) {
if (index == 0) {
return aLocLine;
}
return bLocLine;
}
/**
* Tests whether this label has side position information
* for a source geometry.
*
* @param index the source geometry index
* @return true if at least one side position is known
*/
public boolean hasSides(int index) {
if (index == 0) {
return aLocLeft != LOC_UNKNOWN
|| aLocRight != LOC_UNKNOWN;
}
return bLocLeft != LOC_UNKNOWN
|| bLocRight != LOC_UNKNOWN;
}
/**
* Creates a copy of this label.
*
* @return a copy of the label
*/
public OverlayLabel copy() {
return new OverlayLabel(this);
}
public String toString()
{
return toString(true);
}
public String toString(boolean isForward)
{
StringBuilder buf = new StringBuilder();
buf.append("A:");
buf.append(locationString(0, isForward));
buf.append("/B:");
buf.append(locationString(1, isForward));
return buf.toString();
}
private String locationString(int index, boolean isForward) {
StringBuilder buf = new StringBuilder();
if (isBoundary(index)) {
buf.append( Location.toLocationSymbol( getLocation(index, Position.LEFT, isForward) ) );
buf.append( Location.toLocationSymbol( getLocation(index, Position.RIGHT, isForward) ) );
}
else {
// is a linear edge
buf.append( Location.toLocationSymbol( index == 0 ? aLocLine : bLocLine ));
}
if (isKnown(index))
buf.append( dimensionSymbol(index == 0 ? aDim : bDim) );
if (isCollapse(index)) {
buf.append( ringRoleSymbol( index == 0 ? aIsHole : bIsHole ));
}
return buf.toString();
}
/**
* Gets a symbol for the a ring role (Shell or Hole).
*
* @param isHole true for a hole, false for a shell
* @return the ring role symbol character
*/
public static char ringRoleSymbol(boolean isHole) {
return isHole ? 'h' : 's';
}
/**
* Gets the symbol for the dimension code of an edge.
*
* @param dim the dimension code
* @return the dimension symbol character
*/
public static char dimensionSymbol(int dim) {
switch (dim) {
case DIM_LINE: return SYM_LINE;
case DIM_COLLAPSE: return SYM_COLLAPSE;
case DIM_BOUNDARY: return SYM_BOUNDARY;
}
return SYM_UNKNOWN;
}
}