如何计算一条直线与任意形状的交点？

Question

有没有一种方法可以几何计算出线条和任意图形路径的交点？我知道路径中所有的线段和曲线的位置，如果有帮助的话，我正在使用HTML5画布元素。基本上，我可以访问所有画布绘制命令及其参数。例如，如果API使用lineTo，然后是moveTo，然后是arc，我拥有所有这些信息。每次对API的调用都存储在一个数组中。我已经有了路径定义，我只想弄清楚直线与路径相交的位置。下面是一个示例图像，显示我需要找到的点。

感谢任何帮助！如果可能的话，我更愿意以几何方式而不是基于像素来完成。

- devongovett

Answer 1

您可能想看一下Kevin Lindsey的Javascript几何库——它包含了您寻找的所有相交算法：http://www.kevlindev.com/geometry/index.htm

- Quasimondo

Answer 2

如果不知道你的图形路径是如何定义的，就无法用具体的算法回答你的问题。在这本算法书中有一种解决直线段问题的方法。

- user181548

---

基本上，我可以访问所有画布绘图命令及其参数。例如，如果使用lineTo调用API，然后是moveTo，再然后是arc，我都有这些信息。每次对API的调用都存储在一个数组中。我已经有路径定义，现在只想弄清楚线条与路径相交的位置。 - devongovett

@devongovett：我的建议是您将该信息添加到问题中。 - Alceu Costa

你的问题是找到由JavaScript画布绘图命令定义的直线与一条直线的交点。 - user181548

Answer 3

如果你有每个方程式，那么理论上你可以做到。实际上并不是那么容易（特别是在一般情况下）。 此讨论 对相交线和贝塞尔曲线有一些很好的建议。

- Seth

Answer 4

你想要求解一条直线和一个“样条”x(t)，y(t)的交点，其中x(t)和y(t)的最高次数应该都不超过4次多项式。你需要解方程，但并不需要知道所有的参数。如果解超出了范围（线段和样条段都有起点和终点）- 就将其丢弃。相关问题：

样条和直线的交点

- Hamish Grubijan