HullTri.java
/*
* Copyright (c) 2021 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.algorithm.hull;
import java.util.ArrayDeque;
import java.util.Deque;
import java.util.List;
import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.Triangle;
import org.locationtech.jts.triangulate.tri.Tri;
/**
* Tris which are used to form a concave hull.
* If a Tri has an edge (or edges) with no adjacent tri
* the tri is on the border of the triangulation.
* The edge is a boundary edge.
* The union of those edges
* forms the (linear) boundary of the triangulation.
* The triangulation area may be a Polygon or MultiPolygon, and may or may not contain holes.
*
* @author Martin Davis
*
*/
class HullTri extends Tri
implements Comparable<HullTri>
{
private double size;
private boolean isMarked = false;
public HullTri(Coordinate p0, Coordinate p1, Coordinate p2) {
super(p0, p1, p2);
this.size = lengthOfLongestEdge();
}
public double getSize() {
return size;
}
/**
* Sets the size to be the length of the boundary edges.
* This is used when constructing hull without holes,
* by erosion from the triangulation border.
*/
public void setSizeToBoundary() {
size = lengthOfBoundary();
}
public void setSizeToLongestEdge() {
size = lengthOfLongestEdge();
}
public void setSizeToCircumradius() {
size = Triangle.circumradius(p2, p1, p0);
}
public boolean isMarked() {
return isMarked;
}
public void setMarked(boolean isMarked) {
this.isMarked = isMarked;
}
public boolean isRemoved() {
return ! hasAdjacent();
}
/**
* Gets an index of a boundary edge, if there is one.
*
* @return a boundary edge index, or -1
*/
public int boundaryIndex() {
if (isBoundary(0)) return 0;
if (isBoundary(1)) return 1;
if (isBoundary(2)) return 2;
return -1;
}
/**
* Gets the most CCW boundary edge index.
* This assumes there is at least one non-boundary edge.
*
* @return the CCW boundary edge index
*/
public int boundaryIndexCCW() {
int index = boundaryIndex();
if (index < 0) return -1;
int prevIndex = prev(index);
if (isBoundary(prevIndex)) {
return prevIndex;
}
return index;
}
/**
* Gets the most CW boundary edge index.
* This assumes there is at least one non-boundary edge.
*
* @return the CW boundary edge index
*/
public int boundaryIndexCW() {
int index = boundaryIndex();
if (index < 0) return -1;
int nextIndex = next(index);
if (isBoundary(nextIndex)) {
return nextIndex;
}
return index;
}
/**
* Tests if a tri is the only one connecting its 2 adjacents.
* Assumes that the tri is on the border of the triangulation
* and that the triangulation does not contain holes
*
* @param tri the tri to test
* @return true if the tri is the only connection
*/
public boolean isConnecting() {
int adj2Index = adjacent2VertexIndex();
boolean isInterior = isInteriorVertex(adj2Index);
return ! isInterior;
}
/**
* Gets the index of a vertex which is adjacent to two other tris (if any).
*
* @return the vertex index, or -1
*/
public int adjacent2VertexIndex() {
if (hasAdjacent(0) && hasAdjacent(1)) return 1;
if (hasAdjacent(1) && hasAdjacent(2)) return 2;
if (hasAdjacent(2) && hasAdjacent(0)) return 0;
return -1;
}
/**
* Tests whether some vertex of this Tri has degree = 1.
* In this case it is not in any other Tris.
*
* @param tri
* @param triList
* @return true if a vertex has degree 1
*/
public int isolatedVertexIndex(List<HullTri> triList) {
for (int i = 0; i < 3; i++) {
if (degree(i, triList) <= 1)
return i;
}
return -1;
}
public double lengthOfLongestEdge() {
return Triangle.longestSideLength(p0, p1, p2);
}
double lengthOfBoundary() {
double len = 0.0;
for (int i = 0; i < 3; i++) {
if (! hasAdjacent(i)) {
len += getCoordinate(i).distance(getCoordinate(Tri.next(i)));
}
}
return len;
}
/**
* Sorts tris in decreasing order.
* Since PriorityQueues sort in <i>ascending</i> order,
* to sort with the largest at the head,
* smaller sizes must compare as greater than larger sizes.
* (i.e. the normal numeric comparison is reversed).
* If the sizes are identical (which should be an infrequent case),
* the areas are compared, with larger areas sorting before smaller.
* (The rationale is that larger areas indicate an area of lower point density,
* which is more likely to be in the exterior of the computed hull.)
* This improves the determinism of the queue ordering.
*/
@Override
public int compareTo(HullTri o) {
/**
* If size is identical compare areas to ensure a (more) deterministic ordering.
* Larger areas sort before smaller ones.
*/
if (size == o.size) {
return -Double.compare(this.getArea(), o.getArea());
}
return -Double.compare(size, o.size);
}
/**
* Tests if this tri has a vertex which is in the boundary,
* but not in a boundary edge.
*
* @return true if the tri touches the boundary at a vertex
*/
public boolean hasBoundaryTouch() {
for (int i = 0; i < 3; i++) {
if (isBoundaryTouch(i))
return true;
}
return false;
}
private boolean isBoundaryTouch(int index) {
//-- If vertex is in a boundary edge it is not a touch
if (isBoundary(index)) return false;
if (isBoundary(prev(index))) return false;
//-- if vertex is not in interior it is on boundary
return ! isInteriorVertex(index);
}
public static HullTri findTri(List<HullTri> triList, Tri exceptTri) {
for (HullTri tri : triList) {
if (tri != exceptTri) return tri;
}
return null;
}
public static boolean isAllMarked(List<HullTri> triList) {
for (HullTri tri : triList) {
if (! tri.isMarked())
return false;
}
return true;
}
public static void clearMarks(List<HullTri> triList) {
for (HullTri tri : triList) {
tri.setMarked(false);
}
}
public static void markConnected(HullTri triStart, Tri exceptTri) {
Deque<HullTri> queue = new ArrayDeque<HullTri>();
queue.add(triStart);
while (! queue.isEmpty()) {
HullTri tri = queue.pop();
tri.setMarked(true);
for (int i = 0; i < 3; i++) {
HullTri adj = (HullTri) tri.getAdjacent(i);
//-- don't connect thru this tri
if (adj == exceptTri)
continue;
if (adj != null && ! adj.isMarked() ) {
queue.add(adj);
}
}
}
}
/**
* Tests if a triangulation is edge-connected, if a triangle is removed.
* NOTE: this is a relatively slow operation.
*
* @param triList the triangulation
* @param removedTri the triangle to remove
* @return true if the triangulation is still connnected
*/
public static boolean isConnected(List<HullTri> triList, HullTri removedTri) {
if (triList.size() == 0) return false;
clearMarks(triList);
HullTri triStart = findTri(triList, removedTri);
if (triStart == null) return false;
markConnected(triStart, removedTri);
removedTri.setMarked(true);
return isAllMarked(triList);
}
}