二维凸包的两项技术问询：凸包边缘端点解析求解与边缘有效性数学证明

嗨，很高兴帮你解答关于二维凸包的这两个问题！作为刚接触凸包的新手，你的问题非常典型，咱们一步步拆解：

问题1：解析求解凸包边缘端点C、D #

首先要明确：你的曲线AB是由离散坐标点构成的，而凸包的顶点本身就是AB上的点（凸包是原始点集的最小凸包络，顶点必然来自原始点）。所以你不需要手动检查或者暴力比对所有点——其实MATLAB的convhull函数已经帮你筛选出了凸包的顶点索引。

高效方法：直接利用凸包输出 #

conv_hull_area返回的是原始X、Y数组中凸包顶点的索引。你可以通过X(conv_hull_area)和Y(conv_hull_area)获取所有凸包顶点的坐标，然后从中找到构成边缘CD的两个点（在你的例子里，C对应索引2，D对应索引82）。如果需要自动化识别这条特定边缘，可以利用支撑线的数学性质：

• 对于线段CD，所有AB上的点都必须位于CD的同一侧（或在线上）。我们可以用向量叉乘来验证这一点：
  设C=(x_c, y_c)，D=(x_d, y_d)，对于AB上任意点P=(x_p, y_p)，计算叉乘值：

  cross = (x_d - x_c) * (y_p - y_c) - (y_d - y_c) * (x_p - x_c)
  

  所有点的cross值符号必须一致（全≥0或全≤0），而C、D对应的cross值为0。

  基于这个性质，你可以从凸包的边缘列表中筛选出满足条件的线段，而不需要遍历所有点对，这比暴力比对高效得多。

问题2：证明线段CD是曲线AB的凸包边缘 #

要证明CD是凸包的边缘，需要满足两个核心数学条件，结合凸包的定义（包含所有点的最小凸集）：

1. 所有AB上的点都在CD的同一闭半平面内
   用刚才的叉乘方法验证：对AB上的每一个点P，计算上述叉乘值，确保所有值的符号一致（或为0）。这说明所有点都在CD的一侧或在线上，满足凸包的“包裹”要求。

2. C和D都是AB的极点（Extreme Points）
   极点的定义是：无法被AB上其他两个点的凸组合表示的点。换句话说，不存在AB上的点P、Q，使得C落在线段PQ内部，D同理。如果C或D不是极点，那它们就不可能是凸包的顶点，CD自然也不会是凸包的边缘。

满足这两个条件后，就可以证明CD是凸包的边缘——因为它是连接两个极点的线段，且所有点都在其一侧，符合凸包边缘的定义。

你提供的MATLAB生成代码 #

X = [-50 1:1:100]';

Y = [0;13.02;22.58;29.82;35.44;39.88;43.44;46.34;48.72;50.70;52.36;53.77;54.96;55.98;56.86;57.62;58.29;58.87;59.39;59.86;60.27;60.65;61;61.32;61.62;61.90;62.17;62.43;62.68;62.92;63.16;63.40;63.64;63.88;64.12;64.36;64.61;64.87;65.13;65.40;65.67;65.96;66.25;66.55;66.87;67.19;67.52;67.87;68.22;68.59;68.97;69.36;69.77;70.19;70.62;71.07;71.53;72.01;72.50;73;73.53;74.06;74.62;75.19;75.78;76.38;77;77.64;78.30;78.98;79.68;80.39;81.13;81.88;82.66;83.46;84.28;85.12;85.98;86.87;87.78;88.71;89.67;90.65;91.66;92.69;93.75;94.84;95.95;97.09;98.26;99.46;100.69;101.95;103.24;104.56;105.92;107.31;108.73;110.18;111.67];

conv_hull_area = convhull(X,Y);

plot(X,Y,'LineWidth',1.5);

hold on

plot(X(conv_hull_area),Y(conv_hull_area),'--','LineWidth',1.5)

plot([1 81],[13.02 88.71],'gX:','LineWidth',1)

hold off

xlabel('X');

ylabel('Y');

hleg=legend('Curve AB','Convex hull of AB','Line CD');

备注：内容来源于stack exchange，提问作者boiledbeans