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

雪山飞狐(lzh) · 发表于 2016-10-12 12:57:00

1.从该凹形任一点出发左右搜索凸点 2.连接左右凸点判断与凹形是否相交相交就回退一个点 3.如果凸点少于3个当前点下移 4.否则连接左右凸点将此凸边形剥离继续第一步

雪山飞狐(lzh) · 发表于 2016-10-12 13:00:47

2应该是判断线段是否在凹形内

aimisiyou · 发表于 2016-10-12 13:17:04

csharp 发表于 2016-10-11 16:49

你这种说法不正确。

Lisphk · 发表于 2016-10-12 13:38:24

aimisiyou 发表于 2016-10-12 13:17

这是个很复杂的问题吗？

aimisiyou · 发表于 2016-10-12 13:47:44

Lisphk 发表于 2016-10-12 13:38

不是很复杂，用递归的思路就能很好的解决。

Lisphk · 发表于 2016-10-12 14:12:07

aimisiyou 发表于 2016-10-12 13:47

给大家写个代码啊，谢谢。

aimisiyou · 发表于 2016-10-12 21:49:58

怎么不能上传图片？

newer · 发表于 2016-10-12 22:04:58

aimisiyou 发表于 2016-10-12 21:49

可以啊

cable2004 · 发表于 2016-10-13 00:15:14

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

aimisiyou · 发表于 2016-10-13 14:24:30

此问题即为如何将一个复杂多边形切割成多个小凸多边形，切割之后的每个小凸多边形至少有一段、至多有两段“割线”来作为它的边，且小凸多边形的数目最少？

aimisiyou · 发表于 2016-10-13 15:00:10

以下算法的分割结果不是最优的分割，即生成的凸多边形数目不是最少。
算法可表述为：
1、对多边形的一个顶点Vi，平移多边形使Vi位于坐标原点；
2、绕原点旋转多边形，使Vi+1落在X轴的正半轴上；
3、检查第i+2个顶点y坐标分量的符号。如果符号为正或零，那么多边形在该边处是凸的；反之，则是凹的。分割多边形。
4、分割多边形的时候，检查第i+2个顶点后面的各顶点的y坐标分量，直至发现一个顶点的y坐标分量大于或等于零。这个顶点在x轴的上方，或恰好落在x轴上，记为Vi+j。那么，分割下来的多边形为Vi+1Vi+2...Vi+jVi，剩下的多边形为ViVi+1Vi+j...Vi。
5、多分割的多边形再次使用该算法，直到它们都为凸多边形。

marting · 发表于 2016-10-13 15:05:09

aimisiyou 发表于 2016-10-13 15:00

这个算法已经被网友讨论过证明是错误的了，见： http://blog.sina.com.cn/s/blog_48ff6e140100oqrh.html

账号		自动登录	找回密码
密码			立即注册

[研讨] 凹多边形转换成凸多边形的问题