http://blog.chinaunix.net/uid-26377420-id-3954088.html
2013-10-19
http://blog.sina.com.cn/s/blog_8e6bfecf0100zve9.html 方法1：
從點(diǎn)P向左做射線(xiàn)，計算與多邊形的交點(diǎn)數。如果交點(diǎn)個(gè)數為奇數，點(diǎn)P在多邊形內部；如果交點(diǎn)個(gè)數為偶數，點(diǎn)P在多邊形外部?？梢园慈我忭樞蚩紤]多邊形的每一條邊，來(lái)求取交點(diǎn)的總個(gè)數。
計算時(shí)需要注意：（以邊P1P2為例）
- 如果一個(gè)多邊形頂點(diǎn)以該射線(xiàn)為切線(xiàn)，則直接忽略該頂點(diǎn)（因為射線(xiàn)會(huì )與兩條線(xiàn)段的端點(diǎn)相交，而這兩條線(xiàn)段有一個(gè)共同的端點(diǎn)）；
- 如果邊P1P2水平，射線(xiàn)與其無(wú)交點(diǎn)或有無(wú)數個(gè)交點(diǎn)，該邊也可以直接忽略；
- 如果邊P1P2豎直，很容易判斷是否相交（只能有一個(gè)交點(diǎn)）；
- 判斷相交之前，先判斷P是否在邊P1P2上，如果在，則P在多邊形內部（可根據內部的不同定義更改）。
注意：可以使用bounding box進(jìn)行加速。
方法2：
首先保證多邊形的所有點(diǎn)都有序。然后，做P點(diǎn)到多邊形所有點(diǎn)的連線(xiàn)，計算P點(diǎn)與多邊形所有邊的端點(diǎn)所成的角度（在P點(diǎn)處所成的角）的和（根據邊的頂點(diǎn)位置，求出來(lái)的角度有正有負）。如果所有角度的和等于 2PI ，則點(diǎn)P在多邊形內；否則，點(diǎn)P在多邊形外。
同樣，可以使用bounding box進(jìn)行加速。
判斷一個(gè)點(diǎn)P是否在三角形ABC內：
當點(diǎn)p在三角形abc內時(shí)，4個(gè)三角形的面積滿(mǎn)足：abc = abp + apc + pbc
計算面積使用向量外積：abc = |ab x ac| / 2
而且因為：
pb x pc = (ab-ap) x (ac-ap) = ab x ac - ab x ap - ap x ac
所以公式轉換為：
ab x ac 是否等于 ab x ap + ap x ac + (ab x ac - ab x ap - ap x ac)
本站僅提供存儲服務(wù)，所有內容均由用戶(hù)發(fā)布，如發(fā)現有害或侵權內容，請
點(diǎn)擊舉報。
