如何檢查矩形是否可以放入邊界區域？

我寫了一個函式，它會生成很多這樣的東西：

[
        (0, 619.5312394955338, 337.573529597446, 1080),
        (619.5312394955338, 1544.7619727875272, 0, 310.3079296654736),
        (619.5312394955338, 1544.7619727875272, 310.3079296654736, 337.573529597446),
        (1544.7619727875272, 1920, 0, 310.3079296654736),
        (619.5312394955338, 1088.2418093689296, 708.2009619111413, 1080),
        (1088.2418093689296, 1920, 337.573529597446, 708.2009619111413),
        (1088.2418093689296, 1920, 708.2009619111413, 1080),
        (0, 173.32617646340788, 288.56747000927186, 337.573529597446),
        (173.32617646340788, 619.5312394955338, 0, 288.56747000927186),
        (173.32617646340788, 619.5312394955338, 288.56747000927186, 337.573529597446),
        (0, 25.117144604340456, 177.08675820480235, 288.56747000927186),
        (25.117144604340456, 173.32617646340788, 0, 177.08675820480235),
        (25.117144604340456, 173.32617646340788, 177.08675820480235, 288.56747000927186),
        (0, 22.953859822450067, 0, 96.22494617847441),
        (0, 22.953859822450067, 96.22494617847441, 177.08675820480235),
        (22.953859822450067, 25.117144604340456, 0, 96.22494617847441),
        (22.953859822450067, 25.117144604340456, 96.22494617847441, 177.08675820480235),
        (619.5312394955338, 1061.0668595171933, 337.573529597446, 487.04072151109654),
        (619.5312394955338, 1061.0668595171933, 487.04072151109654, 708.2009619111413),
        (1061.0668595171933, 1088.2418093689296, 337.573529597446, 487.04072151109654),
        (1061.0668595171933, 1088.2418093689296, 487.04072151109654, 708.2009619111413),
        (1544.7619727875272, 1797.260895403902, 310.3079296654736, 324.5737372982961),
        (1544.7619727875272, 1797.260895403902, 324.5737372982961, 337.573529597446),
        (1797.260895403902, 1920, 310.3079296654736, 324.5737372982961),
        (1797.260895403902, 1920, 324.5737372982961, 337.573529597446)
]

第一個數字總是小于第二個數字，第三個數字總是小于第四個數字，前兩個數字代表x坐標，后兩個數字代表y坐標。

上面的串列代表了這一點：

[
        [(0, 337.573529597446), (619.5312394955338, 337.573529597446), (619.5312394955338, 1080), (0, 1080)],
        [(619.5312394955338, 0), (1544.7619727875272, 0), (1544.7619727875272, 310.3079296654736), (619.5312394955338, 310.3079296654736)],
        [(619.5312394955338, 310.3079296654736), (1544.7619727875272, 310.3079296654736), (1544.7619727875272, 337.573529597446), (619.5312394955338, 337.573529597446)],
        [(1544.7619727875272, 0), (1920, 0), (1920, 310.3079296654736), (1544.7619727875272, 310.3079296654736)],
        [(619.5312394955338, 708.2009619111413), (1088.2418093689296, 708.2009619111413), (1088.2418093689296, 1080), (619.5312394955338, 1080)],
        [(1088.2418093689296, 337.573529597446), (1920, 337.573529597446), (1920, 708.2009619111413), (1088.2418093689296, 708.2009619111413)],
        [(1088.2418093689296, 708.2009619111413), (1920, 708.2009619111413), (1920, 1080), (1088.2418093689296, 1080)],
        [(0, 288.56747000927186), (173.32617646340788, 288.56747000927186), (173.32617646340788, 337.573529597446), (0, 337.573529597446)],
        [(173.32617646340788, 0), (619.5312394955338, 0), (619.5312394955338, 288.56747000927186), (173.32617646340788, 288.56747000927186)],
        [(173.32617646340788, 288.56747000927186), (619.5312394955338, 288.56747000927186), (619.5312394955338, 337.573529597446), (173.32617646340788, 337.573529597446)],
        [(0, 177.08675820480235), (25.117144604340456, 177.08675820480235), (25.117144604340456, 288.56747000927186), (0, 288.56747000927186)],
        [(25.117144604340456, 0), (173.32617646340788, 0), (173.32617646340788, 177.08675820480235), (25.117144604340456, 177.08675820480235)],
        [(25.117144604340456, 177.08675820480235), (173.32617646340788, 177.08675820480235), (173.32617646340788, 288.56747000927186), (25.117144604340456, 288.56747000927186)],
        [(0, 0), (22.953859822450067, 0), (22.953859822450067, 96.22494617847441), (0, 96.22494617847441)],
        [(0, 96.22494617847441), (22.953859822450067, 96.22494617847441), (22.953859822450067, 177.08675820480235), (0, 177.08675820480235)],
        [(22.953859822450067, 0), (25.117144604340456, 0), (25.117144604340456, 96.22494617847441), (22.953859822450067, 96.22494617847441)],
        [(22.953859822450067, 96.22494617847441), (25.117144604340456, 96.22494617847441), (25.117144604340456, 177.08675820480235), (22.953859822450067, 177.08675820480235)],
        [(619.5312394955338, 337.573529597446), (1061.0668595171933, 337.573529597446), (1061.0668595171933, 487.04072151109654), (619.5312394955338, 487.04072151109654)],
        [(619.5312394955338, 487.04072151109654), (1061.0668595171933, 487.04072151109654), (1061.0668595171933, 708.2009619111413), (619.5312394955338, 708.2009619111413)],
        [(1061.0668595171933, 337.573529597446), (1088.2418093689296, 337.573529597446), (1088.2418093689296, 487.04072151109654), (1061.0668595171933, 487.04072151109654)],
        [(1061.0668595171933, 487.04072151109654), (1088.2418093689296, 487.04072151109654), (1088.2418093689296, 708.2009619111413), (1061.0668595171933, 708.2009619111413)],
        [(1544.7619727875272, 310.3079296654736), (1797.260895403902, 310.3079296654736), (1797.260895403902, 324.5737372982961), (1544.7619727875272, 324.5737372982961)],
        [(1544.7619727875272, 324.5737372982961), (1797.260895403902, 324.5737372982961), (1797.260895403902, 337.573529597446), (1544.7619727875272, 337.573529597446)],
        [(1797.260895403902, 310.3079296654736), (1920, 310.3079296654736), (1920, 324.5737372982961), (1797.260895403902, 324.5737372982961)],
        [(1797.260895403902, 324.5737372982961), (1920, 324.5737372982961), (1920, 337.573529597446), (1797.260895403902, 337.573529597446)]
]

非重疊矩形的頂點坐標串列：

我想知道，給定一個具有 widthw和 height的矩形h，我如何有效地找到該矩形可以放入的所有邊界框？

我只知道如何使用串列理解來做到這一點：

[(x1, x2, y1, y2) for x1, x2, y1, y2 in limits if x2 - x1 >= w and y2 - y1 >= h]

不允許旋轉。并且位置被忽略。只有大小很重要。

uj5u.com熱心網友回復：

恕我直言，這是裝箱問題的一個實體。矩形包裝的子型別。簡化，這意味著，一般來說，沒有比真正嘗試所有可能的組合來找到匹配項更好/更快的解決方案。

Wikipedia 鏈接了兩種不同的可能方法，并稍微改進了運行時（[1]，[2]）。第一個旨在始終找到最佳解決方案，第二個也可以提出“好，但不完美”的解決方案。它們都很復雜，所以我不會在這里詳細介紹。你可以看看它們，它們解釋得很好，如果這對你來說很有趣的話。

我個人的，沒有那么詳細的方法會更具啟發性，但仍然可以找到最佳解決方案。啟發式方法意味著，可以在程序中提前或非常早地消除一些組合，因此總體上執行的操作更少。

• 對于每個給定的矩形，通過乘以寬度和高度來計算其面積。
• 將這些值與矩形定義一起存盤在支持按此區域值排序的資料結構中（如樹形圖）。
• 對于每個用于比較的矩形，您可以忽略所有面積小于其自身面積的給定矩形。因此，您只需切斷一些源矩形進行比較。
• 無論如何，對于每個剩余的源矩形，您仍然需要進行寬度和高度的填充比較。

我沒有根據所需的（更少）操作來計算我的解決方案的性能增益，當然，就像每個啟發式方法一樣，它高度依賴于您必須處理的具體矩形實體。但總的來說，盡管初始開銷較大（用于計算所有區域），但您應該更快地出來，因為 - 平均而言 - 您對每個矩形進行的比較較少。

uj5u.com熱心網友回復：

如果你有很多矩形和很多測驗要做，那么你可以用部分持久的紅黑樹或類似的東西來解決這個問題。部分持久性意味著資料結構的所有先前版本在您更改后仍然可以訪問。

該解決方案將需要 O(N log N) 時間和空間來設定資料結構，但只需 O(log N output_size) 即可找到對于任何特定矩形都足夠大的所有框。

考慮到這種資料結構，雖然有些復雜，但解決問題很容易。

建造：

1. 從一棵空樹開始。我們將把矩形放入這棵樹中，按高度排序。
2. 按寬度對矩形進行排序，并按寬度遞減的順序處理它們。
3. 對于每個矩形，將其添加到樹中。對于每個寬度，請記住您創建的最后一棵樹。

詢問：

1. 在上面（3）中創建的串列中，二進制搜索找到最小寬度>=查詢寬度，并檢索其樹版本。這棵樹將包含所有足夠寬的矩形，按高度排序。

2. 從最大高度開始遍歷樹，直到到達太小的高度。輸出你找到的每個矩形。

您可以在網上找到部分持久性紅黑樹的實作。它們在函式式語言中很流行，并且被用于大量的計算幾何問題。不過，我不知道 python 中已有的實作。

標籤：Python python-3.x 算法

上一篇：我的演算法的時間和空間復雜度是多少？

下一篇：javascript中使用堆疊鏈表的中綴后綴演算法