Python - 具有一些允許的內部點的凸面船體

Question

我想製作一組2D點（在Python中）的凸包。我發現了幾個有幫助的例子，但我有一個額外的功能，我希望我不能實現。我想要做的是創建凸包，但如果它們足夠靠近邊界，則允許它拾取內點。看到下面的圖片 - >如果theta < x度，那​​麼內部點被添加到船體。

明顯這可以讓事情變得更復雜一點，因爲我已經從我的想法和測試中發現的。例如，如果內部點被添加，則它可能允許添加另一個內部點。

速度在這裏並不是一個真正值得關注的問題，因爲我將要使用的點數相對較少。我寧願有一個更強大的算法，然後快速。

我想知道是否有人知道任何這樣的例子，或者可以指出我從哪裏開始的正確方向。謝謝。

Answer 1

Concave hull可能是你要找的東西，儘管它並沒有使用一個角度，據我所知。 the LOCAL project使用的算法似乎使用k個最近的鄰居。

Answer 2

您可以首先計算凸包，然後破壞圓的邊緣，看看是否有任何邊應該被打破以包含內點。

Answer 3

您正在尋找的概念可能是字母形。調整阿爾法，你承認或多或少凹點你的凹殼。 Look at Edelsbrunner algorithm爲alpha形狀發現。