耳廓修剪三角函数碰撞

Question

我正在努力解决耳廓修剪三角函数libgdx问题。 它在某个时间点进入无限循环并崩溃整个程序。 我记录了a video发生崩溃的位置。三角仪的

源码：

/* 
* Copyright 2010 Mario Zechner (contact@badlogicgames.com), Nathan Sweet (admin@esotericsoftware.com), Nicolas Gramlich 
* 
* Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the 
* License. You may obtain a copy of the License at 
* 
* http://www.apache.org/licenses/LICENSE-2.0 
* 
* Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" 
* BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language 
* governing permissions and limitations under the License. 
*/ 

package com.badlogic.gdx.math; 

import java.util.ArrayList; 
import java.util.Collections; 
import java.util.List; 

/** 
* A simple implementation of the ear cutting algorithm to triangulate simple 
* polygons without holes. For more information: 
* http://cgm.cs.mcgill.ca/~godfried/teaching/cg-projects/97/Ian/algorithm2.html 
* http://www.geometrictools.com/Documentation/TriangulationByEarClipping.pdf 
* 
* @author badlogicgames@gmail.com 
* @author Nicolas Gramlich (Improved performance. Collinear edges are now supported.) 
*/ 
public final class EarClippingTriangulator { 

    private static final int CONCAVE = 1; 
    private static final int CONVEX = -1; 

    private int concaveVertexCount; 

    /** 
    * Triangulates the given (concave) polygon to a list of triangles. The 
    * resulting triangles have clockwise order. 
    * @param polygon the polygon 
    * @return the triangles 
    */ 
    public List<Vector2> computeTriangles(final List<Vector2> polygon) { 
    // TODO Check if LinkedList performs better 
    final ArrayList<Vector2> triangles = new ArrayList<Vector2>(); 
    final ArrayList<Vector2> vertices = new ArrayList<Vector2>(polygon.size()); 
    vertices.addAll(polygon); 

    if(vertices.size() == 3) { 
     triangles.addAll(vertices); 
     return triangles; 
    } 

    while(vertices.size() >= 3) { 
     // TODO Usually(Always?) only the Types of the vertices next to the ear change! --> Improve 
     final int vertexTypes[] = this.classifyVertices(vertices); 

     final int vertexCount = vertices.size(); 
     for(int index = 0; index < vertexCount; index++) { 
     if(this.isEarTip(vertices, index, vertexTypes)) { 
      this.cutEarTip(vertices, index, triangles); 
      break; 
     } 
     } 
    } 

    return triangles; 
    } 

    private static boolean areVerticesClockwise(final ArrayList<Vector2> pVertices) { 
    final int vertexCount = pVertices.size(); 

    float area = 0; 
    for(int i = 0; i < vertexCount; i++) { 
     final Vector2 p1 = pVertices.get(i); 
     final Vector2 p2 = pVertices.get(EarClippingTriangulator.computeNextIndex(pVertices, i)); 
     area += p1.x * p2.y - p2.x * p1.y; 
    } 

    if(area < 0) { 
     return true; 
    } else { 
     return false; 
    } 
    } 

    /** 
    * @param pVertices 
    * @return An array of length <code>pVertices.size()</code> filled with either {@link EarClippingTriangulator#CONCAVE} or 
    * {@link EarClippingTriangulator#CONVEX}. 
    */ 
    private int[] classifyVertices(final ArrayList<Vector2> pVertices) { 
    final int vertexCount = pVertices.size(); 

    final int[] vertexTypes = new int[vertexCount]; 
    this.concaveVertexCount = 0; 

    /* Ensure vertices are in clockwise order. */ 
    if(!EarClippingTriangulator.areVerticesClockwise(pVertices)) { 
     Collections.reverse(pVertices); 
    } 

    for(int index = 0; index < vertexCount; index++) { 
     final int previousIndex = EarClippingTriangulator.computePreviousIndex(pVertices, index); 
     final int nextIndex = EarClippingTriangulator.computeNextIndex(pVertices, index); 

     final Vector2 previousVertex = pVertices.get(previousIndex); 
     final Vector2 currentVertex = pVertices.get(index); 
     final Vector2 nextVertex = pVertices.get(nextIndex); 

     if(EarClippingTriangulator.isTriangleConvex(previousVertex.x, previousVertex.y, currentVertex.x, currentVertex.y, nextVertex.x, nextVertex.y)) { 
     vertexTypes[index] = CONVEX; 
     } else { 
     vertexTypes[index] = CONCAVE; 
     this.concaveVertexCount++; 
     } 
    } 

    return vertexTypes; 
    } 

    private static boolean isTriangleConvex(final float pX1, final float pY1, final float pX2, final float pY2, final float pX3, final float pY3) { 
    if(EarClippingTriangulator.computeSpannedAreaSign(pX1, pY1, pX2, pY2, pX3, pY3) < 0) { 
     return false; 
    } else { 
     return true; 
    } 
    } 

    private static int computeSpannedAreaSign(final float pX1, final float pY1, final float pX2, final float pY2, final float pX3, final float pY3) { 
    float area = 0; 

    area += pX1 * (pY3 - pY2); 
    area += pX2 * (pY1 - pY3); 
    area += pX3 * (pY2 - pY1); 

    return (int)Math.signum(area); 
    } 

    /** 
    * @return <code>true</code> when the Triangles contains one or more vertices, <code>false</code> otherwise. 
    */ 
    private static boolean isAnyVertexInTriangle(final ArrayList<Vector2> pVertices, final int[] pVertexTypes, final float pX1, final float pY1, final float pX2, final float pY2, final float pX3, final float pY3) { 
    int i = 0; 

    final int vertexCount = pVertices.size(); 
    while(i < vertexCount - 1) { 
     if((pVertexTypes[i] == CONCAVE)) { 
     final Vector2 currentVertex = pVertices.get(i); 

     final float currentVertexX = currentVertex.x; 
     final float currentVertexY = currentVertex.y; 

     /* TODO The following condition fails for perpendicular, axis aligned triangles! 
     * Removing it doesn't seem to cause problems. 
     * Maybe it was an optimization? 
     * Maybe it tried to handle collinear pieces ? */ 
//  if(((currentVertexX != pX1) && (currentVertexY != pY1)) || ((currentVertexX != pX2) && (currentVertexY != pY2)) || ((currentVertexX != pX3) && (currentVertexY != pY3))) { 
      final int areaSign1 = EarClippingTriangulator.computeSpannedAreaSign(pX1, pY1, pX2, pY2, currentVertexX, currentVertexY); 
      final int areaSign2 = EarClippingTriangulator.computeSpannedAreaSign(pX2, pY2, pX3, pY3, currentVertexX, currentVertexY); 
      final int areaSign3 = EarClippingTriangulator.computeSpannedAreaSign(pX3, pY3, pX1, pY1, currentVertexX, currentVertexY); 

      if(areaSign1 > 0 && areaSign2 > 0 && areaSign3 > 0) { 
      return true; 
      } else if(areaSign1 <= 0 && areaSign2 <= 0 && areaSign3 <= 0) { 
      return true; 
      } 
//  } 
     } 
     i++; 
    } 
    return false; 
    } 

    private boolean isEarTip(final ArrayList<Vector2> pVertices, final int pEarTipIndex, final int[] pVertexTypes) { 
    if(this.concaveVertexCount != 0) { 
     final Vector2 previousVertex = pVertices.get(EarClippingTriangulator.computePreviousIndex(pVertices, pEarTipIndex)); 
     final Vector2 currentVertex = pVertices.get(pEarTipIndex); 
     final Vector2 nextVertex = pVertices.get(EarClippingTriangulator.computeNextIndex(pVertices, pEarTipIndex)); 

     if(EarClippingTriangulator.isAnyVertexInTriangle(pVertices, pVertexTypes, previousVertex.x, previousVertex.y, currentVertex.x, currentVertex.y, nextVertex.x, nextVertex.y)) { 
     return false; 
     } else { 
     return true; 
     } 
    } else { 
     return true; 
    } 
    } 

    private void cutEarTip(final ArrayList<Vector2> pVertices, final int pEarTipIndex, final ArrayList<Vector2> pTriangles) { 
    final int previousIndex = EarClippingTriangulator.computePreviousIndex(pVertices, pEarTipIndex); 
    final int nextIndex = EarClippingTriangulator.computeNextIndex(pVertices, pEarTipIndex); 

    if(!EarClippingTriangulator.isCollinear(pVertices, previousIndex, pEarTipIndex, nextIndex)) { 
     pTriangles.add(new Vector2(pVertices.get(previousIndex))); 
     pTriangles.add(new Vector2(pVertices.get(pEarTipIndex))); 
     pTriangles.add(new Vector2(pVertices.get(nextIndex))); 
    } 

    pVertices.remove(pEarTipIndex); 
    if(pVertices.size() >= 3) { 
     EarClippingTriangulator.removeCollinearNeighborEarsAfterRemovingEarTip(pVertices, pEarTipIndex); 
    } 
    } 

    private static void removeCollinearNeighborEarsAfterRemovingEarTip(final ArrayList<Vector2> pVertices, final int pEarTipCutIndex) { 
    final int collinearityCheckNextIndex = pEarTipCutIndex % pVertices.size(); 
    int collinearCheckPreviousIndex = EarClippingTriangulator.computePreviousIndex(pVertices, collinearityCheckNextIndex); 

    if(EarClippingTriangulator.isCollinear(pVertices, collinearityCheckNextIndex)) { 
     pVertices.remove(collinearityCheckNextIndex); 

     if(pVertices.size() > 3) { 
     /* Update */ 
     collinearCheckPreviousIndex = EarClippingTriangulator.computePreviousIndex(pVertices, collinearityCheckNextIndex); 
     if(EarClippingTriangulator.isCollinear(pVertices, collinearCheckPreviousIndex)){ 
      pVertices.remove(collinearCheckPreviousIndex); 
     } 
     } 
    } else if(EarClippingTriangulator.isCollinear(pVertices, collinearCheckPreviousIndex)){ 
     pVertices.remove(collinearCheckPreviousIndex); 
    } 
    } 

    private static boolean isCollinear(final ArrayList<Vector2> pVertices, final int pIndex) { 
    final int previousIndex = EarClippingTriangulator.computePreviousIndex(pVertices, pIndex); 
    final int nextIndex = EarClippingTriangulator.computeNextIndex(pVertices, pIndex); 

    return EarClippingTriangulator.isCollinear(pVertices, previousIndex, pIndex, nextIndex); 
    } 

    private static boolean isCollinear(final ArrayList<Vector2> pVertices, final int pPreviousIndex, final int pIndex, final int pNextIndex) { 
    final Vector2 previousVertex = pVertices.get(pPreviousIndex); 
    final Vector2 vertex = pVertices.get(pIndex); 
    final Vector2 nextVertex = pVertices.get(pNextIndex); 

    return EarClippingTriangulator.computeSpannedAreaSign(previousVertex.x, previousVertex.y, vertex.x, vertex.y, nextVertex.x, nextVertex.y) == 0; 
    } 

    private static int computePreviousIndex(final List<Vector2> pVertices, final int pIndex) { 
    return pIndex == 0 ? pVertices.size() - 1 : pIndex - 1; 
    } 

    private static int computeNextIndex(final List<Vector2> pVertices, final int pIndex) { 
    return pIndex == pVertices.size() - 1 ? 0 : pIndex + 1; 
    } 
} 

崩溃发生@在上面链接的源代码53＃线...
while循环computeTriangles功能与以下的条件：当（vertices.size（） > = 3）{...

Answer 1

问题是你的多边形需要是简单的，即它不能相交。 javadoc说明了这一事实。但是，对无效输入进行无限循环是非常糟糕的行为。

也就是说，还有一些错误会导致三角函数将有效的简单多边形剪裁成一个具有自交点的多边形，从而陷入无限循环。当点（几乎或完全）共线时，可能发生这种情况。至少有两个关于此问题的错误报告：我自己的 #1407以及 #207，它被标记为固定，但可能仅在某些情况下才被修复。

我发送了刚合并的a pull request，因此2013年6月30日之后的任何libgdx版本都应该具有较少的这些问题。