凹多边形转换成凸多边形的问题

Lisphk

论坛的高手们，凹多边形转成凸多边形，程序代码怎么写？ 是否有很多种解？

/db_自贡黄明儒_

记得高飞大师发了一个捆扎法，凹点肯定就捆扎不到了。
转成凸，肯定有无穷解了。如果凹点刚好位捆扎线上（或者说凹点全部删除），这样就只有一个解了。

Lisphk

/db_自贡黄明儒_ 发表于 2016-10-11 16:23

黄总，能不能写个代码，造福下后辈

/db_自贡黄明儒_

不知道你要什么样的，再说这段时间忙。说一下我的思路，
1 求得多边形各顶点
2用高飞大师的凸包扫描（这个N版也发过），求得各凸点。
3 删除多边形的点（不是凸点的全部删除）

csharp

凹点之间按顺序连接即可

Lisphk

/db_自贡黄明儒_ 发表于 2016-10-11 16:42

把不是凸点的删除了，那还能生成里面那些凸多边形吗？

/db_自贡黄明儒_

未验证
(defun C:w1 ()
  (setq e (car (entsel "\n多段线")))
  (setq en (entget e))
  (setq pts (VL-REMOVE-IF-NOT '(lambda (x) (= (car x) 10)) en))
  (setq pts (mapcar 'cdr pts))
  (setq ptsT (Graham-scan pts))                                    ;凸点
  (setq p (VL-REMOVE-IF '(lambda (x) (member x ptsT)) pts))
  (cond (p (setq en (VL-REMOVE-IF '(lambda (x) (cdr x en)) p))))
  (entmod en)
)

Lisphk

/db_自贡黄明儒_ 发表于 2016-10-11 17:01

黄总，你这个是把一个凹多边形，变成一个凸多边形吧？ 我想是得到分开的多个子凸多边形（他们组合成凹多边形）

qqqincccken

谢谢提供,学习一下!!

iLisp

1:向量法：按照逆时钟的方向计算边向量的叉积结果，并且记录叉积结果z分量的符号。 如果z分量变为负值，则多边形为凹多边形，可以沿叉积向量对中第一条边的延长线将 多边形分解开。对新得到的两个多边形重复前面步骤，最后把凹多边形分成若干个凸 多边形。 2：旋转法：绕多边形逆时钟前进，将多边形顶点Vk平移到坐标原点。然后顺时针旋转， 使下一个顶点Vk+1在x轴上。 如果下下一个顶点Vk+2在x轴下方，则多边形为凹多边形，沿x轴将多边形分割为两个新多边形，对这两个新的多边形重复进行凹多边形测试。 否则继续旋转x轴上的顶点，并测试顶点的y值是否为负。



具体算法如下：
0) 初始化ma = pi
1）将凹多边形放入凹多边形队列
2）从队首取出一个多边形G
3）遍历G每个顶点，找出其中一个凹顶点p。
4）过p和另一个顶点q作这个多边形的一条弦（我想一定至少可以找到一个q能做一条弦，但是没有证明过），这条弦将原先的凹顶角分割成两个角a,b
5）记 angle = min(a, b)
6）如果弦的另一端点q也是凹顶点，且angle < pi/2，则令angle = angle - pi/2，（这是为了将凹多边形尽可能少地分割成凸多边形块）
7）若ma > angle ，则令ma = angle，记分割弦 cd = line_segment(p,q)
8）回到4）直到遍历过所有的顶点
9）用分割弦分割多边形，判断分割出的两个子多边形是否为凹多边形，若是，放入队列
10）回到2）直到队列为空

算法的时间复杂度为O(n^2)

aimisiyou

Lisphk 发表于 2016-10-11 17:12

你要的子凸多边形的个数是最少，还是最多？比如正六边形本身就是一个凸多边形，也可以分成四个三角形。你要得到哪种结果？

longer1000

支持楼主大人了

newer

aimisiyou 发表于 2016-10-12 09:25

如果有相对最优的结果，就要这个，比如多边形数目最少。

cable2004

正需要，支持楼主大人了！

Lisphk

aimisiyou 发表于 2016-10-12 09:25

谢谢楼上各位，我想，主要是判断是否是凹多边形，如果是，把凹多边形分解为最少的凸多边形组合。当然您说的把已经是凸多边形的在细分，另外写个代码最好了。