[Python3]長方形に内包される長方形を判定したい

Question

複数の長方形の座標を元に，長方形いずれかの長方形を内包するときその外側にある長方形のリストを削除したいです．
長方形が重なることはないので外か内かどちらかになります．また角度もありません．
以下のような結果が出るようにしたいです．

総当たりで判定するよりもそこそこ効率的な解き方はありますか？
どうぞよろしくお願いいたします．

#[[[left,top],[right,bottom]]]
target_list = [[[0, 0],[ 400, 800]], [[2,2], [200,400]], [[5,5],[20,40]], [[10,450], [300,500]] ]

result = [[[5,5],[20,40]], [[10,450], [300,500]] ] #残ったリスト（いずれかの長方形に内包していた長方形）

Answer 1

総当たり（N^2オーダーの計算量）を気にすることは悪くないとは思いますが・・・そこそこ効率的な考え方を・・・という程度の動機であれば、総当たりかどうかよりも「list.appendを使わずに内包表記でかく（for文によるループ論理をなるべく避ける）」のようなPythonの性能の特徴を踏まえたような書き方を工夫すれば充分なことも多いと思います。計算回数が数百～数万程度だとアルゴリズムによる計算量を気にするよりPythonでの書き方の違いによって繰り返しを行う部分がPythonのnativeな実装の中で行われるのかfor文のようにpythonインタープリタのレベルで動くのかの違い位だけ気にするというのでもいいのではないでしょうか？

---

もし処理対象の四角形の領域の数Nが数万とか数十万というオーダーで、「アルゴリズムの計算量オーダーを気にして」処理しなければならないのなら、「そこそこ」ではなく「それなりに考えた」方法を採ることになるだろうと思います。

###面積の順番に比較対象を絞り込む
「重なりがない」という前提を利用して領域を面積の順番にあらかじめソートしておき、特定の領域より小さいものだけを「内包されるかどうかの判定対象にする」といった方法で計算量を押さえられると思います。

###空間分割法
効率化の前提として「空間が非常に広大、かつ範囲があらかじめわかっている」「個々の領域の大きさはそう大きくない」といった条件を満たすようなら、空間の全座標点をある程度の大きさのブロックに分割し、「どのブロックに属しているか」でＮ個の領域をあらかじめグルーピングしておき「同じブロック・および近隣のブロックに属しているもの同士のみを総当たりで確認する」といった方法で計算量を下げることができると思います。

Comments

[evanstera]

グルーピングについて少し考えていましたが，面積の比較は盲点でした．
目的によってアルゴリズム以外でコーディングのテクニックで対処できるというご指摘も大変参考になりました．
ありがとうございます．

Answer 2

KSwordOfHasteさんの面積の大きい順にそれよりも小さいものを比較するという方法には大いに同意します。図形が包含できるためには、必ず被包含対象の図形は包含する図形よりも小さくなければならないはずです。これで大幅に計算量（つまり繰り返し回数）はかなり減りますが、さらに、図形A・B・Cがあり、AはBを包含し、AがCを包含している場合、BとCは削除対象なのでBとCの比較は必要ありません。つまり、一度、比較によって削除された図形はその後の比較対象から除外することができるということです。

ということで整理すると、
1）各図形の面積を計算し、大きい順に並び変える。
2）最も大きいものを基準にそれよりも小さいものについて包含判定を行う。
3）判定の結果、削除となったものを除外する。
4）除外したもののうち、比較作業未済のものについて包含判定を行う。（以後、3）に戻る）
となるようにコードを作成するといいかと思います。
なお、実際にコードにする際は、DataFrameからarrayに変換して一括処理をうまく使うようにしたほうがコードの見やすく、計算量が少なくなると思います。

Comments

[KSwordOfHaste]

> 比較によって削除された図形はその後の比較対象から除外する
そうした工夫も考えたくなりますよね・・・

ところで、「外側にある長方形のリストを削除」とのことなので、包含している方を削除すると解釈したのですが?

[R.Shigemori]

済みません。問題文を逆に読んでいました。処理としては同じで、残ったものは最終的なアウトプットから除外するリストという解釈でうまくいくはずです。

[KSwordOfHaste]

> 最終的なアウトプットから除外するリストという解釈でうまくいく
そうですね。
本件のような工夫は最適化の一環として有効だと思います。

[evanstera]

ご指摘頂いた方法で実装したうまくいきました．
回答ありがとうございます．

Answer 3

まず面積の大きい順に色違いでレンダリングして、その次に各長方形領域内で使用されている色数を見て、色数==1なら残す。

from itertools import chain
from collections import namedtuple
from functools import total_ordering
from operator import sub

from PIL import Image
from PIL import ImageOps


X = slice(0, None, 2)
Y = slice(1, None, 2)


@total_ordering
class Rect(namedtuple('Rect', 'x1 y1 x2 y2')):
    @property
    def w(self):
        return abs(sub(*self[X]))

    @property
    def h(self):
        return abs(sub(*self[Y]))

    @property
    def area(self):
        return self.w * self.h

    def __lt__(self, other):
        return self.area < other.area

    def __eq__(self, other):
        return self.area == other.area

    @classmethod
    def from_2d(cls, array):
        return cls(*chain(*array))

    def to_2d(self):
        return [*zip(self[X], self[Y])]


def fgrects(rects, mode='RGB', debug=False):
    rects = [*sorted(map(Rect.from_2d, rects), reverse=True)]
    flatten = [*chain(*rects)]
    field = Image.new(mode, (max(flatten[X]), max(flatten[Y])))

    for color, rect in enumerate(rects, 1):
        field.paste(color, rect)

    if debug:
        ImageOps.equalize(field).show()
        for rect in rects:
            print(rect)

    n_colors = 1 + len(rects)
    for rect in rects:
        if len(field.crop(rect).getcolors(n_colors)) == 1:
            yield rect.to_2d()


target_list = [[[0, 0],[ 400, 800]], [[2,2], [200,400]], [[5,5],[20,40]], [[10,450], [300,500]]]
print(*fgrects(target_list, debug=True))