F*******h 发帖数: 136 | 1 请问
有何快速算法可以做判断两个正方形相交?
而且尽可能的减少时间复杂度?
谢谢
bow |
c*******e 发帖数: 8624 | 2 正方形A的4个点,每个点和正方形B的两个相邻顶点组成
三角形(4个)的面积和,如果这个和等于正方形B的面积
那么在内部,就是相交,否则就不相交.
不知道对不对,就闪过那么个年头
【在 F*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问 : 有何快速算法可以做判断两个正方形相交? : 而且尽可能的减少时间复杂度? : 谢谢 : bow
|
r****y 发帖数: 1437 | 3 check the distance between the centers of two squares.
【在 F*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问 : 有何快速算法可以做判断两个正方形相交? : 而且尽可能的减少时间复杂度? : 谢谢 : bow
|
c*******e 发帖数: 8624 | 4 这个不成吧
【在 r****y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : check the distance between the centers of two squares.
|
c*******e 发帖数: 8624 | 5 实际上就是求A的顶点里面到B的4条边的距离之和
如果<2倍A的边长,那就是在内部了;
好象还有问题,如果A完全在B的内部,这个也完全符合
再加上中心距离应该够了?
【在 c*******e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 正方形A的4个点,每个点和正方形B的两个相邻顶点组成 : 三角形(4个)的面积和,如果这个和等于正方形B的面积 : 那么在内部,就是相交,否则就不相交. : 不知道对不对,就闪过那么个年头
|
b**g 发帖数: 335 | 6 hint:判断两个正方形不相交更容易点
这是经典面试老题了
【在 F*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问 : 有何快速算法可以做判断两个正方形相交? : 而且尽可能的减少时间复杂度? : 谢谢 : bow
|
s**i 发帖数: 381 | 7 两个三角形相交得判断容易做吧?
正方形就做4次三角形预算吧?
不过可能不是最佳算法
【在 F*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问 : 有何快速算法可以做判断两个正方形相交? : 而且尽可能的减少时间复杂度? : 谢谢 : bow
|
s**i 发帖数: 381 | 8 对了,这个是二维还是三维得啊?
【在 F*******h 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 请问 : 有何快速算法可以做判断两个正方形相交? : 而且尽可能的减少时间复杂度? : 谢谢 : bow
|