对于许多圆圈，查找圆圈内的所有线。优化

Question

我正在开发一个程序，我需要找到位于某个半径的某个笛卡尔点的圆中的所有线。

目前，对于每个圆，我都在遍历所有的线并检查线 enters/contacts 是否在任何一点都是圆。

代码基本上是这样的。

for (int i = 0; i < num_circles; i++) 
{
    for (int j = 0; j < num_lines; j++) 
    {
        if(lineIntersectWithCircle(circle[i], lines[j])) 
        {
            //Append line[j] to a list of lines intersecting with circle[i];

            //some code
        }
    }
}

我一直在想很多办法来优化这个，但我遇到了麻烦。我已按最小笛卡尔距离对圆圈进行排序，并按最大距离对线进行排序。通过这种方式，您可以进行一些优化，但它非常小，因为一旦达到 line[j].max > circle[i].min 的位置，您仍然必须遍历所有其余行。

我对我的交集检查方法没问题，我只是想尽量减少调用它的次数。

有什么好的方法吗？

Answer 1

最便宜的方法是在更昂贵的相交测试之前检查两个形状（线和圆）的边界 extents/rectangles。很有可能您甚至可以动态计算 line/circle 的范围，而不是预先计算，并且仍然可以获得不错的性能提升，除非您的 line/circle 交集已经非常便宜。

一种非常有效但需要更多工作的方法是只创建一个网格。您可以使用上面计算的边界矩形来廉价地查看您的形状与哪些网格单元格相交。

struct GridNode
{
    // Points to the index of the next node in the grid cell
    // or -1 if we're at the end of the singly-linked list.
    int next_node;

    // Points to the index of the shape being stored.
    int shape;
};

struct GridCell
{
    // Points to the first node or -1 if the cell is empty.
    int first_node;
};

struct Grid
{
    // Stores the cells in the grid. This is just illustrative
    // code. You should dynamically allocate this with adjustable
    // grid widths and heights based on your needs.
    struct GridCell cells[grid_width * grid_height];

    // Stores the nodes in the grid (one or more nodes per shape
    // inserted depending on how many it intersects). This is 
    // a variable-sized array you can realloc needed (ex: double 
    // the size when you're out of room).
    struct GridNode* nodes;

    // The maximum number of nodes we can store before realloc.
    int node_cap;

    // The number of nodes inserted so far. realloc when this
    // exceeds node_cap.
    int node_num;
};

...类似的东西。通过这种方式，大多数时候您可以将元素插入到网格中，而不仅仅是执行一些整数（模拟指针）操作并将一些网格节点条目添加到这个可变大小的 nodes 数组中。堆分配很少发生。

我发现在实践中，如果你有许多动态元素从一个单元格移动到下一个单元格，就像在 2D 视频游戏中一样，在我们需要快速碰撞检测的同时，一切都在不断移动，并且可以如果您小心节点的内存布局以在遍历与您正在测试的形状相交的网格单元时最大程度地减少缓存未命中，甚至可以与四叉树进行搜索。您甚至可以在构建网格后执行 post-pass，以根据您需要的交集搜索效率重新排列每个节点的内存以进行缓存友好的列表迭代。如果你想变得花哨，你可以使用 Bresenham 来精确地计算出一条线与哪些网格单元相交，例如，但是考虑到你正在做的事情的二次复杂性，你可以成倍地提高而不用理会它并且只是在一种非常简单的边界矩形方法。

基本上要找到一个交点，首先要抓住形状的边界矩形。然后查看它与网格中的哪些单元格相交。现在检查与原始形状相交的网格单元中包含的形状的交集。通过这种方式，您可以朝着恒定时间的复杂性努力，除了巨大的形状（O(n) 的最坏情况），希望这种情况很少见。

当事物经常移动时，我什至发现它们在 3 维中的用途。它们通常比提供广泛搜索加速的八叉树、BVH 和 kd 树变体便宜，但以更昂贵的构建和更新为代价，如果您对每个网格单元使用单链表的策略，它不会不必单独分配节点，即使是第 3 维，您也可以将其存储在非常合理的内存量中。我不会将它的 3 维版本用于光线跟踪，但它对于 3D 碰撞检测非常有用，例如检测每帧移动的粒子之间的碰撞。

Answer 2

与任何事情一样，这取决于您的用例。如果您有固定数量的线或不经常添加，您可能需要预先计算一些计算以确定线的任何部分是否在圆心的半径距离内

从直线和点之间的最短距离的方程开始，比较该距离小于圆的半径：

//abs(Cx*(y1-y0)-Cy*(x1-x0)+x1*y0-y1*x0)/sqrt((y1-y0)*(y1-y0)+(x1-x0)*(x1-x0))<R
//pull out some constants and cache these as they are initialized
//int y10 = y1-y0, //add to the line struct
//  x10 = x1 -x0,
//  delta = x1*y0-y1*x0,
//  sides = (y10)*(y10)+(x10)*(x10);
//  R2 = R*R; //add to the circle struct
//now the equation factors down to
//abs(Cx*(y10)-Cy*(x10)+delta)/sqrt(sides)< R //replace constants
//abs(Cx*(y10)-Cy*(x10)+delta) < sqrt(sides) * R //remove division
//pow(Cx*(y10)-Cy*(x10)+delta , 2.0) < sides * R * R //remove sqrt()
//int tmp = Cx*(y10)-Cy*(x10)+delta //factor out pow data
//tmp * tmp < sides * R2 //remove pow() and use cache R squared
//now it is just a few cheap instructions

现在检查应该只有 4 个整数乘法，2 个 add/subtract 和一个比较。

lineIntersectWithCircle(size_t circle, size_t line){
  struct circle C = circle_cache[circle]; //these may be separate arrays
  struct line L = line_cache[line];       //from your point data

  long tmp = C.x * L.y10 - C.y * L.x10 + L.delta;
  return (tmp*tmp < L.sides * C.R2);
}

...但您可能想检查一下我的计算结果 - 已经有一段时间了。我还假设这些点是整数 - 根据需要更改为浮点数 - 它应该仍然相对较快。

如果速度不够快，您可以为圆和线的边界框添加额外的数据

bool lineIntersectWithCircle(size_t circle, size_t line){
  struct circle C = circle_cache[circle]; //these may be separate arrays
  struct line L = line_cache[line];       //from your point data

  //if the bounding boxes don't intersect neither does the line
  //this may not be _that_ helpful and you would need to:
  // figure out the bounding boxes for each line/circle
  // and cache additional data
  if (C.leftx > L.rightx || L.leftx > C.rightx) //a box is to the side
    return 0;
  if (C.topy < L.boty || L.topy < C.boty) //a box is below/above
    return 0;

  //the bounding boxes intersected so check exact calculation
  long tmp = C.x * L.y10 - C.y * L.x10 + L.delta;
  return (tmp*tmp < L.sides * C.R2);
}

对于许多圆圈，查找圆圈内的所有线。优化

Find all lines within a circle, for many circles. Optimization

c

optimization

computational-geometry