更准确的顶点顺时针排序

我用几个算法顺时针顶点排序仍然不能排序，因为它应该进行排序。更准确的顶点顺时针排序

聚总是与相同尺寸的板缺掉较小的正方形广场（让我们为它们命名块）。所以说我有6x6的方块和1x1的块。更具体地：正方形有顶点：[0,0]，[5,0]，[5,5]，[0,5]。如果我会在位置切大块关[0,0]（像小方做了顶点，从[0,0]到[1,1]路口），方看起来是这样的：

他的顶点现在：[0,1]，[1,1]，[1,0]，[5,0]，[5,5]，[0,5]

它的罚款。但让我们再做一些交叉点。我不会在位置[1,0]显示第二个交点，因为没有问题。现在，如果我做第三个十字路口，说在位置[0,1]，它看起来像这样：

当然，它应该是这样的：

所以正如你所看到的，它只是排序失效，这之前[0,2]

我不知道是否会排序很好，当我会喜欢检查从质心的距离添加的东西排序顶点[1,2]。嗯..下面是这个排序的代码：

function (a, b) { 

    var distance1 = Math.sqrt(Math.pow(a.x - centroid.x, 2) + Math.pow(a.y - centroid.y, 2)); 
    var distance2 = Math.sqrt(Math.pow(b.x - centroid.x, 2) + Math.pow(b.y - centroid.y, 2)); 
    var a1 = Math.acos((a.x - centroid.x)/distance1); 
    var a2 = Math.acos((b.x - centroid.x)/distance2); 

    if (a.y > centroid.y) 
     a1 = Math.PI + Math.PI - a1; 

    if (b.y > centroid.y) 
     a2 = Math.PI + Math.PI - a2; 

    return a1 - a2; 

}

和质心：

function (vertices) { 
    var 
     x = 0, 
     y = 0, 
     pointCount = vertices.length; 

    for (var i = 0; i < pointCount; i++){ 
     x += vertices[i].x; 
     y += vertices[i].y; 
    } 

    x = x/pointCount; 
    y = y/pointCount; 

    return new vec2(x, y); 
}

来源

2016-06-12 ThaFog

什么是'centroid'的价值在你的例子中？是否预计？ – Bergi

基于代码'centroid'应在[2,2] – ThaFog

那么在这种情况下有也难怪为什么[1,2]各种前[0,2] - 都具有相同的角度，重心和可以被放置在任一订单。您需要选择更好的算法来定位要分类的中心，而不是更改排序。 – Bergi

好吧，我已经实现了clockWise排序后的新功能，即角度优化。整个算法是这样的：

如果有任何sugestions，请随时

这里是角优化代码：

for (var i = 1; i < vertices.length; i++) { 
     var a = vertices[i - 1]; 
     var b = vertices[i]; 
     var j = i; 

     do { 
      var distanceAngle = Math.abs(Math.atan2(a.y - b.y, a.x - b.x)); 
      if (
       distanceAngle == Math.PI/2 || 
       distanceAngle == Math.PI || 
       distanceAngle == 3 * Math.PI/2 || 
       distanceAngle == 2 * Math.PI || 
       distanceAngle == 0 
      ) 
      { 
       var tmp = vertices[i]; 
       vertices[i] = vertices[j]; 
       vertices[j] = tmp; 
       break; 
      } 
      j++; 
      b = vertices[j]; 
     } while (j < vertices.length); 
    }

来源

2016-06-15 01:12:17 ThaFog

我真的没有检查是否有您比较函数的任何错误，但它过于复杂。您可以使用Math.atan2来获得两点之间的角度。你的功能应该看起来像

function(a, b) { 
    return Math.atan2(a.y - centroid.y, a.x - centroid.x) 
     - Math.atan2(b.y - centroid.y, b.x - centroid.x); 
}

来源

2016-06-12 22:11:00 Bergi

我整理了这样相信我还是不可惜还是烦，我的实际功能更好的排序这个广场的顶点 – ThaFog

更准确的顶点顺时针排序

回答

相关问题