import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
private static boolean isEdgeSideOfTriangle( DelaunayTriangle triangle,
                                             TriangulationPoint ep,
                                             TriangulationPoint eq )
{
    int index;
    index = triangle.edgeIndex( ep, eq );
    if( index != -1 )
    {
        triangle.markConstrainedEdge( index );
        triangle = triangle.neighbors[ index ];
        if( triangle != null )
        {
            triangle.markConstrainedEdge( ep, eq );
        }
        return true;
    }        
    return false;
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * When we need to traverse from one triangle to the next we need 
 * the point in current triangle that is the opposite point to the next
 * triangle. 
 * 
 * @param ep
 * @param eq
 * @param ot
 * @param op
 * @return
 */
private static TriangulationPoint nextFlipPoint( TriangulationPoint ep,
                                                 TriangulationPoint eq,
                                                 DelaunayTriangle ot, 
                                                 TriangulationPoint op )
{
    Orientation o2d = orient2d( eq, op, ep );
    if( o2d == Orientation.CW )
    {
        // Right
        return ot.pointCCW( op );
    }
    else if( o2d == Orientation.CCW )
    {
        // Left                
        return ot.pointCW( op );
    }
    else
    {
        // TODO: implement support for point on constraint edge
        throw new PointOnEdgeException("Point on constrained edge not supported yet");
    }                    
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * After a flip we have two triangles and know that only one will still be
 * intersecting the edge. So decide which to contiune with and legalize the other
 * 
 * @param tcx
 * @param o - should be the result of an orient2d( eq, op, ep )
 * @param t - triangle 1
 * @param ot - triangle 2
 * @param p - a point shared by both triangles 
 * @param op - another point shared by both triangles
 * @return returns the triangle still intersecting the edge
 */
private static DelaunayTriangle nextFlipTriangle( DTSweepContext tcx, 
                                           Orientation o,
                                           DelaunayTriangle  t, 
                                           DelaunayTriangle ot, 
                                           TriangulationPoint p, 
                                           TriangulationPoint op)
{
    int edgeIndex;
    if( o == Orientation.CCW )
    {
        // ot is not crossing edge after flip
        edgeIndex = ot.edgeIndex( p, op );
        ot.dEdge[edgeIndex] = true;
        legalize( tcx, ot );
        ot.clearDelunayEdges();
        return t;
    }
    // t is not crossing edge after flip
    edgeIndex = t.edgeIndex( p, op );
    t.dEdge[edgeIndex] = true;
    legalize( tcx, t );
    t.clearDelunayEdges();            
    return ot;
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * Adds a triangle to the advancing front to fill a hole.
 * @param tcx
 * @param node - middle node, that is the bottom of the hole
 */
private static void fill( DTSweepContext tcx, AdvancingFrontNode node )
{
    DelaunayTriangle triangle = new DelaunayTriangle( node.prev.point, 
                                                      node.point, 
                                                      node.next.point );
    // TODO: should copy the cEdge value from neighbor triangles
    //       for now cEdge values are copied during the legalize 
    triangle.markNeighbor( node.prev.triangle );
    triangle.markNeighbor( node.triangle );
    tcx.addToList( triangle );

    // Update the advancing front
    node.prev.next = node.next;
    node.next.prev = node.prev;
    tcx.removeNode( node );
    
    // If it was legalized the triangle has already been mapped
    if( !legalize( tcx, triangle ) )
    {
        tcx.mapTriangleToNodes( triangle );
    }
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
public void createAdvancingFront()
{
    AdvancingFrontNode head,tail,middle;
    // Initial triangle
    DelaunayTriangle iTriangle = new DelaunayTriangle( _points.get(0), 
                                                       getTail(), 
                                                       getHead() );
    addToList( iTriangle );
    
    head = new AdvancingFrontNode( iTriangle.points[1] );
    head.triangle = iTriangle;
    middle = new AdvancingFrontNode( iTriangle.points[0] );
    middle.triangle = iTriangle;
    tail = new AdvancingFrontNode( iTriangle.points[2] );

    aFront = new AdvancingFront( head, tail ); 
    aFront.addNode( middle );
    
    // TODO: I think it would be more intuitive if head is middles next and not previous
    //       so swap head and tail
    aFront.head.next = middle;
    middle.next = aFront.tail;
    middle.prev = aFront.head;
    aFront.tail.prev = middle;
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * Try to map a node to all sides of this triangle that don't have 
 * a neighbor.
 * 
 * @param t
 */
public void mapTriangleToNodes( DelaunayTriangle t )
{
    AdvancingFrontNode n;
    for( int i=0; i<3; i++ )
    {
        if( t.neighbors[i] == null )
        {
            n = aFront.locatePoint( t.pointCW( t.points[i] ) );
            if( n != null )
            {
                n.triangle = t;
            }
        }            
    }        
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
@Test
public void test3dPoints() {
    List<TriangulationPoint> p = get3DPointsList();
    PointSet pt = get3DPoints(p);
    Set<DelaunayTriangle> expectedTriangles = new HashSet<DelaunayTriangle>();
    expectedTriangles.addAll(Arrays.asList(
            new DelaunayTriangle(p.get(9),p.get(5),p.get(2)),
            new DelaunayTriangle(p.get(2),p.get(5),p.get(6)),
            new DelaunayTriangle(p.get(2),p.get(6),p.get(4)),
            new DelaunayTriangle(p.get(8),p.get(2),p.get(4)),
            new DelaunayTriangle(p.get(8),p.get(4),p.get(3)),
            new DelaunayTriangle(p.get(6),p.get(3),p.get(4)),
            new DelaunayTriangle(p.get(1),p.get(3),p.get(6)),
            new DelaunayTriangle(p.get(1),p.get(7),p.get(3)),
            new DelaunayTriangle(p.get(1),p.get(0),p.get(10)),
            new DelaunayTriangle(p.get(9),p.get(10),p.get(0)),
            new DelaunayTriangle(p.get(5),p.get(9),p.get(0)),
            new DelaunayTriangle(p.get(5),p.get(0),p.get(6)),
            new DelaunayTriangle(p.get(6),p.get(0),p.get(1))
            ));
    Poly2Tri.triangulate(pt);
    assertEquals(expectedTriangles.size(), pt.getTriangles().size());
    for(DelaunayTriangle tri : pt.getTriangles()) {
        assertTrue("Could not find "+tri, expectedTriangles.contains(tri));
    }
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * Convert triangles list into wkt form for debugging purpose
 * @param triangles Triangle array
 * @return String WKT
 */
public static String toWKT(List<DelaunayTriangle> triangles) {
    StringBuilder stringBuilder = new StringBuilder("MULTIPOLYGON(");
    AtomicBoolean first = new AtomicBoolean(true);
    for(DelaunayTriangle triangle : triangles) {
        if(!first.getAndSet(false)) {
            stringBuilder.append(",");
        }
        stringBuilder.append("((");
        TriangulationPoint[] pts = triangle.points;
        addPts(stringBuilder, pts);
        // Close linestring
        stringBuilder.append(", ");
        addPts(stringBuilder, pts[0]);
        stringBuilder.append("))");
    }
    stringBuilder.append(")");
    return stringBuilder.toString();
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
public static void updateFaceNormals( Mesh mesh,
                                      List<DelaunayTriangle> triangles,
                                      CoordinateTransform pc )
{
    FloatBuffer nBuf;
    Vector3 fNormal;
    HashMap<DelaunayTriangle,Vector3> fnMap;
    int size = 3*3*triangles.size();

    fnMap = calculateFaceNormals( triangles, pc );
    
    prepareNormalBuffer( mesh, size );
    nBuf = mesh.getMeshData().getNormalBuffer();
    nBuf.rewind();        
    for( DelaunayTriangle t : triangles )
    {
        fNormal = fnMap.get( t );
        for( int i=0; i<3; i++ )
        {
            nBuf.put(fNormal.getXf());
            nBuf.put(fNormal.getYf());
            nBuf.put(fNormal.getZf());
        }
    }        
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
private static boolean isEdgeSideOfTriangle( DelaunayTriangle triangle,
                                             TriangulationPoint ep,
                                             TriangulationPoint eq )
{
    int index;
    index = triangle.edgeIndex( ep, eq );
    if( index != -1 )
    {
        triangle.markConstrainedEdge( index );
        triangle = triangle.neighbors[ index ];
        if( triangle != null )
        {
            triangle.markConstrainedEdge( ep, eq );
        }
        return true;
    }
    return false;
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * When we need to traverse from one triangle to the next we need
 * the point in current triangle that is the opposite point to the next
 * triangle.
 *
 * @param ep
 * @param eq
 * @param ot
 * @param op
 * @return
 */
private static TriangulationPoint nextFlipPoint( TriangulationPoint ep,
                                                 TriangulationPoint eq,
                                                 DelaunayTriangle ot,
                                                 TriangulationPoint op )
{
    Orientation o2d = orient2d( eq, op, ep );
    if( o2d == Orientation.CW )
    {
        // Right
        return ot.pointCCW( op );
    }
    else if( o2d == Orientation.CCW )
    {
        // Left
        return ot.pointCW( op );
    }
    else
    {
        // TODO: implement support for point on constraint edge
        throw new PointOnEdgeException("Point on constrained edge not supported yet");
    }
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * After a flip we have two triangles and know that only one will still be
 * intersecting the edge. So decide which to contiune with and legalize the other
 *
 * @param tcx
 * @param o - should be the result of an orient2d( eq, op, ep )
 * @param t - triangle 1
 * @param ot - triangle 2
 * @param p - a point shared by both triangles
 * @param op - another point shared by both triangles
 * @return returns the triangle still intersecting the edge
 */
private static DelaunayTriangle nextFlipTriangle( DTSweepContext tcx,
                                           Orientation o,
                                           DelaunayTriangle  t,
                                           DelaunayTriangle ot,
                                           TriangulationPoint p,
                                           TriangulationPoint op)
{
    int edgeIndex;
    if( o == Orientation.CCW )
    {
        // ot is not crossing edge after flip
        edgeIndex = ot.edgeIndex( p, op );
        ot.dEdge[edgeIndex] = true;
        legalize( tcx, ot );
        ot.clearDelunayEdges();
        return t;
    }
    // t is not crossing edge after flip
    edgeIndex = t.edgeIndex( p, op );
    t.dEdge[edgeIndex] = true;
    legalize( tcx, t );
    t.clearDelunayEdges();
    return ot;
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * Adds a triangle to the advancing front to fill a hole.
 * @param tcx
 * @param node - middle node, that is the bottom of the hole
 */
private static void fill( DTSweepContext tcx, AdvancingFrontNode node )
{
    DelaunayTriangle triangle = new DelaunayTriangle( node.prev.point,
                                                      node.point,
                                                      node.next.point );
    // TODO: should copy the cEdge value from neighbor triangles
    //       for now cEdge values are copied during the legalize
    triangle.markNeighbor( node.prev.triangle );
    triangle.markNeighbor( node.triangle );
    tcx.addToList( triangle );

    // Update the advancing front
    node.prev.next = node.next;
    node.next.prev = node.prev;
    tcx.removeNode( node );

    // If it was legalized the triangle has already been mapped
    if( !legalize( tcx, triangle ) )
    {
        tcx.mapTriangleToNodes( triangle );
    }
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
public void createAdvancingFront()
{
    AdvancingFrontNode head,tail,middle;
    // Initial triangle
    DelaunayTriangle iTriangle = new DelaunayTriangle( _points.get(0),
                                                       getTail(),
                                                       getHead() );
    addToList( iTriangle );

    head = new AdvancingFrontNode( iTriangle.points[1] );
    head.triangle = iTriangle;
    middle = new AdvancingFrontNode( iTriangle.points[0] );
    middle.triangle = iTriangle;
    tail = new AdvancingFrontNode( iTriangle.points[2] );

    aFront = new AdvancingFront( head, tail );
    aFront.addNode( middle );

    // TODO: I think it would be more intuitive if head is middles next and not previous
    //       so swap head and tail
    aFront.head.next = middle;
    middle.next = aFront.tail;
    middle.prev = aFront.head;
    aFront.tail.prev = middle;
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * Try to map a node to all sides of this triangle that don't have
 * a neighbor.
 *
 * @param t
 */
public void mapTriangleToNodes( DelaunayTriangle t )
{
    AdvancingFrontNode n;
    for( int i=0; i<3; i++ )
    {
        if( t.neighbors[i] == null )
        {
            n = aFront.locatePoint( t.pointCW( t.points[i] ) );
            if( n != null )
            {
                n.triangle = t;
            }
        }
    }
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
public void prepareTriangulation( TriangulationContext<?> tcx )
{
    if( _triangles == null )
    {
        _triangles = new ArrayList<DelaunayTriangle>( _points.size() );            
    }
    else
    {
        _triangles.clear();                        
    }
    tcx.addPoints( _points );
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
private static void finalizationPolygon( DTSweepContext tcx )
{
    // Get an Internal triangle to start with
    DelaunayTriangle t = tcx.aFront.head.next.triangle;
    TriangulationPoint p = tcx.aFront.head.next.point;
    while( !t.getConstrainedEdgeCW( p ) )
    {
        t = t.neighborCCW( p );
    }
    
    // Collect interior triangles constrained by edges
    tcx.meshClean( t );
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
public void removeFromList( DelaunayTriangle triangle )
    {
        _triList.remove( triangle );
        // TODO: remove all neighbor pointers to this triangle
//        for( int i=0; i<3; i++ )
//        {
//            if( triangle.neighbors[i] != null )
//            {
//                triangle.neighbors[i].clearNeighbor( triangle );
//            }
//        }
//        triangle.clearNeighbors();
    }
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
private void meshCleanReq( DelaunayTriangle triangle )
{
    if( triangle != null && !triangle.isInterior() )
    {
        triangle.isInterior( true );
        _triUnit.addTriangle( triangle );
        for( int i = 0; i < 3; i++ )
        {
            if( !triangle.cEdge[i] )
            {
                meshCleanReq( triangle.neighbors[i] );
            }
        }
    }
}
 

import org.poly2tri.triangulation.delaunay.DelaunayTriangle; //导入依赖的package包/类
/**
 * Creates constraints and populates the context with points
 */
public void prepareTriangulation( TriangulationContext<?> tcx )
{
    if( m_triangles == null )
    {
        m_triangles = new ArrayList<DelaunayTriangle>( _points.size() );
    }
    else
    {
        m_triangles.clear();
    }

    // Outer constraints
    for( int i = 0; i < _points.size()-1 ; i++ )
    {
        tcx.newConstraint( _points.get( i ), _points.get( i+1 ) );
    }
    tcx.newConstraint( _points.get( 0 ), _points.get( _points.size()-1 ) );
    tcx.addPoints( _points );

    // Hole constraints
    if( _holes != null )
    {
        for( Polygon p : _holes )
        {
            for( int i = 0; i < p._points.size()-1 ; i++ )
            {
                tcx.newConstraint( p._points.get( i ), p._points.get( i+1 ) );
            }
            tcx.newConstraint( p._points.get( 0 ), p._points.get( p._points.size()-1 ) );            
            tcx.addPoints( p._points );
        }
    }

    if( _steinerPoints != null )
    {
        tcx.addPoints( _steinerPoints );
    }
}