凹面船體在邊界上取多邊形的所有點

Question

在我的工作中，我必須在邊界中包含一些隨機點。凸包正在採取額外的空間，並沒有嚴格的形狀，所以我修改它放寬以下方式邊緣：

ⅰ）畫出凸包點爲在給定數量。

II）現在對凸包邊界檢查每個點不如果它可以被添加到（當然，改變邊界整形）的邊界，同時確保沒有任何給定的點在於新的外多邊形形狀。 （在多邊形算法點）

ⅲ）如果所有的點位於多邊形重複步驟2對於一些其它點的內部。

iv）如果沒有更多的點可以包括在邊界上，停止。現在

，這個問題是在任何樣品的測試集，越來越包括在邊界內的所有點。我的疑惑是：

i）這是一個凹形的船體嗎？

II）這怎麼不同，如果我只是在安排逆時針順序給點意見，並通過所有的人，而不是先繪製一個凸包繪製和多邊形？

III）這是真的，對點的任何給定的電話號碼，我可以通過他們得出一個非自相交多邊形，這樣所有的點位於多邊形的邊界？

Answer 1

假設你有興趣在一個2D多面體（也可以是第二;！它只是更容易解釋和可視化2D），你需要找到一組點的四個Pareto frontiers，這會導致您正在尋找的「非主導」船體。爲什麼四個邊界？考慮下面

注意的例子，你需要四個邊界（最大值與最大值，最小值與最大值，最大主場迎戰分鐘，分鐘對分）完全定義的多面體的邊緣。此外，請注意，船體是否凸出取決於你的觀點。上面的例子顯示了一個非凸和不連續的邊界，因此，多面體不是凸的，也不是連續的。四個帕累託邊界的集合包含完整的多面體形狀。

如果你正在尋找這個工具自己，這是不是太糟糕，只是要求每個點比較對每個點比較它們的軸，並確定哪些點在有利的方向前進兩個軸。這被稱爲兩兩比較。

對於C++已經編碼的解決方案，這應該是啓動https://github.com/kevinduh/pareto