複数の長方形の座標を元に,長方形いずれかの長方形を内包するときその外側にある長方形のリストを削除したいです.
長方形が重なることはないので外か内かどちらかになります.また角度もありません.
以下のような結果が出るようにしたいです.
総当たりで判定するよりもそこそこ効率的な解き方はありますか?
どうぞよろしくお願いいたします.
python
1#[[[left,top],[right,bottom]]] 2target_list = [[[0, 0],[ 400, 800]], [[2,2], [200,400]], [[5,5],[20,40]], [[10,450], [300,500]] ] 3 4result = [[[5,5],[20,40]], [[10,450], [300,500]] ] #残ったリスト(いずれかの長方形に内包していた長方形)
気になる質問をクリップする
クリップした質問は、後からいつでもMYページで確認できます。
またクリップした質問に回答があった際、通知やメールを受け取ることができます。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
回答3件
0
総当たり(N^2オーダーの計算量)を気にすることは悪くないとは思いますが・・・そこそこ効率的な考え方を・・・という程度の動機であれば、総当たりかどうかよりも「list.appendを使わずに内包表記でかく(for文によるループ論理をなるべく避ける)」のようなPythonの性能の特徴を踏まえたような書き方を工夫すれば充分なことも多いと思います。計算回数が数百~数万程度だとアルゴリズムによる計算量を気にするよりPythonでの書き方の違いによって繰り返しを行う部分がPythonのnativeな実装の中で行われるのかfor文のようにpythonインタープリタのレベルで動くのかの違い位だけ気にするというのでもいいのではないでしょうか?
もし処理対象の四角形の領域の数Nが数万とか数十万というオーダーで、「アルゴリズムの計算量オーダーを気にして」処理しなければならないのなら、「そこそこ」ではなく「それなりに考えた」方法を採ることになるだろうと思います。
###面積の順番に比較対象を絞り込む
「重なりがない」という前提を利用して領域を面積の順番にあらかじめソートしておき、特定の領域より小さいものだけを「内包されるかどうかの判定対象にする」といった方法で計算量を押さえられると思います。
###空間分割法
効率化の前提として「空間が非常に広大、かつ範囲があらかじめわかっている」「個々の領域の大きさはそう大きくない」といった条件を満たすようなら、空間の全座標点をある程度の大きさのブロックに分割し、「どのブロックに属しているか」でN個の領域をあらかじめグルーピングしておき「同じブロック・および近隣のブロックに属しているもの同士のみを総当たりで確認する」といった方法で計算量を下げることができると思います。
投稿2018/01/15 13:44
総合スコア18394
0
ベストアンサー
KSwordOfHasteさんの面積の大きい順にそれよりも小さいものを比較するという方法には大いに同意します。図形が包含できるためには、必ず被包含対象の図形は包含する図形よりも小さくなければならないはずです。これで大幅に計算量(つまり繰り返し回数)はかなり減りますが、さらに、図形A・B・Cがあり、AはBを包含し、AがCを包含している場合、BとCは削除対象なのでBとCの比較は必要ありません。つまり、一度、比較によって削除された図形はその後の比較対象から除外することができるということです。
ということで整理すると、
1)各図形の面積を計算し、大きい順に並び変える。
2)最も大きいものを基準にそれよりも小さいものについて包含判定を行う。
3)判定の結果、削除となったものを除外する。
4)除外したもののうち、比較作業未済のものについて包含判定を行う。(以後、3)に戻る)
となるようにコードを作成するといいかと思います。
なお、実際にコードにする際は、DataFrameからarrayに変換して一括処理をうまく使うようにしたほうがコードの見やすく、計算量が少なくなると思います。
投稿2018/01/15 14:51
総合スコア3376
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/01/15 15:44
2018/01/16 01:30
2018/01/16 01:32
0
まず面積の大きい順に色違いでレンダリングして、その次に各長方形領域内で使用されている色数を見て、色数==1なら残す。
python
1 2from itertools import chain 3from collections import namedtuple 4from functools import total_ordering 5from operator import sub 6 7from PIL import Image 8from PIL import ImageOps 9 10 11X = slice(0, None, 2) 12Y = slice(1, None, 2) 13 14 15@total_ordering 16class Rect(namedtuple('Rect', 'x1 y1 x2 y2')): 17 @property 18 def w(self): 19 return abs(sub(*self[X])) 20 21 @property 22 def h(self): 23 return abs(sub(*self[Y])) 24 25 @property 26 def area(self): 27 return self.w * self.h 28 29 def __lt__(self, other): 30 return self.area < other.area 31 32 def __eq__(self, other): 33 return self.area == other.area 34 35 @classmethod 36 def from_2d(cls, array): 37 return cls(*chain(*array)) 38 39 def to_2d(self): 40 return [*zip(self[X], self[Y])] 41 42 43def fgrects(rects, mode='RGB', debug=False): 44 rects = [*sorted(map(Rect.from_2d, rects), reverse=True)] 45 flatten = [*chain(*rects)] 46 field = Image.new(mode, (max(flatten[X]), max(flatten[Y]))) 47 48 for color, rect in enumerate(rects, 1): 49 field.paste(color, rect) 50 51 if debug: 52 ImageOps.equalize(field).show() 53 for rect in rects: 54 print(rect) 55 56 n_colors = 1 + len(rects) 57 for rect in rects: 58 if len(field.crop(rect).getcolors(n_colors)) == 1: 59 yield rect.to_2d() 60 61 62target_list = [[[0, 0],[ 400, 800]], [[2,2], [200,400]], [[5,5],[20,40]], [[10,450], [300,500]]] 63print(*fgrects(target_list, debug=True))
投稿2018/01/16 08:32
編集2018/01/16 08:40総合スコア6142
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
あなたの回答
tips
太字
斜体
打ち消し線
見出し
引用テキストの挿入
コードの挿入
リンクの挿入
リストの挿入
番号リストの挿入
表の挿入
水平線の挿入
プレビュー
質問の解決につながる回答をしましょう。 サンプルコードなど、より具体的な説明があると質問者の理解の助けになります。 また、読む側のことを考えた、分かりやすい文章を心がけましょう。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2018/01/16 01:29