一道阿里前端筆試題，求思路？

01-15

怎麼實現在一塊畫布上，畫任意個圓不相交，且圓不能碰邊界，要求做到時間和空間的平衡。

可以做碰撞檢測，再重畫，我看過一個類似的例子

@winter 的做法是先劃分區域，然後在區域內用圓填充；

正方形切割的方式最簡單，可以等大小的正方形切割，也可以用隨機大小，不斷填充縫隙（類似流式布局）。

其他多邊形來切割就相對複雜了。

@朱曉宇的做法比較符合我的邏輯，就是用物理手段模擬：

可以隨機生成不同大小的圓，然後用類似俄羅斯方塊的方式「落」下來，堆滿就行了。

demo time，一起來玩玩。

給每個塊加一個padding不就行了？

同心圓可以？

同心圓可以嗎？

在平面上畫若干個點，生成這些點的delaunay triangularization,這一步應該是O(nlogn)的，然後對每個三角形求內接圓就可以啦

function check相離 C1 C2

if 兩圓圓心距離 &> 兩圓半徑和

return true

變數計時變數

function generateData 參數：是否開始計時

如果可以計時開始計時

確定矩形面積

做邊界限制

生成添加圓的數據

例如，右面已經有一對，左面就添加右面最後添加的數據。

如果左面是單數，就隨機生成一個限制數據：圓心，半徑，添加到左面。

檢測是否可添加

成功，存儲隨機數據，結束計時，

如果是立即追加上的圓，則計算本次耗時與上次耗時之間的差，做延遲處理，

最後退出函數。

失敗可以添加定時器

在隨機值的基礎上，略做改動，遞歸此函數，參數為false

最後檢測添加函數

遍歷矩形一側的圓，

如果圓的右側添加，並且和下一個圓不符合碰撞情況，添加，break

返回值 true添加成功 false 失敗

附註：可能還有更好的策略，望跟帖！

剛好有閑,花了3個小時完成,沒做過類似功能一個小時寫完代碼要求挺高.

主要的思路是通過勾股定理判斷圓形是否相交, 處理相交的方法選擇了縮小圓半徑,縮小圓半徑還是相交則重新生成一個圓,如此循環. 畫100個圓的平均速度是90ms, 1000個圓耗時800ms-900ms

github : lzever/drawCircle

正反面畫可以嗎？

難道不是圓心之間的距離大於兩個圓的半徑和就夠了嗎？

怎麼都感覺是求最短路徑的變種。

先畫n個點，每個點坐標不同，求每個點離自己最近的那個點的距離，然後半徑等於這個距離的一半兒就可以了吧。

附加要求可以是，要求所有圓的面積加和最大。這樣的話這個方案應該就不適用了，那樣怎麼做得再想想

最簡單的思路是用方塊劃分空間，然後畫出比方塊內切園稍小的圓

我也參加了阿里的筆試，為什麼我沒有這道題啊。。。

不出邊界的話，可以讓所畫的圓心的範圍為畫布的寬高分別減去圓半徑的長度吧。

在下愚見，還望指正。

正反兩面各畫一個