找到一条线接触凸包的第一个点

Question

首先，我使用 convexHull Matlab 函数绘制了给定点的凸包：

x = [4*rand(10,1)-2];
y = [rand(10,1)+5];
DT = delaunayTriangulation(x,y);
C = convexHull(DT);
plot(DT.Points(:,1),DT.Points(:,2),'.','MarkerSize',10)
hold on
plot(DT.Points(C,1),DT.Points(C,2),'r')

这个凸包只是一个例子，它可以是任何其他的凸包。我们假设凸包在抛物线内 y=x^2.

然后我想在凸包上找到第一个接触线 y=[(a^2+1)/a]x-1 的点，当我们从 a=1 开始时，它可以一直到 a=+\infty 如果不接触凸包（当凸包在 LHS 上）。

如何实现？我的最终目标是找到图上的a

Answer 1

对多边形的每个角 (x_i, y_i) 求解 a_i 的二次方程。

y_i*a_i = (a_i^2 + 1)*x_i - 1

将点坐标代入线方程即可得到方程。接下来，丢弃与您无关的解决方案 (a<1)。完成后，按 a 对解决方案进行排序。如果您还需要相应顶点的索引，Matlab 中的 sort 函数会为您提供索引数组作为附加输出。然后你可以画线。

作为极端情况，直线可能会碰到两个顶点。如果您只需要 a，这不是问题。如果你想要顶点id，随便丢弃一个，或者使用一些额外的规则。

找到一条线接触凸包的第一个点

Find the first point where a line touches a convex hull

matlab

line

convex-hull