我目前正在通过以所需角度从该点绘制一条任意（长）距离的线，然后使用python gis工具包（形状）使其与折线相交来实现此目的。如果有多个交叉点，则按距离对它们进行排序，然后选择最接近的一个。
此方法有效，但有点笨拙。有没有更有效的方法来计算最接近的交点？几乎似乎是光线追踪（我对此了解甚少），但在网上找不到适用于我的案例的大量信息。
我考虑的另一种方法是遍历折线中的每个线段，并使用y = mx + b查看该线段是否与该点相交。折线可能包含许多段，可能很长，但是我也在线看到了一些排序技巧，可以使这种方法更有效。有什么我想念的方法吗？
#1 楼
鉴于您要测试与许多不同起点和方向的光线的相交，因此值得研究光线跟踪样式的加速结构，例如边界体积层次（BVH）。在2D中，这看起来像是一棵轴对齐的边界框树，用于划分空间。该树的每个叶节点都将存储对折线附近线段的一小部分的引用以及包含这些线段的边界框。较高的节点将存储一个包含所有子项的边界框。关于BVH构造并遍历大量材料，因此建议进行一些搜索并阅读。通过从整个折线的边界框开始并递归拆分，实现自顶向下的构造方法并不难。然后，要将其用于加速，当您进行光线查询时，您可以找到光线接触了哪些BVH节点，并仅测试这些节点中的线段是否有交点。想针对您使用轮廓线的原始问题提出另一种方法。在我看来，这是Delaunay三角剖分可能非常有用的地方。它基本上构造了一个三角形网格，该三角形网格将一组输入顶点和边连接起来。例如，这是我在互联网上找到的等高线图：
现在，这里是受约束的Delaunay三角剖分，它是使用Jonathan Shewchuk的“三角”程序计算的：
如您所见，三角剖分为您提供了有关等高线图中相邻区域的大量信息，因此我怀疑您可以找到一种获取方法您想从中获得什么。例如，您可以找到所有与两条感兴趣的轮廓线接触的三角形，并查看它们的边缘，中点等。
评论
$ \ begingroup $
谢谢您的建议内森，我将研究BVH。 Delaunay三角剖分可能会有用，但是我在您发布的示例中看到了潜在的问题。我遇到的最大问题是，一个轮廓明显长于另一个轮廓。在图像的ENE脊上，三角形跨越相同的轮廓，这是我确实需要线条跨越两个轮廓以内插平滑曲线的位置类型。我可能不得不使用光线跟踪类型的方法。
$ \ endgroup $
–迈克·班尼斯特（Mike Bannister）
16年3月14日在17:05
$ \ begingroup $
@MikeBannister，是的，在某些地方三角形跨越相同的轮廓，但是您可以检测到并过滤掉它们，而仅查看跨越两个相邻轮廓的三角形。
$ \ endgroup $
–内森·里德（Nathan Reed）
16-3-14在21:17
评论
您是否要针对相同的折线从同一起点重复测试许多不同角度的光线？还是起点和角度都可变？ （我要说的是，有可能建立一个加速这些查询的加速结构，但是哪种结构最好取决于它的使用方式。）内森（Nathan），我将从一个起点开始进行许多测试。然后从另一个起点，另一个起点等测试多个角度。我实际上有两条轮廓线的线段，并试图在两条轮廓线之间绘制一条线。我当前的策略是在两条线之间以半规则间隔绘制一系列线。然后，我可以在所有短线之间创建一条折线。我目前正在研究如何创建在两个轮廓之间相交的线，由于其中一些轮廓线的弯曲和褶皱，这非常困难。
那么，您的Triong会找到曲线上最接近的点吗？
我测试了曲线上最接近的点，虽然它可以工作，但有太多情况根本无法工作或效果不佳。我目前正在考虑的方法是基于角度的。在其他两条线之间绘制一条线时，将创建4个角度。我在想，当所有4个角度都尽可能接近90度时，就会创建“最佳”线。因此，我打算在给定位置绘制每条可能的线（间隔为5或10度或类似角度），并根据4个角度的排名选择最佳线。
您对使用预先计算的加速度结构的解决方案感兴趣吗？ Bsp树和可能的vornoi图似乎很有用（：