我猜題主想要的是這種效果吧？

這是一個(gè)典型的由凸包(Convex Hull)問(wèn)題衍生出來(lái)的

問(wèn)題。

1.凸包是什么

對(duì)包含n個(gè)點(diǎn)的集合S來(lái)說(shuō)，凸包可以看作是所有包含這n個(gè)點(diǎn)的閉合半平面的交集。在在二維歐幾里得空間中，可以把凸包想象成用一根有彈性的橡皮筋恰好包住所有的點(diǎn)

2.如何求解凸包

1)Gift wrapping算法：假設(shè)平面內(nèi)共有n個(gè)點(diǎn)，對(duì)點(diǎn)Pi(0<=i<=n),從最左邊的點(diǎn)i=0開(kāi)始，遍歷所有的點(diǎn)，找到點(diǎn)Pi+1，使得剩下的n-2個(gè)點(diǎn)全部在直線(xiàn)PiPi+1的右邊，重復(fù)這一過(guò)程直到回到點(diǎn)P0。

2)Graham scan算法：找到n個(gè)點(diǎn)的集合S中位于最下方的點(diǎn)(縱坐標(biāo)最小)P，分別計(jì)算剩下n-1個(gè)點(diǎn)與點(diǎn)P連線(xiàn)的斜率，按大小將這些點(diǎn)的編號(hào)排序，維護(hù)一個(gè)棧，以保存當(dāng)前的凸包。按排序得到的結(jié)果，依次將點(diǎn)加入到棧中，如果正在考慮的點(diǎn)與棧頂?shù)膬蓚€(gè)點(diǎn)不是“向左轉(zhuǎn)”的，就表明當(dāng)前棧頂?shù)狞c(diǎn)并不在凸包上，而我們需要將其彈出棧，重復(fù)這一個(gè)過(guò)程直到正在考慮的點(diǎn)與棧頂?shù)膬蓚€(gè)點(diǎn)是“向左轉(zhuǎn)”的。判斷是不是“向左轉(zhuǎn)”使用的方法是求三點(diǎn)構(gòu)成的三角形的有向面積，當(dāng)有向面積為正是，判斷它是“向左轉(zhuǎn)”，為負(fù)時(shí)“向右轉(zhuǎn)”，等于零時(shí)三點(diǎn)共線(xiàn)。圖2中以BC為頂點(diǎn)，在考慮點(diǎn)D是發(fā)現(xiàn)它是向右轉(zhuǎn)的，所以點(diǎn)C不是凸包上的點(diǎn)，把它從棧中彈出

3.凸包的優(yōu)點(diǎn)和缺點(diǎn)

1)優(yōu)點(diǎn)：可以很方便地求得一個(gè)點(diǎn)集的邊界，適合用于3D游戲中的碰撞檢測(cè)。

2)缺點(diǎn)：并不能很好地描述點(diǎn)集的形狀。凸包不能很好地描述點(diǎn)集形狀

4.

由于構(gòu)建凸包的算法已經(jīng)十分成熟且容易，凸包問(wèn)題被用來(lái)解決很多更復(fù)雜的問(wèn)題，尤其是計(jì)算機(jī)科學(xué)中，其應(yīng)用相當(dāng)廣泛。在模式識(shí)別中，科學(xué)家發(fā)現(xiàn)，通過(guò)選取極值點(diǎn)構(gòu)建凸包，可以表征某一個(gè)集合的“形狀”。然而，由于凸包本身的缺點(diǎn)，這種表示是相當(dāng)不精確的。這也是題主發(fā)現(xiàn)很多凸包會(huì)重合在一起的原因。為了解決這一問(wèn)題，Herbert Edelsbrunner等人于1983年提出了alpha-shape(為了方便，后文都寫(xiě)作a-shape)的概念。alpha-shape可以很好地表示一個(gè)點(diǎn)集的形狀

要定義a-shape，首先需要引入幾個(gè)概念。

定義1：對(duì)于點(diǎn)集S來(lái)說(shuō)，取一個(gè)足夠小且大于0的任意實(shí)數(shù)a，所有半徑為1/a且包含了全部點(diǎn)的圓的交集我們稱(chēng)其為點(diǎn)集S的Postive a-hull。點(diǎn)集S的ostive a-hull

定義2：對(duì)于點(diǎn)集S來(lái)說(shuō)，取一個(gè)足夠大且小于0的任意實(shí)數(shù)a，對(duì)所有半徑為-1/a的圓，若其補(bǔ)集包含了點(diǎn)集S中的所有點(diǎn)，對(duì)這樣的圓的補(bǔ)集，求它們(圓的補(bǔ)集)的交集，我們稱(chēng)這個(gè)交集為點(diǎn)集S的Negative a-hull。點(diǎn)集S的Negative a-hull

定義3：對(duì)于點(diǎn)集S中的某一點(diǎn)p，如果存在一個(gè)半徑為1/a的圓，點(diǎn)p在圓上，且該圓包含了點(diǎn)集S中所有的點(diǎn)，則稱(chēng)點(diǎn)p為點(diǎn)集S的a-extreme極值點(diǎn)。如果點(diǎn)集S中存在這樣的兩個(gè)a-extreme極值點(diǎn)p和q，使得p和q在同一個(gè)圓上，且該圓包含了點(diǎn)集S中的所有極值點(diǎn)，則稱(chēng)這樣的點(diǎn)p和點(diǎn)q為一對(duì)a-neighbors。

定義4：給出一個(gè)點(diǎn)集S，和一個(gè)任意實(shí)數(shù)a，點(diǎn)集S的a-shape是由直線(xiàn)段連成的封閉圖形，這些直線(xiàn)段滿(mǎn)足：線(xiàn)段的頂點(diǎn)是a-extreme極值點(diǎn)，線(xiàn)段連接的兩個(gè)頂點(diǎn)是一對(duì)a-neighbors。

好了，這樣我們就得到了a-shape的定義了，剩下的就是如何求解a-shape。

5.a-shape的求解

在《On the shape of a set of points in the plane》一文中，Herbert Edelsbrunner證明了a-shape是Delaunay Triangulation的子集，并給出了利用Voronoi Diagrams和Delaunay Triangulation聯(lián)合求解a-shape的過(guò)程，具體如下：

1)給定一個(gè)點(diǎn)集S和參數(shù)a

2)構(gòu)建點(diǎn)集S的Delaunay Triangulation，得到每一條直線(xiàn)段

的長(zhǎng)度

3)構(gòu)建點(diǎn)集S的Voronoi Diagram，利用Voronoi Diagram計(jì)算每?jī)蓚€(gè)點(diǎn)間距離的極值

和

4)當(dāng)且僅當(dāng)

時(shí)，這條直線(xiàn)段屬于a-shape的一部分

5)計(jì)算得到所有滿(mǎn)足要求的直線(xiàn)段

，得到的圖形就是我們要求的

總結(jié)

以上是生活随笔為你收集整理的python散点图如何设置外边框_如何绘制散点图的外围边框？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。