线性规划-铸模制造

Terms

• 二维小平面(facet)
• 顶面(top face): 有且仅有一个小平面
• 普通面(ordinary facet)
• 半平面(): 在平面上位于某条直线左(或右)侧的部分
• 可铸造的(castable)
• 外法矢(outward normal)

Theories

4.1 沿某个方向\(\vec{d}\)通过一次平移, 多面体\(P\)能够从其铸模中抽取出来, 当且仅当相对于\(P\)的每一张普通面的外法矢, 移动方向\(\vec{d}\)v 与之所呈的角度都至少为 90度

由4.1 可推出: 若可以通过多次小幅度的平移将 p 抽取出, 则必然可以仅通过一次平移就将其抽取出来(向量的合成)

IntersectHalfPlanes(H)

Input: 由平面上 n 张半平面组成的一个集合 H

Output: 凸多边形区域 C

1. \(\)
2. \(\)
3. \(\)
4. \(\)
5. \(\)
6. \(\)