[待解决] [+500威望+500财富+提升为荣誉会员] 凸多边形(polygon) [复制链接]

........

有趣!

建议解题者先找出数学方法来解决....

先算两个，合并成一个
算的时候，一个为基础，一个将它的线段分成“里面”，“外面”（出现一个交点，这条线段从
“里面”到“外面”或从“外面”变成了“里面”）
于是，交点就求出来了，然后，再找一个东西，在合并
直到只有一个东西了


是不是啊
！！
；）

楼上的，你测过我的代码了吗？答案都正确吗？
思想大概就是这样的，代码有些地方重复了。

可不可以创建一个二维表，然后模拟这一块区域
每输入一组图形顶点的位置把此图形覆盖的点所对应的数组元素加一
最后看看那些元素是n，其个数就是面积
（一家之言仅供参考）

I have no idea！

从06年到现在的问题，都快成精了吧^_^
刚找一解决方案到此，见此问题，遂注册帐号回答
问题好像不是很难吧，写个大致思路，还有很多工作要做，就不编码了
1. 先合并两个polygon得到一个新的polygon，从相交点得到新polygon的各顶点坐标(当然，还有一种可能是其中一个polygon的某些顶点包含在另一polygon之内，别丢了)
2. 然后将新产生的polygon与第三个polygon合并得到各顶点坐标，依次类推
3. 最后得到一个x边的polygon，N个凸多边形Combine后仍得到一个凸多边形，所以结果还是一个凸多边形
4. 剩下的任务就是算这个polygon的面积了，这个就更简单了吧，既然是凸多边形，那就任取一个顶点，从选中的顶点向所有与其不相临的顶点作连线得到x-2个三角形，求三角形的面积就没什么好讲了吧，而这x-2个三角形的面积总和就是要求的polygon的面积了
没时间细想，也可能是我想得太简单了，欢迎继续探讨，不过回复我最好用E-Mail或者QQ之类的

蒙特卡洛方法

引用第63楼sky_huang于2008-03-02 16:28发表的  :
从06年到现在的问题，都快成精了吧^_^
刚找一解决方案到此，见此问题，遂注册帐号回答
问题好像不是很难吧，写个大致思路，还有很多工作要做，就不编码了
1. 先合并两个polygon得到一个新的polygon，从相交点得到新polygon的各顶点坐标(当然，还有一种可能是其中一个polygon的某些顶点包含在另一polygon之内，别丢了)
2. 然后将新产生的polygon与第三个polygon合并得到各顶点坐标，依次类推
.......

合并两个polygon时只用判断一个polygon的顶点是不是在另一个的内部（用叉积判这个顶点是否在另一个polygon所有边的同一侧）。假设两个polygon的编号是1、2
对于1的每一条边，如果它的一个顶点在2内（或上），一个在2外，那么就求出它和2的交点，如果都在2外或都在2内，就直接忽略。
但是这样也会存在较大的浮点误差，并不好做