前言

相信很多社交產(chǎn)品中，肯定會(huì)存在尋找附近人或者附近商家的需求，類(lèi)似下圖，在大圓和小圓之間(橘色區(qū)域)生成一系列的隨機(jī)圓，并且所有隨機(jī)圓之間也不能有交集，我暫且稱(chēng)這種圓為標(biāo)準(zhǔn)圓。

關(guān)于這樣的需要以前在做項(xiàng)目中有同事做過(guò)，雖然可以實(shí)現(xiàn)了上面的效果圖，但是坐標(biāo)及半徑都是寫(xiě)死，從寫(xiě)死的數(shù)據(jù)隨機(jī)取值，看上去是滿(mǎn)足了，但是對(duì)于用戶(hù)來(lái)說(shuō)多次使用該功能時(shí)，肯定有一定的視覺(jué)疲倦，且寫(xiě)死的一些數(shù)據(jù)真的不好寫(xiě)，如果大圓或者小圓半徑變化了，或者需要更多的標(biāo)準(zhǔn)圓，那怎么辦呢？一臉懵逼????

實(shí)現(xiàn)思路

思路一：

對(duì)于這個(gè)需求，我一開(kāi)始也陷入了寫(xiě)死數(shù)據(jù)的套路，但是在兼容大小圓半徑上做了一定的兼容，大致的將大圓切分成 9塊 ，然后在除了中間區(qū)域外的8塊區(qū)域再生成一系列的偽標(biāo)準(zhǔn)圓。然后取值時(shí)現(xiàn)隨機(jī)選取8塊區(qū)域，再隨機(jī)從塊區(qū)拿取 偽標(biāo)準(zhǔn)圓 ：

很明顯，在 1、3、6、8 塊中及中間塊 存在很大的誤差，明顯也不可取

思路二：

根據(jù)數(shù)學(xué)思路，尋找標(biāo)準(zhǔn)圓：

1、在大圓內(nèi)部生成 隨機(jī)圓1 ，也就是生成內(nèi)含圓：（其中只有圓1才是該步驟所需要的 隨機(jī)圓1 ）

對(duì)應(yīng)的數(shù)學(xué)公式，當(dāng)圓心距小于兩圓半徑之差時(shí) 兩圓內(nèi)含:

大圓中心坐標(biāo)為（px1、py1），半徑為R； 隨機(jī)圓中心坐標(biāo)為（px2、py2），半徑為r

Objective-c代碼如下：

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

2、從第1步得到的隨機(jī)圓1中，篩選出和小圓不相交 隨機(jī)圓2 :（其中只有圓1才是該步驟所需要的 隨機(jī)圓2 ）

對(duì)應(yīng)的數(shù)學(xué)公式，當(dāng)圓心距大于兩圓半徑之和時(shí) 兩圓外離:

小圓中心坐標(biāo)為（px1、py1），半徑為Rr； 隨機(jī)圓 中心坐標(biāo)為（px2、py2），半徑為r

Objective-c代碼如下：

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

3、從第2步得到的隨機(jī)圓2中，篩選出和已存在的 標(biāo)準(zhǔn)圓 不相交 隨機(jī)圓3 ， 隨機(jī)圓3 即我們所需要的 標(biāo)準(zhǔn)圓 （其中圓2是已經(jīng)存在的 標(biāo)準(zhǔn)圓 ，那么只有圓1才是該步驟所需要的 隨機(jī)圓3 ）

對(duì)應(yīng)的數(shù)學(xué)公式，當(dāng)圓心距小于兩圓半徑之和時(shí) 兩圓相交或兩圓內(nèi)含，隨機(jī)圓2應(yīng)該廢棄:

存在的標(biāo)準(zhǔn)圓中心坐標(biāo)為（px、py），半徑為rr； 隨機(jī)圓中心坐標(biāo)為（px2、py2），半徑為r

Objective-c代碼如下：

// 3: 新生成的 圓 和已經(jīng)存在的 圓 不能重合
 BOOL success = YES;
for (NSValue *value in randomCircleInfos) {
 CircleInfo circle; 
 [value getValue:&circle]; 
 // 只要新生成的 圓 和 任何一個(gè)存在的 圓 有交集，則失敗 
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]];}為了尋找 8 個(gè)標(biāo)準(zhǔn)圓一共生成了 53 個(gè)隨機(jī)圓 生成了 29 個(gè)在大圓內(nèi)部的圓 生成了 9 個(gè)在大圓內(nèi)部的圓且不與中圓有交集的圓 為了尋找 8 個(gè)標(biāo)準(zhǔn)圓一共生成了 38 個(gè)隨機(jī)圓 生成了 28 個(gè)在大圓內(nèi)部的圓 生成了 10 個(gè)在大圓內(nèi)部的圓且不與中圓有交集的圓

只要通過(guò)這三步成功后，即得到了我們所要的標(biāo)準(zhǔn)圓，從算法的時(shí)間復(fù)雜度看 ，得到標(biāo)準(zhǔn)圓的復(fù)雜度為O(n*n)，對(duì)于小量了標(biāo)準(zhǔn)圓來(lái)說(shuō)，速度是非?？斓模海ó?dāng)然效率上還由隨機(jī)圓的半徑有關(guān)系）

為了尋找 8 個(gè)標(biāo)準(zhǔn)圓一共生成了 53 個(gè)隨機(jī)圓 生成了 29 個(gè)在大圓內(nèi)部的圓 生成了 9 個(gè)在大圓內(nèi)部的圓且不與中圓有交集的圓  為了尋找 8 個(gè)標(biāo)準(zhǔn)圓一共生成了 38 個(gè)隨機(jī)圓 生成了 28 個(gè)在大圓內(nèi)部的圓 生成了 10 個(gè)在大圓內(nèi)部的圓且不與中圓有交集的圓

但是在產(chǎn)生大量的標(biāo)準(zhǔn)圓上，隨機(jī)生成的總量會(huì)非常大：(可以考慮將隨機(jī)圓半徑減少，或者生成該頁(yè)面之前，提前生成好這些標(biāo)準(zhǔn)圓相關(guān)數(shù)據(jù)：即圓心坐標(biāo)和半徑)

為了尋找 30 個(gè)標(biāo)準(zhǔn)圓 一共生成了 233220 個(gè)隨機(jī)圓 生成了 138095 個(gè)在大圓內(nèi)部的圓 生成了 40287 個(gè)在大圓內(nèi)部的圓且不與中圓有交集的圓

最后給出最終成果圖：

對(duì)應(yīng)的log日志：

為了尋找 9 個(gè)標(biāo)準(zhǔn)圓 一共生成了 127 個(gè)隨機(jī)圓 生成了 75 個(gè)在大圓內(nèi)部的圓 生成了 20 個(gè)在大圓內(nèi)部的圓且不與中圓有交集的圓為了尋找 12 個(gè)標(biāo)準(zhǔn)圓 一共生成了 265 個(gè)隨機(jī)圓 生成了 150 個(gè)在大圓內(nèi)部的圓 生成了 40 個(gè)在大圓內(nèi)部的圓且不與中圓有交集的圓 為了尋找 23 個(gè)標(biāo)準(zhǔn)圓 一共生成了 5181 個(gè)隨機(jī)圓 生成了 3112 個(gè)在大圓內(nèi)部的圓 生成了 909 個(gè)在大圓內(nèi)部的圓且不與中圓有交集的圓

源碼下載：點(diǎn)擊這里

總結(jié)

以上就是這篇文章的全部?jī)?nèi)容了，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來(lái)一定的幫助，如果有疑問(wèn)大家可以留言交流。