数学之美--不规则多边形重叠计算(2)

数学之美--不规则多边形重叠计算

补充

我的上一篇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的值,重新方程,上文只是为了方便才说"平行射线"