將最大凸包裝到一組點的內部

我想找到適合於一組點的最大凸包。我有一組大致圓形的點，在我想要適合的圓外有大量離羣點。想象一個帶有「太陽耀斑」的圓圈......我想要適應圓圈並完全忽略耀斑。我已經嘗試了各種合適的撲殺策略，但他們運作得不好。將最大凸包裝到一組點的內部

我搜索了很多，沒有找到解決方案。提前致謝。

2013-05-01 Mark Allen Neil

你可以發佈一個樣本或兩個點的樣子嗎？ – Nuclearman 2013-05-02 04:57:10

你可能想看看[Gabriel graph]（http://en.wikipedia.org/wiki/Gabriel_graph）。這應該至少能夠把你限制在最相關的邊緣。如果你回答上述問題，我可以將其擴展爲答案。 – Nuclearman 2013-05-02 05:07:41

我已經發布了一張[image]（http://i43.tinypic.com/2entj69.jpg）供參考 - 它不完全如我所描述的，但足夠相似。我最終沒有使用alpha形狀，因爲點之間的連通性取決於所選的alpha。太小的alpha可能無法關閉形狀。太大的alpha將排除有效點。我最終做的是通過乘以一個環形面罩，鏡像環形外緣的點，擬合一個凸包，然後再次將該凸包繞在環形環上進行鏡像來掩蓋掉我不想要的數據。完美的作品。 – 2013-05-04 04:29:59

您需要的概念可能是字母形狀。凸包是alpha形狀的一個子集，用於alpha的極值。阿爾法形狀適合一組點，比凸包更接近alpha值。

理論是由Edelbrunner開發的。這是一個好的開始：http://www.mpi-inf.mpg.de/~jgiesen/tch/sem06/Celikik.pdf

對於計算，您必須：計算delaunay三角測量和/或voronoi圖，然後選擇觀察一個條件的點。

例阿爾法形狀：

enter image description here

這實際上是一個凹殼，並且它可以忽略的異常值。

來源

2013-05-01 22:19:45 octoback

不是我正在尋找的東西，但我能夠使用這種策略來獲得足夠的東西來滿足我需要的東西。非常感謝你指導我朝這個方向發展。我發現以下網站對於理解alpha形狀是非常寶貴的--Java applet向你展示瞭如何很好地工作。 http://cgm.cs.mcgill.ca/~godfried/teaching/projects97/belair/alpha.html – 2013-05-02 00:50:04

將最大凸包裝到一組點的內部

回答

相關問題