求一算法,检测一平面坐标系内数量特别巨大的矩形互相是否重叠

求一算法,检测一平面坐标系内数量特别巨大的矩形互相是否重叠
在一个平面坐标内,有数量特别巨大的矩形,他们的长宽、大小可能都不一样,位置也随机,知道所有矩形的顶点坐标,寻找一种算法能够确定他们的位置关系,也就是有没有互相重叠,两个两个的比较当然是可以的,但是由于数量巨大速度会很慢,那有没有更好的办法呢
imbx 1年前 已收到1个回答 举报

zs0212 幼苗

共回答了12个问题采纳率:83.3% 举报

将每个矩形根据四个顶点中最小x坐标进行排序,然后再根据每个矩形的最大x坐标插入到之前排的序列中,在这个序列中,如果某个矩形的最小x坐标和最大x坐标没有挨在一起,那它就有可能和排在最小最大坐标中间的所有矩形有重叠,记下这些可能重叠的矩形;然后再针对y坐标的最大和最小值进行同样操作,记下可能重叠的矩形;再对两次结果的交集进行逐个判断!时间复杂度和排序算法的时间复杂度一致!空间和重叠的数量成正比

1年前

6
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 17 q. 0.053 s. - webmaster@yulucn.com