查找线段和凸多边形之间的交点

Question

我正在尝试在 MATLAB 中构建一个函数，您在其中输入一个 segment（由两个点定义）和一个 polygon（4 边）通过在数组上指示其顶点。

我有以下代码：

function intersection = intersectSegmentPolygon (s, p)
% Create a vector with X coords of vertices and same for Y coords.
xv = [p(1,1) p(2,1) p(3,1) p(4,1)];
yv = [p(1,2) p(2,2) p(3,2) p(4,2)];
% Read the segment
x = [s.A(1) s.B(1)];
y = [s.A(2) s.B(2)];
[in,on] = inpolygon(x,y,xv,yv);
% Return vectors containing the coords of the intersecting points
intersection = [x(on), y(on)];

我对获取位置 on 处的点（交叉点）很感兴趣，但是，显然该函数仅检查点 A 和 B（线段的初始坐标和最终坐标），什么我可以做些什么来检查 AB 段中包含的所有点吗？谢谢。

Answer 1

使用线段的参数方程，P = (1-t) A + t B，与0<=t<=1。

找到多边形边与线段支撑线的交点，用t表示交点的位置（暂时忽略t上的约束）。

您会发现 0 或 2 个交叉点，而不是更多，因此 t 的 0 或 2 个值形成一个区间。该区间与区间 [0,1] 的交集给出了解决方案，这是一个基本的一维问题。

查找线段和凸多边形之间的交点

Find intersection points between a segment and a convex polygon

matlab

intersection

computational-geometry