首頁(yè) 猿問(wèn) 如何確定點(diǎn)是否在二維三角形中？

如何確定點(diǎn)是否在二維三角形中？

算法數(shù)學(xué)

白板的微信 2019-06-15 11:34:15

如何確定點(diǎn)是否在二維三角形中？是否有一個(gè)簡(jiǎn)單的方法來(lái)確定一個(gè)點(diǎn)是否在一個(gè)三角形內(nèi)？它是二維的，不是3D的。

查看完整描述

3 回答

一只斗牛犬

TA貢獻(xiàn)1784條經(jīng)驗(yàn) 獲得超2個(gè)贊

解下列方程組：

p = p0 + (p1 - p0) * s + (p2 - p0) * t

重點(diǎn)p在三角形內(nèi)，如果0 <= s <= 1和0 <= t <= 1和s + t <= 1.

s,t和1 - s - t被稱(chēng)為重心坐標(biāo)重點(diǎn)p.

反對(duì) 回復(fù) 2019-06-15

慕尼黑的夜晚無(wú)繁華

TA貢獻(xiàn)1864條經(jīng)驗(yàn) 獲得超6個(gè)贊

我同意安德烈亞斯·布林克，以重心為中心的坐標(biāo)對(duì)此任務(wù)非常方便。請(qǐng)注意，不需要每次求解方程系統(tǒng)：只需計(jì)算解析解即可。使用安德烈亞斯“表示法，解決辦法是：

s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);

哪里Area是三角形的(簽名)區(qū)域：

Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);

只是評(píng)估一下s, t和1-s-t..重點(diǎn)p是三角形的當(dāng)且僅當(dāng)它們都是正的。

編輯：請(qǐng)注意，該區(qū)域的上述表達(dá)式假定三角形節(jié)點(diǎn)編號(hào)是逆時(shí)針?lè)较虻?。如果編?hào)是順時(shí)針?lè)较虻?，則此表達(dá)式將返回一個(gè)負(fù)區(qū)域(但大小正確)。測(cè)試本身(s>0 && t>0 && 1-s-t>0)并不取決于編號(hào)的方向，因?yàn)樯厦娴谋磉_(dá)式乘以1/(2*Area)如果三角形節(jié)點(diǎn)方向發(fā)生變化，也要更改符號(hào)。

編輯2：要獲得更高的計(jì)算效率，請(qǐng)參見(jiàn)COPROC下面的注釋(它指出，如果預(yù)先知道三角形節(jié)點(diǎn)(順時(shí)針或逆時(shí)針)的方向，則按2*Area在表達(dá)式中s和t可以避免)。另見(jiàn)阿祖爾注釋中的jspldle-代碼安德烈亞斯·布林克答案。