尋找一個點是否在由一組點產生的凸殼

尺寸通常爲10〜30D

該組的大小是小的，通常爲2〜10

我需要的任務是判斷一個點是否是從構成的凸包內點集。

什麼是一些算法來執行，還是有，我可以用任何現有的庫

2016-08-15 Alaya

您不需要構造凸包以查看點是否位於其中。只需解決一個線性規劃問題，查看是否可以通過對點集合進行線性組合來生成該點，其中所有係數都在[0,1] – mcdowella

範圍內;而在二維中，凸包可以表示爲一個多邊形和一些[算法]（https://en.wikipedia.org/wiki/Quickhull）是衆所周知的，我不清楚在一個更高維度的合適數據結構中如何表示凸包;請澄清所需的表示。 – Codor

mcdowella是正確的，在你的情況下，你想避免計算完整的凸包（時間複雜度隨着D指數增長）。如果因爲其他原因需要構建凸包，可以使用[CGAL]（http://doc.cgal.org/latest/Convex_hull_d/index.html）。 – geoalgo

注：算法的這些原始草圖，它需要revision.It可以輸出錯誤的結果（見下面的評論）

以下是針對您的問題的多種可能解決方案之一。

讓D - 你的空間的維度，N - 你的點數。您可以使用以下算法：

您應該爲空間的每個座標平面計算投影凸包。你會得到D凸殼。這一步的複雜性是D * N * log N

然後你應該測試一下，你的每個投影點是否位於每個專用凸包的內部。該步驟的複雜度爲d * N（使用本地算法）

總體執行復雜性= d * N *登錄N.

注意：該算法的基本思想是歸結計算上平面凸包具有以下測試點的位置。

P.S.當然，你可以得到一些退化的情況，凸包可以是線段或只是點。但這些情況可以容易處理

P.P.S.此算法僅允許檢查點是位於凸包內部還是位於其邊界內

2016-08-17 14:50:27 LmTinyToon

確實，標題詢問計算凸包，但這是誤導性的 - 問題闡明瞭只有包含/排除是必要的。這可以在不計算凸包本身的情況下完成。 –

我同意你的意見。但這取決於他解決問題的方式。當然，作者可能不會計算凸包來解決這個任務（使用上面例子中的線性規劃）。但我認爲我的算法可以很容易地實現。注意：它不涉及計算多維凸包。它使用輔助投影來測試點的位置。 – LmTinyToon

請不要誤解我的意思 - 我不是在批評你的好答案。由於您在撰寫答案時的標題具有誤導性，因此我想添加評論（可能對未來的讀者）。在這裏，有一個upvote。 –

回答