我想生成隨機矩形。這是一項相當容易的任務。問題是我需要它們不與這些黑點中的任何一個重疊：
倒置以方便觀察：
現在我可以告訴它忽略它生成的任何矩形，如果它與任何黑點重疊，但隨著點密度的增加，它會達到低效率的
uj5u.com熱心網友回復：
選擇一個隨機白點。
找到最近的黑點。這將是一個圓的半徑
創建一個以隨機點為中心的圓。
在圓上選擇 2 個點。找到它們通過圓心的相對點，從 4 個點繪制矩形。
PS只要確保2點不是圓的直徑......
uj5u.com熱心網友回復：
這是我的想法，與其他人提出的想法略有不同。這是演算法：
- 為點的 x 和 y 創建 2 個陣列。復制 x 和 ys 并對陣列進行遞增排序。
- 創建一個隨機 x 和隨機 y。這將是矩形的左上角。讓我們稱它們為
x1andy1。 - 在 x 陣列中對最小的 x 進行二分搜索，使得
x >= x1. - 在 y 陣列中進行二分搜索，找到最大的 y 使得
y <= y1.- if
x1 == x or y1 == y: go to step 2注意：我們不能展開來創建一個矩形。
- if
- 在您在第 3 步中找到的隨機 x 之間創建一個
x1 and the right bound x，兩端互斥。呼叫它x2。 - 在您在第 4 步中找到的隨機 y 之間創建一個隨機 y
y2 and the lower bound y，兩端互斥。呼叫它y2。 (x1, y1)將和保存(x2, y2)為矩形的左上角和右下角。- 從第 2 步開始重復。
該演算法在準備階段具有初始時間復雜度O(n * log n)和空間復雜度，其中是給定點的數量。對于二分搜索，每個矩形創建都有時間復雜度。我假設矩形的左上角和一個點之間的碰撞概率很低，我們可以忽略它。O(n)nO(log n)
如果您為它們選擇了正確的資料結構（如排序地圖、排序串列或類似的東西，具體取決于它在特定語言中的名稱），這種方法還允許您以對數時間更新這些點。
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/413570.html
標籤：
上一篇：具有高布局的SwiftUI影像