Readygo技术搜索引擎 网络搜索 efish 2008-1-17 9:39:43

在二维平面中，如何判断两个任意多边型是否有重叠？

楼主hmaik（）2001-10-29 10:09:16 在 专题开发/技术/项目 / 数据结构与算法 提问

问题点数：20、回复次数：19Top

1 楼tarzan710（）回复于 2001-10-29 10:36:15 得分 5

前面有一篇文章是讨论   如何判断一点是否在一个三角形内。有兄弟已经将其扩展成为   如何判断一点是否在一个多边形内。在此基础上，要判断两个任意多边形是否有重叠，就变得简单多了：  
  只要判断其中某个多边形是否至少有一个顶点在另一个多边形内(包括在边线上)就可以了。   Top

2 楼starfish（海星）回复于 2001-10-29 10:43:06 得分 5

仅仅判断多边形是否重叠很容易,楼上说的方法就可以了;但是如果要判断一个多边形是否包含另一个多边形就比较麻烦一点，有很多特殊情况要考虑。其实即使对于判断线段是否在多边形内这个简单的问题，其麻烦程度也比判断点在多边形内大得多，因为有很多特殊情况要予以考虑Top

3 楼tarzan710（）回复于 2001-10-29 11:36:27 得分 0

上面还不是很具体，有一点点错误。  
  如果有一点在边线上，还须寻找是否还有一个点在别一条边线上或多边形内，如果存在，则重叠；  
  如果有一点刚好在另一个顶点上，须寻找是否还有一点在不连接此顶点的边上或多边形内，如果存在，则重叠。Top

4 楼tarzan710（）回复于 2001-10-29 11:42:29 得分 0

要判断包含，我觉得就看是不是某个多边形的所有顶点都在另一个多边形内就可以了吧。有什么特殊情况要考虑呢？请教海星。Top

5 楼xlybw（犀利亚布瓦）回复于 2001-10-29 11:46:16 得分 0

tarzan710(陶然)  
   
  凹多边形Top

6 楼tarzan710（）回复于 2001-10-29 12:01:40 得分 0

有道理Top

7 楼NewViewer（）回复于 2001-10-29 12:09:46 得分 0

我觉得原始问题很简单啊  
  不管是什么样的多变形，如果是重叠的话（包括包含情形），则总有一个多边形至少一点在  
  另一个多变形种  
  Top

8 楼tarzan710（）回复于 2001-10-29 12:10:11 得分 0

如果有考虑凹多边形的话，我上面的两个“如果”也就不再成立了。这样判断是否重叠也变得复杂了。Top

9 楼tarzan710（）回复于 2001-10-29 12:23:20 得分 0

NewViewer()　  
   
  你说得很对，把你的话反过来说呢？你所叙述的命题只是一个充分条件，并不是必要条件，也就不是一个充要命题。Top

10 楼gcsoft（gcsoft）回复于 2001-10-29 15:48:30 得分 0

呵呵，如果考虑多边形可以自我交叉的话，这个问题就不存在了。  
  因为这个多边形是没有内外部之分的Top

11 楼hmaik（）回复于 2001-10-29 16:39:41 得分 0

哈,我都没想到有这么多情况.  
  提这问题主要是要解决在2D游戏中的精灵碰撞判断.一般的精确判断方法是使用像数色彩判断.  
  另外提个题中题:  
  在<图形/游戏/多媒体>中有"谁有好的边界算法？"    
  想得到一幅图片的边界（除去背景）  
  进行水平和垂直方向两次扫描可以得到准确的边界图形,但其实只需要该多边型的顶点数据就可以.  
  如何从中取出顶点数据呢?如gcsoft所提的还要去处内包的部分.  
  Top

12 楼mayb（午谷逢灯）回复于 2001-10-29 16:53:34 得分 10

有三种情况讨论：  
  两个多边形边界有相交，即有重叠；  
  一个多边形有顶点在另一个的边界上；  
  两个多边形边界没有相交，再判断有没有顶点在另一个多边形内，两个要相互判断。Top

13 楼hmaik（）回复于 2001-10-30 15:39:34 得分 0

是否有现成的算法或在现有的算法上扩展来实现？  
  关于第二个问题有什么好的思路吗？Top

14 楼vampirelord（）回复于 2001-10-30 15:46:45 得分 0

判断顶点可能面临凹多边形有麻烦。  
  那么判断边是否有相交应该可以吧。Top

15 楼ruixp（锐剑）回复于 2001-10-30 20:24:55 得分 0

只要想想三个同心的不同半径的圆Top

16 楼gcsoft（gcsoft）回复于 2001-10-31 09:38:46 得分 0

纠正一个错误，多边形的边界应该是一条封闭的折线，而不是几条。因此多边形是不会存在内包的问题，俺所说的是自我交叉，是类似“8”的图形。  
   
  如果不考虑自我交叉，俺认为可以使用格点法得到近似解。理论上如果采用的格点密度足够大，结果是正确的。Top

17 楼truestorm（以眼杀人以德服人）回复于 2001-10-31 11:11:07 得分 0

好象只要线段没有相交就不重叠。  
  如果有相交就重叠。Top

18 楼nilm（）回复于 2001-10-31 11:52:13 得分 0

这里好热闹，弟兄们帮我   看看：  
  http://www.csdn.net/expert/topic/347/347758.shtmTop

19 楼starfish（海星）回复于 2001-10-31 18:19:23 得分 0

这个问题我早就作过了，只要考虑一些特殊情况就可以判断两个多边形是否相互包含（相交的情况很简单，不用说了吧）。  
  可惜这里没办法贴出图来给大家看：（  
   
   
  Top