以x，y位置的形式獲取三角形內的位置列表

假設我有一個由三個整數頂點（x1，y1），（x2，y2）和（x3，y3）給出的三角形。我可以使用什麼樣的算法來返回位於三角形內部的ALL（x，y）整數對的全面列表。以x，y位置的形式獲取三角形內的位置列表

2012-01-21 CodeGuy

這將是無限的點數，除非您施加一些一種約束，例如座標是整數？ –

請註明。如果@PaulR是對的，解決方案與我在我的回答中提出的建議非常不同。 –

你強調你想要所有的對，但顯然有很多是不計其數的。你是指整數對嗎？在這種情況下，這是光柵化的問題，關於這個問題有大量的文獻。這是一個很好的教程：http://joshbeam.com/articles/triangle_rasterization/您可能需要調整它，這取決於您在'inside'中的含義，因爲我不知道是否要包含邊界。 – sigfpe

下面的算法應該是合適的：

排序的三角形頂點按x座標遞增。現在我們在一側（頂部或底部）有兩個線段（1-2和2-3），另一個線段（1-3）。線的方程（其含有鏈段）的

計算係數：

A * x + B * y + C = 0 
A = y2 - y1 
B = x1 - x2 
C = x2 * y1 - x1 * y2

有（X1，Y1）和（X2，Y2）是線的兩個點。

對於每個範圍[X1，X2），（X2，X3]和X2（特殊情況）遍歷整數個範圍，然後針對每x如下：
1. 查找頂部結合作爲y_top =（ - A1 * x - C1）div B1。
2. 查找下邊界爲y_bottom =（ - A2 * y - C2 - 1）div B2 +1。
3. 將（x，y_bottom）和（x，y_top）。

該算法不適用於嚴格的內部頂點。對於嚴格的內部頂點項目3.1和3.2略有不同。

來源

2012-01-22 23:07:51 citxx

我想你有一個你想測試的對子列表（如果這不是你的問題所在，請清楚地說明你的問題）。您應該首先將這些對存儲爲四叉樹或kd-tree結構，以便擁有足夠小的候選集合。如果你有幾分，這可能是不值得的麻煩（但如果你不這樣做，它不會很好地擴展）。

您還可以通過針對三角形的邊界框進行測試來縮小候選範圍。

然後，對每個候選對(x, y)，解決a, b, c系統

a + b + c = 1 
a x1 + b x2 + c x3 = x 
a y2 + b y2 + c y3 = y

（我讓你工作了這一點），並且這個點在三角形內，如果ab和c都是積極的。

來源

2012-01-21 22:00:42

我喜歡光線投射，很好地描述在this Wikipedia article。在我的項目中用於相同的目的。該方法也可以在其他多邊形上縮放，包括凹面。不知道性能，但很容易被編碼的，所以你可以自己嘗試一下（我在我的項目中沒有性能問題）

來源

2012-01-22 21:53:26

此問題的正確名稱是三角形rasterization。

這是一個研究得很好的問題，有很多方法可以做到這一點。兩種流行的方法是：

掃描線掃描線。

對於每條掃描線，您都需要一些基本幾何圖形來重新計算該行的開始和結束。見Bresenham's Line drawing algorithm。
測試邊界框中的每個像素以查看它是否在三角形中。

這通常通過使用barycentric座標來完成。

大多數人認爲方法1）是因爲你不浪費時間測試像素，可以是三角形外，大約在邊框中的所有像素的一半以上有效。但是，2）有一個主要優勢 - 它可以更容易地並行運行，所以對於硬件來說通常是更快的選擇。 2）編碼也更簡單。

用於描述如何使用方法2的原始paper由Juan Pineda於1988年撰寫，被稱爲「多邊形柵格化的並行算法」。

對於三角形，它在概念上非常簡單（如果你學習重心協調）。如果將每個像素轉換爲三角形重心座標，alpha，beta和gamma - 那麼簡單測試就是alpha，beta和gamma必須介於0和1之間。

來源

2012-01-22 23:28:16

以x，y位置的形式獲取三角形內的位置列表

回答

相關問題