10 个解决方案
#1
我想了一个办法,
可以先考虑两个三角形的相交判别方法,再将多边形分割成多个三角形进行判断
考虑三角形ABC与DEF
1)D,E,F的坐标代入AB的直线方程,与C的坐标代入AB的直接方程异号,即D,E,F与C点在AB直线两侧
2)D,E,F的坐标代入AC的直线方程,与B的坐标代入AC的直接方程异号,即D,E,F与B点在AC直线两侧
3)D,E,F的坐标代入BC的直线方程,与A的坐标代入BC的直接方程异号,即D,E,F与A点在BC直线两侧
满足1),2),3)任意一条即可判定两个三角形不相交。
对两个任意多边形分割成两个三角形集合,判断两个集合中的三角形有没有相交就可判断两个多边形有没有相交。
当然还需要进一步考虑怎样将坐标有效地组合,得到所需要的一系列三角形的坐标。
可以先考虑两个三角形的相交判别方法,再将多边形分割成多个三角形进行判断
考虑三角形ABC与DEF
1)D,E,F的坐标代入AB的直线方程,与C的坐标代入AB的直接方程异号,即D,E,F与C点在AB直线两侧
2)D,E,F的坐标代入AC的直线方程,与B的坐标代入AC的直接方程异号,即D,E,F与B点在AC直线两侧
3)D,E,F的坐标代入BC的直线方程,与A的坐标代入BC的直接方程异号,即D,E,F与A点在BC直线两侧
满足1),2),3)任意一条即可判定两个三角形不相交。
对两个任意多边形分割成两个三角形集合,判断两个集合中的三角形有没有相交就可判断两个多边形有没有相交。
当然还需要进一步考虑怎样将坐标有效地组合,得到所需要的一系列三角形的坐标。
#2
多边形方程式相等? 有解和无解^_^
#3
把2组坐标 分别描述出他们的直线来 然后判断直线是否相交 ^_^
#4
不知道 楼主是怎么根据坐标来判断多边形的 如果能够顺利画出其中一个多边形来 只需要判断另外一个多边形 的点 是否有在它各个线段的2侧 如果有那就再判断 那2个点是否组成另外多边形的边
#5
何为相交??
能准确定义一下吗?
能准确定义一下吗?
#6
多边形相交实际上就是说有两条线段相交,且这两条直线分属于两个多边形,按照这个思路可以得出只要确认线段相交就行。
麻烦一些可以这样确认直线相交:
设A,B两个多边形
再设(x1,y1),(x2,y2)为A上两个相邻点,(a,b),(c,d)为B上两个相邻点
判断:
((a-x1)*(y1-y2)-(b-y1)*(x1-x2))*((a-x1)*(y1-y2)-(b-y1)*(x1-x2))
和((c-x1)*(y1-y2)-(d-y1)*(x1-x2))*((d-x1)*(y1-y2)-(b-y1)*(x1-x2))
如果至少有一组两个都小于0,则相交
如果都没有小于0的,但是至少有一组两个有至少其一等于0,则相邻
其余情况则是不相邻
麻烦一些可以这样确认直线相交:
设A,B两个多边形
再设(x1,y1),(x2,y2)为A上两个相邻点,(a,b),(c,d)为B上两个相邻点
判断:
((a-x1)*(y1-y2)-(b-y1)*(x1-x2))*((a-x1)*(y1-y2)-(b-y1)*(x1-x2))
和((c-x1)*(y1-y2)-(d-y1)*(x1-x2))*((d-x1)*(y1-y2)-(b-y1)*(x1-x2))
如果至少有一组两个都小于0,则相交
如果都没有小于0的,但是至少有一组两个有至少其一等于0,则相邻
其余情况则是不相邻
#7
对了还有一种情况是其中一个多边形的边横跨在另一个多边形内;
这种情况可在第二种假设中细分:当判断出有一组边时,分别取出边和对应的另一个多边形其余边循环比较,如果仍有“都没有小于0的,但是至少有一组两个有至少其一等于0”,则为相交
------------
这样应该比较完整了吧
这种情况可在第二种假设中细分:当判断出有一组边时,分别取出边和对应的另一个多边形其余边循环比较,如果仍有“都没有小于0的,但是至少有一组两个有至少其一等于0”,则为相交
------------
这样应该比较完整了吧
#8
按照你的思路只用建立两个链表,用以上的方法可以实现
#9
楼主,
可以使用 基本图形算法中的 扫描线方法
可以使用 基本图形算法中的 扫描线方法
#10
从多边形 的上顶点开始扫描,
直到 多边形的 下顶点,
如果在某个扫描位置 扫描线 进入一个多边形区域,
在没有退出该多边形时候,
又进入了第二个多边形,
那么两个多边形就是相交的 ....
直到 多边形的 下顶点,
如果在某个扫描位置 扫描线 进入一个多边形区域,
在没有退出该多边形时候,
又进入了第二个多边形,
那么两个多边形就是相交的 ....
#1
我想了一个办法,
可以先考虑两个三角形的相交判别方法,再将多边形分割成多个三角形进行判断
考虑三角形ABC与DEF
1)D,E,F的坐标代入AB的直线方程,与C的坐标代入AB的直接方程异号,即D,E,F与C点在AB直线两侧
2)D,E,F的坐标代入AC的直线方程,与B的坐标代入AC的直接方程异号,即D,E,F与B点在AC直线两侧
3)D,E,F的坐标代入BC的直线方程,与A的坐标代入BC的直接方程异号,即D,E,F与A点在BC直线两侧
满足1),2),3)任意一条即可判定两个三角形不相交。
对两个任意多边形分割成两个三角形集合,判断两个集合中的三角形有没有相交就可判断两个多边形有没有相交。
当然还需要进一步考虑怎样将坐标有效地组合,得到所需要的一系列三角形的坐标。
可以先考虑两个三角形的相交判别方法,再将多边形分割成多个三角形进行判断
考虑三角形ABC与DEF
1)D,E,F的坐标代入AB的直线方程,与C的坐标代入AB的直接方程异号,即D,E,F与C点在AB直线两侧
2)D,E,F的坐标代入AC的直线方程,与B的坐标代入AC的直接方程异号,即D,E,F与B点在AC直线两侧
3)D,E,F的坐标代入BC的直线方程,与A的坐标代入BC的直接方程异号,即D,E,F与A点在BC直线两侧
满足1),2),3)任意一条即可判定两个三角形不相交。
对两个任意多边形分割成两个三角形集合,判断两个集合中的三角形有没有相交就可判断两个多边形有没有相交。
当然还需要进一步考虑怎样将坐标有效地组合,得到所需要的一系列三角形的坐标。
#2
多边形方程式相等? 有解和无解^_^
#3
把2组坐标 分别描述出他们的直线来 然后判断直线是否相交 ^_^
#4
不知道 楼主是怎么根据坐标来判断多边形的 如果能够顺利画出其中一个多边形来 只需要判断另外一个多边形 的点 是否有在它各个线段的2侧 如果有那就再判断 那2个点是否组成另外多边形的边
#5
何为相交??
能准确定义一下吗?
能准确定义一下吗?
#6
多边形相交实际上就是说有两条线段相交,且这两条直线分属于两个多边形,按照这个思路可以得出只要确认线段相交就行。
麻烦一些可以这样确认直线相交:
设A,B两个多边形
再设(x1,y1),(x2,y2)为A上两个相邻点,(a,b),(c,d)为B上两个相邻点
判断:
((a-x1)*(y1-y2)-(b-y1)*(x1-x2))*((a-x1)*(y1-y2)-(b-y1)*(x1-x2))
和((c-x1)*(y1-y2)-(d-y1)*(x1-x2))*((d-x1)*(y1-y2)-(b-y1)*(x1-x2))
如果至少有一组两个都小于0,则相交
如果都没有小于0的,但是至少有一组两个有至少其一等于0,则相邻
其余情况则是不相邻
麻烦一些可以这样确认直线相交:
设A,B两个多边形
再设(x1,y1),(x2,y2)为A上两个相邻点,(a,b),(c,d)为B上两个相邻点
判断:
((a-x1)*(y1-y2)-(b-y1)*(x1-x2))*((a-x1)*(y1-y2)-(b-y1)*(x1-x2))
和((c-x1)*(y1-y2)-(d-y1)*(x1-x2))*((d-x1)*(y1-y2)-(b-y1)*(x1-x2))
如果至少有一组两个都小于0,则相交
如果都没有小于0的,但是至少有一组两个有至少其一等于0,则相邻
其余情况则是不相邻
#7
对了还有一种情况是其中一个多边形的边横跨在另一个多边形内;
这种情况可在第二种假设中细分:当判断出有一组边时,分别取出边和对应的另一个多边形其余边循环比较,如果仍有“都没有小于0的,但是至少有一组两个有至少其一等于0”,则为相交
------------
这样应该比较完整了吧
这种情况可在第二种假设中细分:当判断出有一组边时,分别取出边和对应的另一个多边形其余边循环比较,如果仍有“都没有小于0的,但是至少有一组两个有至少其一等于0”,则为相交
------------
这样应该比较完整了吧
#8
按照你的思路只用建立两个链表,用以上的方法可以实现
#9
楼主,
可以使用 基本图形算法中的 扫描线方法
可以使用 基本图形算法中的 扫描线方法
#10
从多边形 的上顶点开始扫描,
直到 多边形的 下顶点,
如果在某个扫描位置 扫描线 进入一个多边形区域,
在没有退出该多边形时候,
又进入了第二个多边形,
那么两个多边形就是相交的 ....
直到 多边形的 下顶点,
如果在某个扫描位置 扫描线 进入一个多边形区域,
在没有退出该多边形时候,
又进入了第二个多边形,
那么两个多边形就是相交的 ....