Matlab环境下求解可变直线与凸包首个接触点及对应参数a的方法

首先我使用Matlab的convexHull函数绘制了给定点集对应的凸包，实现代码如下：

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²的内部区域。

现在需要实现以下需求：参数a从1开始逐步增大，若凸包始终位于直线左侧则a可增大至+∞，找到该过程中直线y=[(a²+1)/a]x-1与凸包首次接触的接触点，最终目标是得到首次接触时对应的参数a值。

对应场景示意图如下：

核心推导 #

首先把目标直线整理为隐式形式：
(a + 1/a)x - y - 1 = 0
凸包位于直线左侧的判定规则为：凸包所有点代入左侧表达式计算结果均小于0。首次接触的临界点就是刚好存在至少一个凸包顶点代入后结果等于0，其余点计算结果仍小于0。

对凸包上每个顶点(x_i, y_i)，代入等式求解对应的参数a，可以整理出关于a的二次方程：
x_i * a² - (y_i + 1) * a + x_i = 0
求解该方程后筛选出满足a ≥ 1的实根，所有顶点对应解中最小的a就是首次接触的参数值，对应的顶点就是接触点。

Matlab实现代码 #

% 从你已生成的凸包结构中提取所有顶点，格式为N行2列，每行对应(x,y)
pts = DT.Points(C,:);
valid_a = [];
contact_pts = [];

for i = 1:size(pts,1)
    x_i = pts(i,1);
    y_i = pts(i,2);
    % 构造二次方程系数 A*a² + B*a + C = 0
    A = x_i;
    B = -(y_i + 1);
    C_coeff = x_i;
    % 计算判别式
    delta = B^2 - 4*A*C_coeff;
    if delta < 0
        continue % 该顶点不会和直线产生交点，直接跳过
    end
    a1 = (-B + sqrt(delta))/(2*A);
    a2 = (-B - sqrt(delta))/(2*A);
    % 筛选出大于等于1的实根作为候选值
    candidate_a = [a1, a2];
    candidate_a = candidate_a(candidate_a >= 1 & isreal(candidate_a));
    if ~isempty(candidate_a)
        valid_a = [valid_a, candidate_a];
        contact_pts = [contact_pts; repmat(pts(i,:), length(candidate_a),1)];
    end
end

% 输出结果
if ~isempty(valid_a)
    [min_a, idx] = min(valid_a);
    contact_point = contact_pts(idx,:);
    fprintf('首次接触时a=%.4f，接触点坐标为(%.4f, %.4f)\n', min_a, contact_point(1), contact_point(2));
else
    fprintf('凸包始终位于直线左侧，a可增大至无穷大\n');
end

补充说明 #

如果出现多个顶点对应相同的最小a值，说明首次接触时直线同时碰到多个凸包顶点，此时接触点为这些顶点构成的整段线段。

内容的提问来源于stack exchange，提问作者Lee