python - 曲线与没有明显方程的直线之间的碰撞检测

Question

我正在使用 Perlin 噪声来创建 2d 风景。执行以下操作的最简单/最有效的方法是什么：

如果我选择柏林噪声线上方的任何点，然后提供一个向量/方向，我如何判断一条线是否来自给定方向的该点：

一个。触线？

湾。如果它接触线，从原点到线与柏林噪声线碰撞的点的距离是多少？

如果它是直线，我知道该怎么做，但事实并非如此。顺便说一句，我正在使用 pygame 进行此操作，因此如果可以使用任何 pygame 特定功能，那就太好了。

一张图：

抱歉，我无法向您提供有关我的 Perlin 噪音细节的任何细节，但它仍在开发中。

我不认为检查噪声的每个 x 值是可行的，因为我正在处理像素比例，因此可能会发生以下情况：

在这种情况下，粉红色代表我正在测试的线，蓝色代表我的 Perlin 噪声的像素图。在这种情况下，检查每个值将无法产生正确的结果

有人问了一个 Perlin 噪声的例子，一个点的x值是列表的索引，y值是list[x]。

噪音：

[0.0, 1.2950474273729242, 2.302306537551865, 3.021777330536823, 3.4534598063277975, 3.597353964924789, 3.4534598063277975,
 3.021777330536823, 2.302306537551865, 1.2950474273729242, 0.0, 3.910627653655182, 6.952226939831434, 9.124797858528757,
 10.428340409747152, 10.862854593486615, 10.428340409747152, 9.124797858528757, 6.952226939831434, 3.9106276536551814,
 0.0, 2.3925761696810253, 4.253468746099601, 5.5826777292557255, 6.3802031191494, 6.646044915780626, 6.3802031191494,
 5.5826777292557255, 4.253468746099601, 2.3925761696810257, -0.0, -1.3453317543307322, -2.3917008965879676,
 -3.1391074267717074, -3.5875513448819514, -3.7370326509187, -3.5875513448819514, -3.139107426771708,
 -2.3917008965879676, -1.345331754330732, 0.0, 1.9499487707658063, 3.4665755924725437, 4.549880465120213,
 5.199863388708816, 5.4165243632383495, 5.199863388708816, 4.549880465120213, 3.4665755924725437, 1.9499487707658059,
 0.0, 2.025500578709133, 3.6008899177051252, 4.726168016987977, 5.401334876557688, 5.626390496414258, 5.401334876557688,
 4.726168016987977, 3.6008899177051252, 2.025500578709133, 0.0, 1.71832580933312]

例如，第一个点是 (0, 0) 第二个是 (1, 1) 第三个是 (2, 2) 顺便说一句，我正在四舍五入到最接近的整数。

标签： pythonmathgeometry

Answer 1

通过线段相交检查进行二进制搜索似乎可行。

绝对在角线的相对两侧选择两个点（如果需要对角线做同样的事情，在噪声的相对侧绝对选择两个点）。确认两条线段相交。然后在这些点之间选择一个点（可能只使用平均点(X1+x2)/2, (Y1+Y2)/2）来检查线段，看看它们是否也交叉。丢弃不相交的线段与角度线相交。对两个部分都这样做（这样你就会越来越接近两边）。

唯一潜在的问题是是否有多个交叉点。尽管在这种情况下，您可以根据需要将单个二进制搜索拆分为两个二进制搜索，直到找到所有交集，或者您认为最有意义的任何内容。