Determine if an edge lies on the border/boundary/perimeter of a TIN

[micycle1]

In an unconstrained TIN, how do I determine if an edge lies on the border/boundary/perimeter of the triangulation?

[gwlucastrig]

Well, I am really surprised that there isn't a method that does that. In the short term, I will write up some code to show you how to do it. For the long term, I'll add a new isPerimeter() method to the IQuadEdge interface.

Thanks for bringing this to my attention.

Gary

P.S. In case it helps, the IIncrementTin classes do have a method called getPerimeter() that gets an ordered list of the perimeter edges.

[gwlucastrig]

Here's an example application that creates a TIN and tests its edges to see if they are on the perimeter. I'm not quite sure what you need for your purposes, but I think that this application illustrates enough different ways of doing things that you can fine an approach that suits your needs.

The main method of interest is isEdgeOnPerimeter(). Note that each edge in Tinfour has two sides. For a perimeter edge,
one side will be facing inward, and one side will be facing outward. So we need to test both the edge itself and its dual to see if either of them is an outward facing edge.

import java.util.List;
import org.tinfour.common.IQuadEdge;
import org.tinfour.common.Vertex;
import org.tinfour.demo.utils.TestVertices;
import org.tinfour.standard.IncrementalTin;

public class TestPerimeter {

    public static void main(String[] args)  {
        IncrementalTin tin = new IncrementalTin(1.0);
        List<Vertex> vertexList = TestVertices.makeRandomVertices(20, 0);
        tin.add(vertexList, null);

        // as a diagnostic test, we want to see if the edges we get back
        // from the getPerimeter method are the same set we detect using the
        // example method below:
        int n = tin.getMaximumEdgeAllocationIndex();
        boolean[] edgeFlags = new boolean[n];
        List<IQuadEdge> perimeter = tin.getPerimeter();
        for (IQuadEdge edge : perimeter) {
            edgeFlags[edge.getIndex()] = true;
            edgeFlags[edge.getDual().getIndex()] = true;
        }

        for (IQuadEdge edge : tin.edges()) {
            // recall that edge edge has two sides, the edge and its dual.
            // If the edge lies on the perimeter of the triangulation,
            // the the outward facing segment could be either side of
            // the edge.  So we test both sides.
            if (edge.getForward().getB() == null) {
                System.out.println("Edge is Perimeter: " + edge.toString());
            } else if (edge.getForwardFromDual().getB() == null) {
                System.out.println("Dual is Perimeter: " + edge.toString());
            }
            // Test that the perimeter-test is consistent with the results
            // from getPerimeter() and vice versa.
            if (isEdgeOnPerimeter(edge)) {
                if (!edgeFlags[edge.getIndex()]) {
                    System.out.println("Failure for edge " + edge.getIndex());
                }
            } else {
                if (edgeFlags[edge.getIndex()]) {
                    System.out.println("Failure for edge " + edge.getIndex());
                }
            }
        }
    }

    /**
     * Tests to see if an edge or its dual is on the perimeter.
     *
     * @param edge a valid instance
     * @return true if the edge is on the perimeter; otherwise, false.
     */
    static boolean isEdgeOnPerimeter(IQuadEdge edge) {
        // The logic here is that each edge defines one side of a
        // triangle with vertices A, B, and C.  Vertices A and B
        // are the first and second vertices of the edge, vertex C
        // is the opposite one.  Triangles lying outside the Delaunay
        // Triangulation have a "ghost" vertex for vertex C.
        // Tinfour represents a ghost vertex with a null reference.
        // So we test both the edge and its dual to see if their
        // vertex C reference is null.
        //    Also note that vertex C is the second vertex of the forward edge from
        // our edge of interest.  Thus the C = edge.getForward().getB()

        return edge.getForward().getB() == null
          || edge.getForwardFromDual().getB() == null;
    }
}