オーバーラップする四角形をグループ化する最も良い方法は? OpenCVを使用しようとしましたが、grouprectangles
メソッドが意図したとおりに動作しません。オーバーラップする四角形を効率的にグループ化する
私はこのような何かをすることについて考えた:最悪のシナリオでは、次のリストから削除されますマージされていないすべての矩形が、私はのn/2
反復を持っていると思いますので
L = [every rectangle]
L_next = []
while not L.empty():
for rectangle in L:
L.remove(rectangle)
for other_rectangle in L:
if rectangle overlaps with other_rectangle:
L_next += rectangle + other_rectangle
L = L_next
L_next = []
外側のループ。 2つの内部ループはn
とn - 1
回実行する必要があります。そのため、最悪の場合のシナリオでアルゴリズムは約になります。私は何も見逃さず、各ステップにはO(1)
しかかからないと仮定します。
問題:
1)が正しく長方形のグループをマージすること程度の等価クラスか何かを使用する必要があります。ブーストにはそんなことがありますか?
2)これは頻繁に行われなければならない操作のように思われるので、それ以上の素材が見つからないのは驚きです。どうしたの?
3)これを行うために既に実装されているものがないと仮定して、誰かが私のメソッドを改善するためのアドバイスを持っていますか?
4)2つの矩形が重なっているかどうかを確認するにはどうすればよいですか?