python - Pandas 能否在没有迭代的情况下找到连接任何一对**点**并且不与任何给定的**线**相交的所有线？

Question

给定一个正确定义的点列表和一个线列表:

Pandas 能否在没有迭代的情况下找到连接任何一对点并且不与任何给定线相交的所有线？

我目前正在寻求解决方案，正如您在图片中看到的那样，但我必须在此过程中进行迭代，而该迭代使一切都变得非常缓慢。

在图像中，点列表是绘制的彩色点，线列表是烛台。期望的结果是黑线。

虽然这个问题旨在提供理论解决方案，或者如果可能的话或者除了迭代之外没有其他方法的概念确认，这里是我当前使用的代码，以防它有帮助: http://pastebin.com/4DiKVy26

Answer 1

我不了解 Pandas，但我可以看到您正在尝试做什么，是的，它可以更快地完成。我将黑线称为射线，原因我希望会变得清楚；在您的算法中，使用 m 点和 n 行，您找到所有 m(m-1)/2 条射线，然后进行 2n 次比较以过滤它们:m*(m-1)*n => 大小的立方的输入。有一种方法可以使输入中的二次方。

您所描述的可以通过 raycasting 的形式解决 (虽然更简单，因为它是二维的):把点想象成光；如果目标不在直线的阴影中，则源点只能将光线转换到目标点。所以我们从一个点开始，然后向右移动到您可能会照亮的一系列线条和点上。当我们经过线条时，阴影区域会扩大；但是对于任何 x 值，我们只需要知道阴影边缘的 2 个梯度就可以知道 y 值是否在阴影中。当我们通过每条向右走的线时，更新阴影的渐变。当我们通过每个点时，我们检查它是否位于阴影之外；如果有的话，我们有一条射线。对每个点重复这个过程，你就完成了。这大致相当于 m*(m-1)/2+m*n 次计算，可扩展性更好。