共点、长度恒等式与夹逼

VectorPaint凸包点集图:七个输入点只需四个极点围边

用四角、两内点与一边界中点区别输入集合和凸包顶点,再加外点得到五边凸包。

把一组散点圈在最小凸集合里,不要求边界折线依次访问每个输入点。内部点仍属于凸包,但不是极点;落在一条边中间的输入点也不必成为新的转角。先明确本课只输出极点顶点序列,再用半平面与线段定义检查,而不是随手画一圈橡皮筋形状就判对。

七点先按坐标分别落图

取A=(0,0)、B=(6,0)、C=(6,4)、D=(0,4)、E=(2,1)、F=(4,3)、G=(3,0)。建议1600×1200像素,映射u=300+140x、v=900−140y,给右侧加点控制预留空间。七点用等大小标记,先不连接,点、边界、说明和控制各分组并存原稿。E与F不是随机噪声,也不因看起来靠里就从原始清单删除;G与AB同线只是位置条件,不是重复输入或同一个点。

最小凸集合不同于最短巡游线

凸的含义是集合内任意两点之间整条线段仍在集合内;凸包是包含全部输入的最小凸集合。这里“最小”指集合包含关系,不是让一根路径最短地走过七点。先画ABCD闭合边界并浅填内部,E、F在内部,G在底边上,七点都被包含。只画四条线而不说明内部时易误成轮廓本身是全部集合,所以图例写填充区域与边界一起表示凸包。普通路径填色不执行凸性分析。

四角必须包含而内部点不添角

四个角都在原输入中,任何包含输入的凸集合也必须包含这四角间的全部凸组合,即整个矩形;矩形本身又包含其余三点,所以它正是凸包。极点输出按A、B、C、D逆时针,再闭回A,闭合重复A不另计第五顶点。E、F只作为内部点保留标记,不拖到边上制造多边形。G处于AB之间,不改变直边方向,因此本课极点序列不列G;这不等于说G不在凸包中。 G=(A+B)/2直接说明它能由两个不同输入的非平凡凸组合得到,所以不是极点。内部E也可写成A的一半、B的四分之一、C的十二分之一、D的六分之一相加;四权非负且和一,横纵加权后确得(2,1)。先在旁账逐项核权重,不把四个权直接当屏幕坐标。这个构造同时说明内部点被四角包含,不需要把它提升为第五个边界顶点;存在一个组合即可说明包含,不要求这是唯一分解。

用有向边左侧核全部点

对逆时针边AB、BC、CD、DA,分别要求所有点y≥0、x≤6、y≤4、x≥0,七点都满足,边界允许等号。也可算叉积cross(U,V,P)=(Vx−Ux)(Py−Uy)−(Vy−Uy)(Px−Ux),结果非负为左侧或共线。AB对G为零,对E为六;BC对F为八,先独立复算再贴标签。若用了屏幕向下坐标,符号会反向,不能把数学逆时针原样套到屏幕行列数。

A=(0,0); B=(6,0); C=(6,4); D=(0,4)
E=(2,1); F=(4,3); G=(3,0)
extreme hull vertices CCW: A,B,C,D
G on boundary, not an extreme vertex; E,F inside
cross(A,B,G)=0; cross(A,B,E)=6; cross(B,C,F)=8
add H=(8,2): hull A,B,H,C,D; area 24+4=28
wrong tour turn cross(C,F,D)=-6

加外点后边界必须重新构造

另存增加H=(8,2)的版本,H在旧边BC右侧,违反x≤6,旧矩形不再包含全部点。新极点按A、B、H、C、D闭合,原BC成为内部辅助线应淡化,不留作凸包外边。面积可独立核旧矩形24,新增加以BC为底、高二的三角形面积四,总28,但面积不是本课定义依据。控制只加H,不挪E、F或G;移动旧边界标签却没改边,不能算完成更新。

经过全部点的凹折线作为错例

检查副本若按A、G、B、C、F、D、E再回A走过全部点,会向内凹,不是凸包。仅看C、F、D三点的转向,向量CF=(−2,−1)、FD=(−4,1),叉积负六,与逆时针凸边界的非负转向冲突。经过所有输入并闭合仍不充分,不能把此线当另一种同样正确的凸包。另说明若输入全共线,凸包可退化成线段;本例四角不共线,所以使用多边形顶点说法有前提。

按遗漏点共线点和凹角排障

若称七点都必须是顶点,先分输入集合、边界点与极点;若G被删后说不在集合,恢复它的边界标记;若加H仍选四角,查旧右半平面是否漏了外点。凹线错误从负转向所在三点修,不靠把填充透明来藏凹口。保留原图与控制图,逐边核所有点都在正确半平面。手绘接近边界不等于精确在边上,保留原坐标;移动节点后路径端点不会被假定自动重算凸包。

重开同时核包含与最小凸性

保存原生稿和七点、八点清单,导出SVG或PDF并另开PNG。适应窗口核四角版与加H五角版,放大看G在AB上却没有伪造转角,E、F仍可见。重开编辑稿隐藏结论,用四个半平面恢复旧包,再核新边BH、HC。交付极点约定、原始输入、凹错例及退化条件,未做输出检查记待办。引用CGAL仅核定义,不声称VectorPaint内置该库、自动凸包算法或测绘边界认证。

相关教程与资料

VectorPaint 散点图:让每个点同时对应两项数值、VectorPaint 凹五边形鞋带账:保留点序、闭边与十八的面积。

方法来源:CGAL:二维凸包与极点定义。官方文档只用于凸集、凸包与极点术语,七点与加H控制均原创;本课不用其代码,也不将库能力归给绘图App。

版本与操作范围:2026年11月19日核VectorPaint官方商店与Apple公开查询,公开1.0.8,最低iOS / iPadOS 17.0。使用已公开的形状、钢笔、贝塞尔节点、网格辅助线、对齐、图层分组、文字和保存输出手工绘图;入口按安装版本实际可见为准。计算、定义与复算在应用外准备,不推断内置公式、统计或图论求解能力。原生稿保留可编辑结构,SVG、PDF、PNG各按需要阅读检查,含导入位图的SVG或PDF不自动成为全矢量。画布与样本为原创教学设定,未执行真机或实物测量,未做的操作明确待做。