C＃ - 加速使用嵌套for循环的列表比较

Question

我目前正在开发一个测试程序，以确保主板上的孔不是彼此太靠近或者它们没有重叠。

为了做到这一点，我保持所有的洞X，Y坐标和半径的称为对象holeInfo的和列表holeInfoList内的对象。

我目前使用嵌套的for循环要经过所有的洞和一个基本的数学公式的检查孔之间的距离。

这里是我使用的功能：

public void checkHoleConditions() 
{ 
    for (int i = 0; i < holeInfoList.Count - 1; i++) 
    { 
     errorType = new List<string>(); 

     for (int j = i + 1; j < holeInfoList.Count; j++) 
     { 
      holeMinSpaceFailed = false; 

      if (failsHoleConditions(holeInfoList[i], holeInfoList[j])) 
      { 
       if (holeMinSpaceFailed) 
       { 
        errorType.Add("X: " + holeInfoList[j].holeXCoordinate + " Y: " + holeInfoList[j].holeYCoordinate + "R: " + holeInfoList[j].holeDiameter + " too close."); 
       } 
       else 
       { 
        errorType.Add("X: " + holeInfoList[j].holeXCoordinate + " Y: " + holeInfoList[j].holeYCoordinate + "R: " + holeInfoList[j].holeDiameter + " overlap."); 
       } 

       invalidHole = new InvalidHole(holeInfoList[i], errorType); 
       invalidHoleList.Add(invalidHole); 
       Console.WriteLine("Hole Error Detected"); 
      } 
      else 
      { 
       Console.WriteLine("Hole Check Successful"); 
      } 
     } 
    } 
} 

public bool failsHoleConditions(HoleInfo holeOne, HoleInfo holeTwo) 
    { 
     float holeOneXCoordinate = holeOne.holeXCoordinate; 
     float holeOneYCoordinate = holeOne.holeYCoordinate; 
     float holeOneRadius = holeOne.holeDiameter/2; 

     float holeTwoXCoordinate = holeTwo.holeXCoordinate; 
     float holeTwoYCoordinate = holeTwo.holeYCoordinate; 
     float holeTwoRadius = holeTwo.holeDiameter/2; 

     float holeXDifferenceSquared = (float)Math.Pow((holeOneXCoordinate - holeTwoXCoordinate), 2); 
     float holeYDifferenceSquared = (float)Math.Pow((holeOneYCoordinate - holeTwoYCoordinate), 2); 
     float distanceBetweenCenters = (float)Math.Sqrt(holeXDifferenceSquared + holeYDifferenceSquared); 

     float distanceBetweenHoles = distanceBetweenCenters - (holeOneRadius + holeTwoRadius); 

     if (distanceBetweenHoles <= 0) 
     { 
      return true; 
     } 
     else if (distanceBetweenHoles <= minimumSpace) 
     { 
      holeMinSpaceFailed = true; 
      return true; 
     } 
     return false; 
    } 

目前，我的程序将测试在约2.5分钟，254个列表对象。考虑到这是一个测试程序，2.5分钟只有254个孔是很长时间的。

为了让测试运行更快，我可以实现哪些算法？

Answer 1

holeMinSpaceFailed永远不会为真快则Math.Pow

没有必要采取的Sqrt - 刚方minimumSpace

东西喜欢这个。 运行100万300毫秒。你的代码需要几分钟才会出错。

static byte HoleTooClose(HoleInfo x, HoleInfo y, float minDistance) 
{ 
    float holeSize = (x.Diameter + y.Diameter)/2; 
    float deltaX = y.X - x.X; 
    float deltaY = y.Y - x.Y; 

    float distanceSquared = deltaX * deltaX + deltaY * deltaY - holeSize * holeSize; 

    if (distanceSquared <= 0) 
    { 
     return 0; 
    } 

    float minDistanceSquared = minDistance * minDistance; 
    if (distanceSquared <= minDistanceSquared) 
    { 
     return 1; 
    } 

    return 2; 
} 

internal struct HoleInfo 
{ 
    public float Diameter { get; internal set; } 
    public float X { get; internal set; } 
    public float Y { get; internal set; } 
    public HoleInfo (float x, float y, float diameter) 
    { 
     X = x; 
     Y = y; 
     Diameter = diameter; 
    } 
} 


static bool DistanceTooClose(System.Windows.Point x, System.Windows.Point y, Double minDistance) 
{ 
    double deltaX = Math.Abs(y.X - x.X); 
    double deltaY = Math.Abs(y.Y - x.Y); 
    double distanceSquared = deltaX * deltaX + deltaY * deltaY; 
    //double distance = Math.Sqrt(distanceSquared); 
    Double minDistanceSquared = minDistance * minDistance; 
    return (distanceSquared <= minDistanceSquared); 
} 

Answer 2

如果你需要测试一切人反对一切，一个优化可以把它们放在一个n×n的矩阵，而不是一个列表。然后，并行执行验证。矩阵越大，核心越多，效果越好。并行也可以在列表中执行，但我不能100％确定.Net是否决定等待每个线程结束，因为该算法是连续的。

如果您的方法使用欧几里德距离，您可以尝试先根据此距离对列表进行排序。 sqr（x）+ sqr（y）相对于0可以是首先排序的分数。我认为.Net可以轻松处理这种排序。之后，只需运行你的算法，直到第一个允许的电路。然后，你都知道了，必须接受，所以你才会在列表

Answer 3

这种解决方案的灵感的第一要素是执行物理引擎，以及优化那里照顾碰撞检测。

我并不知道这完全是如何工作的，并为更好的解决方案，你应该试试这个研究ODE或子弹动态。

基本上解决方案是对象（空穴）分离成岛屿，并且仅在每个对象的位置进行比较的对象在相同的岛。如果你不能想出一种方法来正确分离岛屿，你可以这样做：

假设我们有一个方形字段有125个对象，5乘5。你可以把它分成25个主要的正方形岛，然后是8个相交岛（沿着主岛边缘的长岛，这些岛的最小边应该是你想要计算的最小距离）。群岛可以重叠。你必须解析整个列表一次才能进行分割。这意味着到目前为止，我们总共循环了125个项目 - O(n)。

接下来，对于每个岛屿（共33件，O(n^(2/3))，发现比他们要，更贴近使用那些相同的嵌套循环对象。共有每个岛屿的复杂性是O((n/n^(2/3))^2) = O(n^(2/3))。时报岛的数量，我们这个算法的总体复杂度= O(n^(4/3))，它小于最初出现的O(n^2)

希望这是有道理的，如果你愿意，我可以写一个Python演示程序，只是它会有很多代码。

编辑：
或者你可以只使用2D物理引擎，用直径等于孔之间的最小距离绘制对象为圆，然后让它检测碰撞。或者从那里取得相关的代码（如果许可证允许的话），因为整个物理引擎对于这项任务来说有点矫枉过正。
https://github.com/VelcroPhysics/VelcroPhysics

编辑2：

254对象列表

我还以为你解析254个不同的板。我强调的这个解决方案只有在巨大的计算负载中才有意义。如果failsHoleConditions是真的
不用跑来逻辑通过这样的

x * x是