 「封面」- 帶德勞內(nèi)三角化的 Voronoi 本篇預(yù)計閱讀時長9min，難度 ???????? 大家好，我是科學(xué)羊，本文節(jié)選，今天我們談一個新知識—— Voronoi（沃羅諾伊圖）圖。 言論 其實大家看封面就知道這是個啥了，是不是感覺很像某個干旱地帶的田地呢。當(dāng)然，這都是自然產(chǎn)生的，至于有沒有給人啟發(fā)，其實不然。但這個圖的思想確是給人很重要的依據(jù)與應(yīng)用。 接下來我?guī)Т蠹乙黄鹛剿飨玛P(guān)于沃羅諾伊圖的故事。 01 什么是沃羅諾伊圖 你可能不知道Voronoi圖（也稱為Dirichlet鑲嵌圖或Thiessen多邊形），但你一定在生活中無數(shù)次見過它們。 無論是在地圖學(xué)、生物學(xué)、計算機(jī)科學(xué)、統(tǒng)計學(xué)，還是在考古學(xué)、建筑學(xué)和藝術(shù)中，Voronoi圖都有廣泛的應(yīng)用。這種圖形看似簡單，卻蘊含著令人驚嘆的性質(zhì)。 沃羅諾伊圖（Voronoi 圖）最早可以追溯到 17 世紀(jì)，當(dāng)時法國數(shù)學(xué)家笛卡爾（René Descartes） 研究了關(guān)于空間劃分的問題。到了 19 世紀(jì)，Voronoi 圖由烏克蘭裔俄國數(shù)學(xué)家 Georgy Voronoi 進(jìn)行了系統(tǒng)地研究和命名。 最初研究沃羅諾伊圖是為了理解和分析空間中點的分布及其相互關(guān)系。 通過將空間劃分成若干區(qū)域，可以研究和解決各種幾何、數(shù)學(xué)以及現(xiàn)實生活中的問題。 那么，到底什么是Voronoi圖？ 想象一下，你和你的朋友們站在一片空地上。 每個人在地上畫一個圓圈，這個圓圈代表你們每個人的地盤。 每個人的地盤是離自己最近的區(qū)域。如果兩個圈子重疊了，那么在重疊的地方畫一條線，把重疊的區(qū)域分開。 最后，你們就會得到一幅圖，這幅圖就是沃羅諾伊圖。 那么你們每個人就是沃羅諾伊圖的種子點，而每個區(qū)域里的點離某個種子點最近就是最近區(qū)域。 再比如，想象一下你在一張紙上畫n個點，Voronoi圖就是將平面細(xì)分為n個單元，每個單元包含了平面中最接近一個特定點的區(qū)域。 這些單元共同覆蓋了整個平面，形成了一個鑲嵌結(jié)構(gòu)。  正如上圖所示，我們繪制了100個隨機(jī)點及其對應(yīng)的Voronoi圖。你會看到，每個點都被一個單元格包圍，這些單元格的邊界在兩個或多個點之間完全等距。 換句話說，關(guān)鍵點在于，單元格中的所有區(qū)域都比鄰近的點更接近單元格中的點。 看到這里你肯定已經(jīng)想到了很多自然界中相似的場景，比如，從洋蔥皮的細(xì)胞結(jié)構(gòu)到菠蘿蜜的外殼，再到長頸鹿的皮毛，這些圖案幾乎無處不在！  Voronoi 模式在自然界無處不在｜ (從左上角到右下角: 肌肉的橫截面，長頸鹿的皮毛圖案，蜻蜓的翅膀，大蒜球，玉米，掛在樹上的菠蘿蜜。) 資料來源: Nephron，Nirav Shah，KarolinaGrabowska，StarGlade，MaliMaeder，Abi Jacob -meduim 當(dāng)然，這些圖案之所以無處不在，有幾個原因。 首先，Voronoi圖形成了有效的形狀，完全鑲嵌了平面，所有空間都被充分利用。如果你想在有限的空間內(nèi)盡可能多地填充內(nèi)容，比如肌肉纖維或蜂巢，這是非常方便的。 其次，Voronoi圖是一種自發(fā)的模式，無論何時，只要有東西從不同的點以均勻的速度增長，就會形成這樣的圖案。 例如，長頸鹿胚胎中的黑色素分泌細(xì)胞分布不均勻，這些細(xì)胞負(fù)責(zé)長頸鹿斑點的深色素沉著。在妊娠過程中，這些細(xì)胞釋放黑色素，形成向外輻射的斑點。  一個 Voronoi 圖是從分散的點不斷向外生長得到的 來源: wiki 或許是因為它們自發(fā)的“自然”外觀，又或是因為它們令人著迷的隨機(jī)性，Voronoi圖被有意地應(yīng)用在人造結(jié)構(gòu)中。 比如，大家可以查看下圖，2008年北京奧運會的水立方就是一個典型案例。 水立方的天花板和外立面采用了Voronoi圖的設(shè)計，因為它們能讓人聯(lián)想到泡沫的形態(tài)，尤其在夜晚，當(dāng)整個建筑被藍(lán)色燈光照亮?xí)r，這種效果更為明顯。 當(dāng)然，Voronoi圖的欣賞并不止于現(xiàn)代建筑。 中國宋代的官窯和葛窯陶瓷上獨特的裂紋也是一種Voronoi圖案。 這些裂紋在冷卻過程中故意形成，被稱為分層裂解，常產(chǎn)生類似于Voronoi圖的斑塊模式。這種圖案在瓷器中被廣泛模仿，成為最受追捧的樣式之一。  另外，Voronoi圖在圖形藝術(shù)中也很常見，被用于創(chuàng)造“抽象”模式。 例如，本文的縮略圖就是通過生成隨機(jī)點和構(gòu)造Voronoi圖來創(chuàng)建的，并根據(jù)每個單元格的點與方框中隨機(jī)選擇的點的距離進(jìn)行著色。  圖源：Francesco Bellelli 好，既然了解了具體的背景和案例，接下來我們了解下關(guān)于Voronoi的數(shù)學(xué)原理。 02 數(shù)學(xué)定義及其性質(zhì) 首先，我們定義一些術(shù)語：
我們需要計算平面上任意一點  兩點之間的距離公式 用公式表示就是：  這里，x=(x1,x2) 和 pi=(pi1,pi2) 雖然數(shù)學(xué)定義聽起來復(fù)雜，但我們可以用簡單的例子來理解。 假設(shè)我們有三個種子點p1,  假如我們想知道一個點x=(5,4) 屬于哪個沃羅諾伊單元，該怎么計算呢？ 好，接下來我們先計算距離：  綜上所述就會發(fā)現(xiàn)，d(x,p2)和d(x,p3)都是根號5，均比d(x,p1)等于根號20要小，所以點x=(5,4)屬于p2和p3的分界線上！ 好，這時候我們再看看關(guān)于沃羅諾伊單元定義就懂了：  二十個點和沃羅諾伊單元格 03 Voronoi圖的其他算法及應(yīng)用 如果你是機(jī)器學(xué)習(xí)領(lǐng)域的開發(fā)人員，應(yīng)該會很熟悉K近鄰算法。 很簡單，其實k-NN 算法是一種基于距離的分類和回歸算法。 給定一個待分類點，k-NN 算法會找到離該點最近的 k 個點，然后根據(jù)這些點的標(biāo)簽或數(shù)值來決定待分類點的類別或數(shù)值。 k-NN算法用于分類、回歸和聚類問題，通過訓(xùn)練數(shù)據(jù)集中的k個最接近的例子進(jìn)行值預(yù)測。 由于Voronoi圖將空間劃分為包含與每個種子點最近的多邊形，Voronoi單元的邊界完全對應(yīng)于1-最近鄰問題的決策邊界。 所以機(jī)器學(xué)習(xí)也不難，它里面的很多算法也是基于很多前置數(shù)學(xué)基礎(chǔ)。 另外，還有一種建模方式——德勞內(nèi)三角化。 德勞內(nèi)三角化是Voronoi圖的對偶圖，通過連接每個點與相鄰單元中的點，可以得到德勞內(nèi)三角化的圖。 如下圖：這種三角化具有使三角形的最小角度最大化的特性，避免了非常銳角的三角形，非常適合用于建模曲面和物體。 帶德勞內(nèi)三角化的Voronoi圖 勞埃德松弛算法是一種與Voronoi圖相關(guān)的實用算法，通過交替構(gòu)建Voronoi圖和尋找每個細(xì)胞的質(zhì)心，不斷迭代生成更均勻的Voronoi單元。 經(jīng)過多次迭代，單元格會趨向于更圓的形狀，點的分布更加均勻，最終形成質(zhì)心Voronoi圖。 Delaunay 三角形的構(gòu)造使得任何一個點都不會落在圍繞每個三角形的圓圈內(nèi)。來源: Wiki 勞埃德算法在數(shù)據(jù)科學(xué)中作為K平均算法的基礎(chǔ)，被廣泛應(yīng)用于聚類分析。此外，它還用于生成平滑的網(wǎng)格、圖像抖動以及程序化地圖生成。 如何構(gòu)造Voronoi圖？ 可以通過逐個構(gòu)建每個細(xì)胞來構(gòu)造Voronoi圖，方法是延伸連接每個點組合的片段的平分線。 然而，這種技術(shù)效率低下，因此提出了更有效的替代方案。 例如，掃線算法通過二叉查找樹和優(yōu)先級隊列操作逐步構(gòu)建Voronoi單元，德勞內(nèi)三角化技術(shù)也可以用于構(gòu)建Voronoi圖。 結(jié)語 Voronoi圖不僅是一種數(shù)學(xué)工具，更是一種自然與藝術(shù)的表達(dá)形式。 它們在自然界中廣泛存在，從微觀細(xì)胞到宏觀建筑，無處不在的Voronoi圖展示了自然界和人類智慧的奇妙聯(lián)系。 好，今天就先這樣啦～ 好，今天先這樣啦～ 科學(xué)羊?? 祝幸福~ 「感恩關(guān)注，科學(xué)羊持續(xù)為您帶來最好的科普知識」 |
|
|
