在样条/贝塞尔曲线上检查一个点位于哪些点之间。

Question

这是我要解决的问题。我有包含3个点（x1，y1），（x2，y2），（x3，y3）的贝塞尔曲线（在二维平面上）。我想要弄清楚的是，如果用户在贝塞尔曲线上单击第四个点，点击点是否位于点1和点2之间，或者位于点2和点3之间。当直接单击该线时，才记录点击点，因此它必须位于点1和点2之间或点2和点3之间。

这些线在编译时随机创建，并且可以从任何（x，y）位置开始和结束。 构成线的3组点是起始点、曲线点和结束点。这三个点是线的控制点。然后从控制点创建线对象。每次运行程序时都会随机创建控制点，使样条线每次都不同。

对于这个问题，是否应遵循特定的算法？我正在使用javascript编写代码，但任何类似于c ++或java的伪代码都可以。感谢您的帮助。

- TeddyG

---

你是指二次贝塞尔曲线吗？ - MBo

这些点 (x1, y1), (x2, y2), (x3, y3) 是控制点吗？还是已知在曲线上的任意点？ - finnw

你说的“在点1和点2之间”以及“在点2和点3之间”是什么意思？如果你的三个点形成一个真正的曲线，那么三角形{1,2,3}内的任何一点既在1和2之间，也在2和3之间。你能否更新你的帖子，更准确地解释你想要实现什么？（最好添加一张图片，展示一个或多个点配置的示例以及你想要检测到的内容） - Mike 'Pomax' Kamermans

你更新的帖子更清晰了，谢谢。 - Mike 'Pomax' Kamermans

您需要确定用户的点击是否在曲线上吗？还是已知道了？这是如何确定的？ - agentp

Answer 1

构建一个查找表（LUT），这样当用户单击它时，您就可以将他们单击的（x，y）坐标解析为曲线的t 值（或者您称之为控制变量的任何内容）。与基于（x，y）坐标评估相比，这几乎是不可能的，而是将所有四个坐标解析为t 值，这变得非常简单：

假设（x1，y1）为 t=0，(x2，y2) 为某些 T 的 t=（x3，y3）为t=1，如果用户在曲线上单击任何位置，我们会得到一个新的 t 值。 如果该值小于T，则该点位于第1和第2点之间，如果大于T，则位于第2和第3点之间。

构建查找表应该是每条曲线的一次操作，在绘制曲线时，第一次运行，因为那时您已经将t 值映射到（x，y）坐标，所以您可以“免费”构建反向映射。如果您没有控制绘图代码，那么您将不得不在创建曲线时运行自己的代码。

这有一个问题：您在此处给出的曲线由三个曲线上点定义，不是定义Bezier曲线的通常方式。对于Bezier曲线，控制点定义曲线“船体”；对于二次曲线（有三个点），这意味着点1和3在曲线上，但点2则完全不在曲线上。要找到基于这三个点的真正Bezier曲线（即通过这三个点的曲线），您需要运行将三个点转换为真正曲线的算法。

（完整代码告诉您如何做到这一点，基本上超出了这个答案的范围，但我在关于Bezier曲线的长篇文章中解释了这一点，最终形成了http://pomax.github.io/bezierinfo/#pointcurves用于基于三个点形成真正曲线）

- Mike 'Pomax' Kamermans

---

这不是真正的贝塞尔曲线，而更像是样条曲线。所有点都在曲线上。我仍然困惑于查找表如何帮助解决此情况，因为构成线条的点始终不同，并且每次运行时线条的形状也会不同。 - TeddyG

你需要提供更具体的关于曲线描述的信息。它是由控制点定义的吗？有多少个控制点等等。 - agentp

一个查找表（LUT）总是可以解决你的问题，因为它与你的曲线相结合。如果你随机生成曲线，那么你就会随之生成LUT。如果你有一个更精确的曲线描述（比如样条曲线，采用哪种插值函数？），请更新你的帖子，我（和其他人）也许可以在我的回答中提供更具体的建议。 - Mike 'Pomax' Kamermans