您现在的位置: IOS教程網 >> IOS系統 >  >> iOS 程式開發 >> iOS 開發綜合

隨機生成兩圓之間互不重疊的標準圓:思路與性能實測

編輯:iOS 開發綜合

前言

社交類產品裡「附近的用戶/商家」幾乎是標配,視覺上常表現為:在一個大圓和中間的小圓之間(橘色環帶區域)撒佈若干個互不重疊的小圓,本文暫且把這些小圓稱為標準圓。

以前同事做過類似效果,但圓心坐標和半徑都是寫死的,只是從寫死的數據裡隨機取值。看似滿足需求,實際問題不少:用戶反覆使用會產生視覺疲勞;一旦大圓或小圓半徑變化、或需要更多標準圓,寫死的數據就完全跟不上。

思路一:切塊(否決)

最初也掉進了寫死數據的坑,只是對大小圓半徑做了一定兼容:把大圓切成 9 塊,除中間區域外的 8 塊各自生成一批「偽標準圓」,取用時先隨機選塊再從塊裡隨機取圓。

問題很直觀:1、3、6、8 這幾塊以及中間塊誤差很大,视觉上能明显看出分布不均,不可取。

思路二:用幾何條件逐步篩選

轉向數學解法,分三步過濾:

第一步:生成大圓內部的隨機圓1

依據的規則是:當圓心距小於兩圓半徑之差時,兩圓內含。

大圓圓心(px1、py1),半徑 R;隨機圓圓心(px2、py2),半徑 r

 // 1: 判斷隨機生成的 圓 包含在 self 這個大圓內部 if ( sqrt(pow(self.center.x - randomCPX, 2) + pow(self.frame.size.height / 2 - randomCPY, 2)) < (R - r) ) { }

第二步:排除與中央小圓相交的情況,得到隨機圓2

依據的規則是:當圓心距大於兩圓半徑之和時,兩圓外離。

小圓圓心(px1、py1),半徑 Rr;隨機圓圓心(px2、py2),半徑 r

 // 2: 判斷隨機生成的 圓 不在 中間 這個圓 不能重合, 即得到兩個圓之間的小圓 if (sqrt(pow(self.center.x - randomCPX, 2) + pow(self.frame.size.height / 2 - randomCPY, 2)) > (Rr + r)) { }

第三步:排除與已有標準圓相交的情況,得到隨機圓3,即最終的標準圓

依據的規則是:當圓心距小於兩圓半徑之和時,兩圓相交或內含,該隨機圓應廢棄。

已存在的標準圓圓心(px、py),半徑 rr;隨機圓圓心(px2、py2),半徑 r

 // 3: 新生成的 圓 和已經存在的 圓 不能重合 BOOL success = YES; for (NSValue *value in randomCircleInfos) { CircleInfo circle; [value getValue:&circle]; // 只要新生成的 圓 和 任何一個存在的 圓 有交集,則失敗 if (sqrt(pow(circle.center.x - randomCPX, 2) + pow(circle.center.y - randomCPY, 2)) <= (circle.radius + r)) { success = NO; break ; } } if (success) { [randomCircleInfos addObject:[self standardCircle:randomCPX centerY:randomCPY radius:r]];}

性能實測

三層過濾下,得到標準圓的時間複雜度約為 O(n²),但對於小量級的標準圓來說速度很快(實際效率還與隨機圓半徑的設定有關)。幾組實測數據:

為了尋找 8 個標準圓,一共生成 53 個隨機圓;其中 29 個落在圓內,9 個同時滿足與中圓無交集。

另一輪:尋找 8 個標準圓共生成 38 個隨機圓,圓內 28 個,最終合格 10 個。

規模放大後差異明顯:

尋找 30 個標準圓,一共生成 233220 個隨機圓,圓內 138095 個,合格 40287 個。

最終成果圖:

對應的 log 日志:

為了尋找 9 個標准圓 一共生成了 127 個隨機圓 生成了 75 個在大圓內部的圓 生成了 20 個在大圓內部的圓且不與中圓有交集的圓

為了尋找 12 個標准圓 一共生成了 265 個隨機圓 生成了 150 個在大圓內部的圓 生成了 40 個在大圓內部的圓且不與中圓有交集的圓

為了尋找 23 個標准圓 一共生成了 5181 個隨機圓 生成了 3112 個在大圓內部的圓 生成了 909 個在大圓內部的圓且不與中圓有交集的圓

源碼下載:點擊這裡

總結

這個方案用「隨機生成 + 三層幾何過濾」替代了寫死數據,半徑和數量都可以自由變化。需要留意的是,當標準圓數量較多時,隨機嘗試的總量會急劇上升(30 個就已經二十多萬次),實戰中可以適度減小隨機圓半徑,或者提前在後台把圓心坐標與半徑算好緩存下來,進入頁面時直接取用。

以上就是本文的全部內容,如有疑問歡迎留言交流。

  1. 上一篇文章:
  2. 下一篇文章:
蘋果刷機越獄教程| IOS教程問題解答| IOS技巧綜合| IOS7技巧| IOS8教程
Copyright © IOS教程網 All Rights Reserved