数学之美--不规则多边形重叠计算
补充
我的上一篇
blog
中忽略了一种关系
,
这种忽略也同样发生在我最初接手这个项目的时候
.
也就是效果
3:
一个图完全包含另外一个图
,
在这种情况下两个多边行是没有交点的
.
如下图所示
:
我很感谢
”
nile black”,”
恋花蝶
”
和其他朋友的回复
.
不过
,
他们的方案都存在一些问题
.
我同样也和他们一样的思路
.
(
回过头来看
,
这篇
blog
应该改名成
,
数学之美
--”
多边形是否重叠计算
”)
最初的想法
:
计算线段相交
,
在思考这种方法的同时我忽略掉了
”
效果三
”
这种可能
,
我当时认为虽然使用
”
线段相交
”
算法逐个比较的计算次数可能较大
,
但是我还是绝定采用
.
在我看来能够解决问题才是最重要的
.
但是我的希望破灭了
,
有人提醒了我
:
还有
”
效果三
”
的产生
.
我一下子突然发现最初的思路解决不了这种情况
.
一时之间
,
我尝试了很多思路
,
甚至想做图象使用比例尺后来计算
”
异或
”,
但是这种方法也不可行
.
如何办呢
?
如何办呢
?
如何办呢
?
如何解决包含这种情况呢
?
当时我开始拼命回忆自己初中
,
高中以及大学的数学知识
,
想看看
:
过去学习过的知识中是否有可以解决这一问题的情况
.
但是没有
!!!
Google
吧
,Google.
最后的结果是惊喜的
,
在我
Google
了大量的网页后
,
呵呵
,
我甚至去访问过小学的几何教学网站
.
解决方案
我来卖卖关子
:
最后解决多变形是否有重叠区域还是靠的计算线段相交
.
各位在看下去之前是否还给自己一些思考的机会呢
???
等不及了
?
我们继续
… …
很幸运
,
我
Google
出了一个理论
,
为了方便大家理解我把这个理论分割了一下
:
1.
理论一
:
如果多边形相交
(
包含
),
那么任意一个多边行至少有一个
”
顶点
”
在另一个多边形怀抱中
.
给一个简单而咸湿的比喻
:
男女
XXX,
一定有某样东西在对方体内
.
如下图所示
:
2.
理论二
:
从上图中
”
图
1”
的顶点向任意一边做平行射线
,
那么平行射线和多边形图
2
的至少有一个交点
(
由于是任意多变形
,
所以射线可能不只和一条边相交
),
如下图所示
:
3.
理论三
(
这个理论最关键
,
前面的都是废话
):
如果存在一条射线
L
和图
2
的线段交点个数为奇数
,
那么这两个图形必有重叠
.
对于理论
3,
我就不画图了
,
这里需要大家发挥自己的平面构思能力来思考这一问题
.
等大家想明白这个理论的时候或许会突然发觉
:
原来是这样
,
原来可以这样
,
原来这么简单我都没有注意到
.
(
需要提醒的是这个理论还是有一个瑕疵
,
不过这个瑕疵还是可以解决的
,
我就故意留下来给大家思考
)
如果你想通了以上理论的话
,
接下来就简单了
,
就是直线方程的计算机化了
.
但是千万不要高兴太早
:
你记得什么是直线方程吗
???
很汗颜的是
,
当时的我确实是忘记了什么是直线方程
:y=kx+b,
或者
ax+by+c=0.
如果你都还没有忘记
,
而且还知道如何求解直线方程的话
,
恭喜您
!
我打算把这篇
blog
就写到这里
,
我认为不必把整个算法代码贴在这里
.
大家如果有兴趣不妨自己动动手
.
再次感谢回复我上篇
blog
的朋友
!
附记:之所以用了"数学之美"这个词语,一方面是模仿Google's Blog;另外一方面在我看来:解决这个"多边形是否重叠"问题的最后思路确确实实给了我一种很奇妙的感觉"原来可以这样"
Sean.Pu 2006.08.17 补充:
感谢phoenixsh提醒了我,我确实又以点概面了,本文的理论一确实是有问题的,所以在目前我能提供的解决多边形重叠的问题的方法是:
1,线段相交计算;
2,射线和线段交点计算,至于射线和多变形顶点的交点问题很好解决:
1),由于是原始数据是地理数据,产生射线和多边形顶点相交的概率非常小,
2),如果出现上面说的情况下,在直线方程中变换K的值,重新方程,上文只是为了方便才说"平行射线"
扫一扫
4295
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
