查找N个矩形重叠的有效方法 [英] Efficient way to find overlapping of N rectangles

问题描述

我正在尝试找到一种有效的解决方案，以找到n个矩形的重叠，其中矩形存储在两个单独的列表中.我们正在寻找 listA 中与 listB 中的矩形重叠的所有矩形(反之亦然).比较第一个列表和第二个列表中的一个元素可能会花费大量时间.我正在寻找有效的解决方案.

I am trying to find an efficient solution for finding overlapping of n rectangles where rectangles are stored in two separate lists. We are looking for all rectangles in listA that overlap with rectangles in listB (and vice versa). Comparing one element from the first list to second list could take immensely large amount of time. I am looking for an efficient solution.

我有两个矩形列表

rect = Rectangle(10, 12, 56, 15)
rect2 = Rectangle(0, 0,1, 15)
rect3 = Rectangle (10,  12, 56, 15)

listA = [rect, rect2]
listB = [rect3]

从类创建的

:

import numpy as np
import itertools as it

class  Rectangle(object):
    def __init__(self, left, right, bottom, top):
        self.left = left
        self.bottom = right
        self.right = bottom
        self.top = top

    def overlap(r1, r2):
        hoverlaps = True
        voverlaps = True
        if (r1.left > r2.right) or (r1.right < r2.left):
            hoverlaps = False
        if (r1.top < r2.bottom) or (r1.bottom > r2.top):
            voverlaps = False
        return hoverlaps and voverlaps

我需要将 listA 中的矩形与 listB 中的矩形进行比较，这样的代码效率非常低-逐一比较

I need to compare rectangle in listA to listB the code goes like this which is highly inefficient - comparing one by one

for a in it.combinations(listB):
    for b in it.combinations(listA):
        if a.overlap(b):

有没有更好的解决问题的有效方法?

Any better efficient method to deal with the problem?

推荐答案

首先:与输出敏感算法).
对于出现的问题， f∈Ω(m + n + o).

First off: As with many a problem from computational geometry, specifying the parameters for order-of-growth analysis needs care: calling the lengths of the lists m and n, the worst case in just those parameters is Ω(m×n), as all areas might overlap (in this regard, the algorithm from the question is asymptotically optimal). It is usual to include the size of the output: t = f(m, n, o) (Output-sensitive algorithm).
Trivially, f ∈ Ω(m+n+o) for the problem presented.

线扫描是一种将几何问题减少一维的范式-以其原始形式，从2D到1D，从平面到线.

Line Sweep is a paradigm to reduce geometrical problems by one dimension - in its original form, from 2D to 1D, plane to line.

想象一下平面中的所有矩形，列表使用不同的颜色.
现在，在该平面上扫一线-通常是从左到右，然后无限地 进一步向右对于低y坐标".(以递增的 x 顺序处理坐标，以递增的 y 顺序以相等的 x 坐标).
对于所有这种 sweep (或 scan )，每种颜色都保留一组代表"y间隔"的颜色.当前x坐标处的所有矩形的值，从空开始.(在支持插入，删除和枚举与查询间隔重叠的所有间隔的数据结构中:请参见下文.)
在矩形的左侧，将段添加到数据结构中以获取其颜色.报告任何其他颜色的重叠间隔/矩形.
在右侧，删除该段.
取决于重叠"的定义，请先处理左侧，再处理右侧(反之亦然).

Imagine all the rectangles in the plane, different colours for the lists.
 Now sweep a line across this plane - left to right, conventionally, and infinitesimally further to the right "for low y-coordinates" (handle coordinates in increasing x-order, increasing y-order for equal x).
 For all of this sweep (or scan), per colour keep one set representing the "y-intervals" of all rectangles at the current x-coordinate, starting empty. (In a data structure supporting insertion, deletion, and enumerating all intervals that overlap a query interval: see below.)
 Meeting the left side of a rectangle, add the segment to the data structure for its colour. Report overlapping intervals/rectangles in any other colour.
 At a right side, remove the segment.
 Depending on the definition of "overlapping", handle left sides before right sides - or the other way round.

有许多数据结构支持间隔的插入和删除，以及查找与查询间隔重叠的所有间隔.目前，我认为增强搜索树可能最容易理解，实施，测试和分析…
使用此方法，从 listA 和 listB 枚举所有与轴对齐的矩形(a，b)相交的所有 o 对应该在 O((m + n)log(m + n)+ o)时间和 O(m + n)空间中是可能的.对于较大的问题实例，请避免数据结构需要的空间超过线性空间((原始)分段树，一个有关间隔重叠的示例).

There are many data structures supporting insertion and deletion of intervals, and finding all intervals that overlap a query interval. Currently, I think Augmented Search-Trees may be easiest to understand, implement, test, analyse…
Using this, enumerating all o intersecting pairs of axis-aligned rectangles (a, b) from listA and listB should be possible in O((m+n)log(m+n)+o) time and O(m+n) space. For sizeable problem instances, avoid data structures needing more than linear space ((original) Segment Trees, for one example pertaining to interval overlap).

算法设计的另一范式是划分并征服" :如果存在计算几何问题，请选择一个可以将问题划分为多个独立的维度和一个坐标，以使下坐标"的子问题可以被分解.和上方的坐标"在预期的运行时间中接近.很可能，另一个(和不同的)子问题包括坐标"被分配给子问题.需要解决.当a)解决子问题的运行时间是超对数线性"，并且b)有一种廉价的(线性)方法可以从子问题的解决方案中构建整体解决方案时，这往往是有益的.问题.
这有助于解决并发问题，并且可以与任何其他解决子问题的方法一起使用，包括行扫描.

Another paradigm in algorithm design is Divide&Conquer: with a computational geometry problem, choose one dimension in which the problem can be divided into independent parts, and a coordinate such that the sub-problems for "coordinates below" and "coordinates above" are close in expected run-time. Quite possibly, another (and different) sub-problem "including the coordinate" needs to be solved. This tends to be beneficial when a) the run-time for solving sub-problems is "super-log-linear", and b) there is a cheap (linear) way to construct the overall solution from the solutions for the sub-problems.
This lends itself to concurrent problem solving, and can be used with any other approach for sub-problems, including line sweep.

有许多方法可以调整每种方法，首先是忽略可能对输出没有贡献的输入项.公平地"比较具有相似增长顺序的算法的实现，而不是针对公平的调整水平":尝试投入大量时间进行调整.

There will be many ways to tweak each approach, starting with disregarding input items that can't possibly contribute to the output. To "fairly" compare implementations of algorithms of like order of growth, don't aim for a fair "level of tweakedness": try to invest fair amounts of time for tweaking.

这篇关于查找N个矩形重叠的有效方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！