知识卡片

普通读书笔记卡 · 8093.f · 生成模型:未记录

凸包也可能退化为点或线段

理解等级:中级

凸集内任意两点的连线都在集合中;点集的凸包是包含所有这些点的最小凸集。对于不全共线的有限二维点集,其边界通常构成凸多边形。

如果所有点共线,凸包是线段;若所有点重合则是一个点。原文把凸包一律称多边形是常见直观简化,实际接口还需约定空集、重复点及共线边界点是否输出。03107展示凸与凹多边形,凹多边形存在两点连线离开形状的情况。

324/03126以去掉凹角解释凸性的直观图,但凸包定义本身要求最小凸集;若凹角点本身属于输入,直接用一条边替换可能把该点排除,不能无条件把图中论证当作严格证明。退化点集也未必形成多边形。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      最小凸多边形。如果一个多边形内任意两点之间的连线完全包含在该多边形内,则称这个多边形是凸多边形(见图17-3a);否则,多边形就是凹的(见图17-3b)。要画出一个点集的凸包,可把它假想成一块板子上的钉子。如果用细线将最外层的钉子逐个连起来,那么细线所围成的形状就是凸包。 图 17-3 a)凸多边形

    • · 查看原书依据

      最小多边形称为凸包。这个名字暗示了这个多边形一定是凸多边形。为什么会这样? 答:回忆一下凸多边形的定义:如果多边形中任意两点间的连线完全在多边形的内部,就说多边形是凸的;否则,多边形就是凹的。要理解为什么凸包一定是凸多边形,不妨考虑一下凹多边形围绕着点集的情形。对于由任意顺序的3个点P1、P2和P3

    参考来源

    - 位置:《算法精解:C语言描述》第17章《凸包简介》(spine1425;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1391.html;u313-ch17-007)。 - 结论依据:313全文与03107两幅凸凹示意图实读;退化情况为定义直接推论。 - 原始内容:最小凸多边形。如果一个多边形内任意两点之间的连线完全包含在该多边形内,则称这个多边形是凸多边形(见图17-3a);否则,多边形就是凹的(见图17-3b)。要画出一个点集的凸包,可把它假想成一块板子上的钉子。如果用细线将最外层的钉子逐个连起来,那么细线所围成的形状就是凸包。 图 17-3 a)凸多边形 - 位置:《算法精解:C语言描述》第17章《问与答》(spine1435;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1401.html;u324-ch17-007)。 - 结论依据:324/03126以去掉凹角解释凸性的直观图,但凸包定义本身要求最小凸集;若凹角点本身属于输入,直接用一条边替换可能把该点排除,不能无条件把图中论证当作严格证明。退化点集也未必形成多边形。 - 原始内容:最小多边形称为凸包。这个名字暗示了这个多边形一定是凸多边形。为什么会这样? 答:回忆一下凸多边形的定义:如果多边形中任意两点间的连线完全在多边形的内部,就说多边形是凸的;否则,多边形就是凹的。要理解为什么凸包一定是凸多边形,不妨考虑一下凹多边形围绕着点集的情形。对于由任意顺序的3个点P1、P2和P3