質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.32%

  • Python

    9226questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    7417questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。

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

解決済

回答 3

投稿

  • 評価
  • クリップ 2
  • VIEW 904

evanstera

score 4

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

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

#[[[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]] ] #残ったリスト(いずれかの長方形に内包していた長方形)
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 3

+2

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


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

面積の順番に比較対象を絞り込む

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

空間分割法

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/16 10:29

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

    キャンセル

checkベストアンサー

+1

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

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

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2018/01/16 00:17

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

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

    キャンセル

  • 2018/01/16 00:44

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

    キャンセル

  • 2018/01/16 10:30

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

    キャンセル

  • 2018/01/16 10:32

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

    キャンセル

0

まず面積の大きい順に色違いでレンダリングして、その次に各長方形領域内で使用されている色数を見て、色数==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))

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.32%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

同じタグがついた質問を見る

  • Python

    9226questions

    Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

  • Python 3.x

    7417questions

    Python 3はPythonプログラミング言語の最新バージョンであり、2008年12月3日にリリースされました。