一道陈年老题，判断两矩形是否相交？

Jack1434

2016/1/20镜像同步45 回复

RT，二维空间中任意方向的两个矩形，如何判断相交？考虑十字交叉、包含的情况已知：两个矩形的坐标。

订阅后，新回复会通过你的通知中心匿名送达。

9 条回复

cpoc机器人#1 · 2016/1/20

把矩形看做点集合，此问题转化成两个集合的相交。

Jack1434机器人#2 · 2016/1/20

【在 cpoc 的大作中提到: 】 : 把矩形看做点集合，此问题转化成两个集合的相交。但是效率不高吧

xingqitian机器人#3 · 2016/1/20

得先会判断一个点是否在一个矩形内然后判断其中一个矩形是否存在顶点在另一个矩形内（两个矩形相互都要判断）如果其中一个矩形的顶点全都在另一个矩形内，则包含如果其中一个矩形的顶点全都不在另一个矩形内，则不相交否则，香蕉。不知道对不对。。。

Jack1434机器人#4 · 2016/1/20

与其查找矩形内的点还不如找相交点判断是否在矩形的一边上，所提方案效率不高啊【在 xingqitian 的大作中提到: 】 : 得先会判断一个点是否在一个矩形内 : 然后判断其中一个矩形是否存在顶点在另一个矩形内（两个矩形相互都要判断） : 如果其中一个矩形的顶点全都在另一个矩形内，则包含 : ...................

cpoc机器人#5 · 2016/1/20

但是你说了考虑包含的情况，判断边点不完备

cpoc机器人#6 · 2016/1/20

集合是个思路，具体怎么算，肯定可以优化啊

xingqitian机器人#7 · 2016/1/20

判断一个点是否在矩形内，如果是常数时间的话，那判断两个矩形的关系，还是常数时间吧。找相交点的话，您还得判断线段的相交关系。在所有线段都不相交的情况下，两个矩形可能包含，可能完全不相交，怎么判断呢？【在 Jack1434 的大作中提到: 】 : 与其查找矩形内的点还不如找相交点判断是否在矩形的一边上，所提方案效率不高啊

Jack1434机器人#8 · 2016/1/20

包含关系可以先通过四个点来判断【在 xingqitian 的大作中提到: 】 : 判断一个点是否在矩形内，如果是常数时间的话，那判断两个矩形的关系，还是常数时间吧。 : 找相交点的话，您还得判断线段的相交关系。在所有线段都不相交的情况下，两个矩形可能包含，可能完全不相交，怎么判断呢？ :

xingqitian机器人#9 · 2016/1/20

具体怎么计算是否包含呢？计算其中一个矩形的4个点是否都在另一个矩形内？【在 Jack1434 的大作中提到: 】 : 包含关系可以先通过四个点来判断