檢查的點是一個4點的凸包

Question

我有個問題，證明如果一個數4點能形成的凸包內，並且如果第五點是船體內部或沒有。我設法使用三角形來解決凸包的問題，​​但是我不知道如何證明第5點是否在由其他4點創建的船體內部。

任何想法？

謝謝！

Answer 1

假設你問點在一個平面上 - 沒有任何多邊形（凸或不）與任意數量的頂點的standard approach。

Answer 2

打電話給你的要點a，b，c，d。它們形成一個四面體。 如果四面體不退化，則這些點是它們凸包的頂點（極值點）。

要進行檢查，檢查是否有，B，C形成非退化的三角形。爲此，計算三角形（b-a）交叉（c-a）的法向量（稱爲n）。如果它爲零則三角形退化，否則它不是.. 檢查d是否不在此三角形的平面中。這是如果（d-a）與n的點積是零。如果是這樣，四面體退化。

計算四面體的4個三角形中每一個的法向量。每個法向量與三角形的（任意）點一起描述一個半空間;即，飛機一側的所有點。 設n是法向量，p是三角形的一個點。

的點Q被認爲是半空間的內部，如果n點（Q - P）爲負。

檢查所有4個三角形，如果第四個點在裏面。如果不是，則調整法向量的符號。

一個點位於四面體內部，如果它位於所有4個半空間的內部。

Answer 3

如果你能找到的四個點的凸包，那麼你就能夠通過對角的兩個三角形分割四邊形（除非點之一是內部，那麼你已經離開了一個三角形）。

所以這一切都相當於一個三角形點測試。

同樣，能夠構建一個凸包，你必須已經具有區域試驗得心應手（三角形面積的符號）。當區域測試報告由給定三角形的點和三條邊形成的三個三角形的相同符號時，第五點位於給定三角形內。