拓扑层分离算法

Question

我有以下问题。假设在平面上有一大排曼哈顿多边形（它们的边与x或y轴平行）。我需要找到一个多边形，放在比一些价值三角洲更接近。问题是 - 如何以最有效的方式做到这一点，因为这些多边形的数量非常大。如果您能给我一个实施解决方案的参考资料，我会很高兴，这将很容易适应我的情况。

Answer 1

首先想到的是扫描和修剪算法（也称为排序和扫描）。

基本上，你首先找出沿每个轴的每个形状的'边界'。对于x轴，这些将是形状上最左边和最右边的点。对于y轴，最顶部和最底部。

比方说你有一个结合的结构，看起来是这样的：

struct Bound 
{ 
    float value;  // The value of the bound, ie, the x or y coordinate. 
    bool isLower; // True for a lower bound (leftmost point or bottommost point). 
    int shapeIndex; // The index (into your array of shapes) of the shape this bound is on. 
}; 

创建这些界限中的两个阵列，一个用于X轴，一个用于y。

Bound xBounds* = new Bound[2 * numberOfShapes]; 
Bound yBounds* = new Bound[2 * numberOfShapes]; 

您还需要两个数组。跟踪每对形状彼此靠近的轴的数组以及候选对的数组。

int closeAxes* = new int[numberOfShapes * numberOfShapes]; 

for (int i = 0; i < numberOfShapes * numberOfShapes; i++) 
    CloseAxes[i] = 0; 

struct Pair 
{ 
    int shapeIndexA; 
    int shapeIndexB; 
}; 

Pair candidatePairs* = new Pair[numberOfShapes * numberOfShape]; 
int numberOfPairs = 0; 

迭代通过你的形状的列表，并适当地填补了阵列，有一点需要注意： 既然你检查亲近，而不是路口，加三角洲各上限。 然后使用您喜欢的任何算法按值排序每个数组。

接下来，执行以下操作（并重复用于Y轴）：

for (int i = 0; i + 1 < 2 * numberOfShapes; i++) 
{ 
    if (xBounds[i].isLower && xBounds[i + 1].isLower) 
    { 
     unsigned int L = xBounds[i].shapeIndex; 
     unsigned int R = xBounds[i + 1].shapeIndex; 

     closeAxes[L + R * numberOfShapes]++; 
     closeAxes[R + L * numberOfShapes]++; 

     if (closeAxes[L + R * numberOfShapes] == 2 || 
      closeAxes[R + L * numberOfShapes] == 2) 
     { 
      candidatePairs[numberOfPairs].shapeIndexA = L; 
      candidatePairs[numberOfPairs].shapeIndexB = R; 
      numberOfPairs++; 
     } 
    } 
} 

所有候选对是小于增量隔开在每个轴上。现在简单地检查每个候选人对，以确保他们实际上小于三角洲分开。我现在不会详细讨论如何做，因为我没有真正考虑过这个问题，但希望我的回答至少能让你开始。我想你可以检查每一对线段并找到最短的x或y距离，但我相信有一个更有效的方式去实施'窄阶段'步骤。

显然，这个算法的实际实现可能会更加复杂。我的目标是使解释清晰简洁而不是优雅。根据您的形状布局和您使用的排序算法，就效率而言，其单次运行大约在O（n）和O（n log n）之间，而不是O（n^2）来检查每个一对形状。