用耳夾有問題

Question

我遇到的問題是因爲我無法確定一個凹陷的三角形與實際上應該被切掉的耳朵。

我怎樣才能區分凸三角和凹三角？

Answer 1

三角形不能凹。你的意思是你的網格是凹的嗎？

---

我沒有意識到你在談論某種特定技術。在做了一點研究之後，我想我理解你的問題就足以嘗試一個答案。

假設您以逆時針順序遍歷多邊形的頂點。如果我們按照這個順序遍歷它們，多邊形的主體總是在左邊。我們正在考慮三個頂點：A,B和C。想象一下，我們從A通過B拍攝射線。如果C在該射線的左側，那麼這是一個形狀良好的三角形，它是多邊形的一部分。如果C在該射線的右側，則它代表負空間。

行，因此讓我們創建矢量v（其爲甲→乙）和瓦特（其爲乙→Ç）。另外，我們構建v'，這是v，但CCW旋轉了90度。 V」 = < -v [Y]，V [X]>

爲了找出Ç是否是到v的左側或右側，我們只需要測量之間的角度v'和w。如果它在（0,90）或（270,360）之內，那麼它在左邊。如果它在（90,270）之內，那麼它在右邊。這是很方便的，因爲它恰好對應於cos（θ）> 0和cos（θ）分別爲0的地方。所以，如果cos（θ）> 0，那麼C在左邊，並且如果cos（θ），則C在右邊。

我們可以使用點積來幫助我們確定cos（Θ）。請記住，COS（Θ）=（V '•瓦特）/（MAG（V'）⋅MAG（瓦特））。然而，我們實際上並不需要cos（Θ），我們只需要符號（cos（Θ））。由於mag（v'）和mag（w）必須都是正面的，所以我們可以忽略它們。因此，如果v'•w> 0，則C在左邊，三點對應於作爲多邊形一部分的三角形。另一方面，如果是0，則C在右邊，三個點對應於多邊形外部的負空間。

我實際上沒有嘗試過這種超越簡單的測試，但我相信它（或接近它的東西）將工作。噢，對於其他誰（像我一樣）從來沒有聽說過這種技術，你可以閱讀關於它的文章here。