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