淺談多邊形與多邊形關(guān)系的判斷

淺談多邊形與多邊形關(guān)系的判斷區(qū)域與多邊形我們這里所說的區(qū)域是指由邊界形成的一個(gè)封閉的區(qū)域（閉域），區(qū)域內(nèi)的點(diǎn)是連貫的，即內(nèi)部任意兩點(diǎn)都可以通過一條折線連接在一起。我們所說的多邊形由線段依次首尾相連，組成一個(gè)封閉的區(qū)域，且線段之間除首尾相連外與其他線段沒有任何連接。沿著組成多邊形的線段一個(gè)方向行走，多邊形所組成的封閉區(qū)域內(nèi)部的點(diǎn)都在線段的一側(cè)。線段兩側(cè)分別是區(qū)域內(nèi)點(diǎn)和區(qū)域外點(diǎn)。幾何分析（一）區(qū)域與區(qū)域我們比對(duì)區(qū)域，區(qū)域主要有相同、相離、相切（內(nèi)切、外切）、相交、包含幾種關(guān)系。表一區(qū)域與區(qū)域的關(guān)系序號(hào)類型特點(diǎn)備注1相同組成兩個(gè)區(qū)域的點(diǎn)是同序或反序相連的2相離區(qū)域之間沒有交點(diǎn)，且任何一個(gè)區(qū)域的任何一個(gè)頂點(diǎn)都不在另外區(qū)域的邊上和內(nèi)部點(diǎn)都在對(duì)方區(qū)域外部，且邊不相交。3外切兩個(gè)區(qū)域的邊有共同點(diǎn)，但是任何一個(gè)區(qū)域的頂點(diǎn)都不在另一個(gè)區(qū)域內(nèi)部（頂點(diǎn)在線端上我們認(rèn)為也是相切）。兩個(gè)區(qū)域的邊有共同點(diǎn)，且任何一個(gè)區(qū)域的點(diǎn)都不在另外一個(gè)區(qū)域內(nèi)部，同時(shí)沒有邊相交。4相交兩個(gè)區(qū)域有共有部分，且有非共有部分。兩個(gè)區(qū)域的線段之間有交點(diǎn)；或者一個(gè)區(qū)域的頂點(diǎn)在另一個(gè)區(qū)域內(nèi)外都有5內(nèi)切兩個(gè)區(qū)域的邊有共同點(diǎn)，但是其中一個(gè)區(qū)域的頂點(diǎn)在另一個(gè)區(qū)域內(nèi)部（頂點(diǎn)在線端上我們認(rèn)為也是相切）。6包含一個(gè)區(qū)域的所有頂點(diǎn)都在另外一個(gè)區(qū)域內(nèi)部，且邊沒有相交。為了便于分析，我們?cè)O(shè)定區(qū)域都是按照順時(shí)針方向排列頂點(diǎn)，即所有區(qū)域的內(nèi)部都在當(dāng)前邊的右側(cè)。我們首先判斷區(qū)域相交的情況，區(qū)域相交必定是兩個(gè)區(qū)域存在同時(shí)包含和互補(bǔ)包含的部分，又因?yàn)閰^(qū)域內(nèi)部點(diǎn)是有邊界（即線段）來分割的，在區(qū)域的相交必定是邊界的相交，即是在一個(gè)區(qū)域的邊界的左右兩邊同時(shí)出現(xiàn)另一個(gè)區(qū)域的邊界。通過分析，我們可以發(fā)現(xiàn)只有以下幾種情況，表二區(qū)域相交情況序號(hào)類型特點(diǎn)例圖1普通相交組成兩個(gè)區(qū)域的線段相交2頂點(diǎn)與邊相交組成一個(gè)區(qū)域的其中一個(gè)線段的端點(diǎn)在組成另一個(gè)區(qū)域的線段上。以兩條向量為鄰邊的平行四邊形的面積。由于向量是有方向的，所以叉積也有方向，即正負(fù)。叉積的方向與兩個(gè)相乘向量的的方向符合右手定則，即當(dāng)=時(shí)，當(dāng)右手的四指從以不超過180度轉(zhuǎn)角轉(zhuǎn)向時(shí)，豎起的大拇指指向是的方向。分別從線段A從a和b向線段B的端點(diǎn)c和d引出兩條有向線段、和、，求()*()（叉乘后的積）的結(jié)果，當(dāng)結(jié)果為負(fù)數(shù)時(shí)，線段A的兩個(gè)端點(diǎn)a和b在線段B的兩側(cè)時(shí)；當(dāng)結(jié)果為0時(shí)，a和b至少有1個(gè)點(diǎn)在B所在的直線上；當(dāng)結(jié)果為正數(shù)時(shí)，則線段A的兩個(gè)端點(diǎn)a和b在線段B的同一側(cè)。同理，我們可以判斷線段B的兩個(gè)端點(diǎn)是否在線段A的兩側(cè)，如果線段A的兩個(gè)端點(diǎn)a和b在線段B的兩側(cè)時(shí)，同時(shí)線段B的兩個(gè)端點(diǎn)也在線段A的兩側(cè)，則線段A和B相交，如圖1所示。圖1兩條線段相交2.當(dāng)兩個(gè)區(qū)域有共同點(diǎn)o時(shí)，如果兩個(gè)區(qū)域的兩條邊分別依次交錯(cuò)分布，則兩個(gè)區(qū)域相交，如圖2。圖2共同點(diǎn)的邊圖2中為正值的區(qū)域里只有和其中1條時(shí)，邊相交，否則邊不相交，也可認(rèn)為是相切。當(dāng)為正值的區(qū)域里只有和其中1條時(shí)，即叉乘的向量為正值，同時(shí)叉乘該向量為負(fù)值，角度內(nèi)∠aob內(nèi)只有一條向量（或線段）時(shí)，則邊相交。2.當(dāng)兩個(gè)區(qū)域的邊界有共同邊時(shí)，我們可以認(rèn)為共同邊是一個(gè)點(diǎn)，參照當(dāng)兩個(gè)區(qū)域有共同點(diǎn)o時(shí)判斷，如圖3。圖3共同邊我們向量移動(dòng)就是向量相加存在向量、，我們需要計(jì)算向量和轉(zhuǎn)換成與m的關(guān)系，我們把沿著共同邊位移到點(diǎn)b',則=-=（--）-=--=-（-）-=-，同理，=-，這樣，我們可以將共同邊轉(zhuǎn)換成共同點(diǎn)來判斷了（將、、、轉(zhuǎn)換成、、、）。（三）點(diǎn)與區(qū)域點(diǎn)與區(qū)域的關(guān)系可以分成區(qū)域內(nèi)、區(qū)域外和區(qū)域（邊）上表四點(diǎn)與區(qū)域的關(guān)系序號(hào)類型特點(diǎn)備注1點(diǎn)在區(qū)域外點(diǎn)向上引出射線與區(qū)域邊的交點(diǎn)的個(gè)數(shù)是奇數(shù)2點(diǎn)在區(qū)域內(nèi)點(diǎn)向上引出射線與區(qū)域邊的交點(diǎn)的個(gè)數(shù)是偶數(shù)3點(diǎn)在區(qū)域上點(diǎn)在區(qū)域的邊上從點(diǎn)向上引一條射線，當(dāng)點(diǎn)在區(qū)域內(nèi)時(shí)，則射線和區(qū)域所有邊的交點(diǎn)的個(gè)數(shù)為奇數(shù)；當(dāng)點(diǎn)區(qū)域外時(shí)，則射線和區(qū)域所有邊的交點(diǎn)的個(gè)數(shù)為偶數(shù)。當(dāng)點(diǎn)在區(qū)域的邊上時(shí)，稱點(diǎn)在區(qū)域上。當(dāng)點(diǎn)經(jīng)過一條邊的兩個(gè)端點(diǎn)時(shí)，也分別計(jì)入1次交點(diǎn)。圖4點(diǎn)在區(qū)域內(nèi)圖5點(diǎn)在區(qū)域外通過點(diǎn)向上引出的射線有兩種特殊情況，一種是射線過區(qū)域的一個(gè)頂點(diǎn)，另一種情況是射線過區(qū)域的一條垂直橫軸的邊。圖6射線過區(qū)域頂點(diǎn)圖7射線過區(qū)域的邊當(dāng)射線經(jīng)過區(qū)域的頂點(diǎn)時(shí)，如果經(jīng)過頂點(diǎn)的兩條邊在射線兩側(cè)，則計(jì)3次交點(diǎn)(頂點(diǎn)為始點(diǎn)線段1次，頂點(diǎn)為終點(diǎn)線段1次，再增加1次)，如果經(jīng)過頂點(diǎn)的兩條邊在射線同一側(cè)，則計(jì)2次交點(diǎn)(頂點(diǎn)為始點(diǎn)線段1次，頂點(diǎn)為終點(diǎn)線段1次)；當(dāng)射線經(jīng)過區(qū)域的一條邊，如果與該條邊相接前后兩條邊在射線兩側(cè)，則計(jì)3次交點(diǎn)(垂線段前線段1次，垂線段后線段1次，垂線段1次)，如果與該條邊相接前后兩條邊在射線同一側(cè)，則計(jì)4次交點(diǎn)（垂線段前線段1次，垂線段后線段1次，垂線段1次，再增加1次）。通過以上合計(jì)交點(diǎn)數(shù)也符合點(diǎn)在區(qū)域內(nèi)部時(shí)交點(diǎn)個(gè)數(shù)為奇數(shù)個(gè)，點(diǎn)在區(qū)域外部時(shí)交點(diǎn)個(gè)數(shù)為偶數(shù)個(gè)。（三）點(diǎn)與線段點(diǎn)與線段的關(guān)系序號(hào)類型特點(diǎn)備注1點(diǎn)在線段下方點(diǎn)向上引出射線與線段有交點(diǎn)2點(diǎn)不在線段下方點(diǎn)向上引出射線與線段沒有交點(diǎn)3點(diǎn)在線段上點(diǎn)在線段之間當(dāng)線段所在直線不是垂直線（與點(diǎn)所在射線平行）時(shí)，線段右面點(diǎn)與點(diǎn)的向量和線段左面點(diǎn)與點(diǎn)的向量叉積，為正數(shù)時(shí)，點(diǎn)在線段下部；為零時(shí)，點(diǎn)在線段上；為負(fù)數(shù)時(shí)，點(diǎn)在線段上部。當(dāng)線段所在直線是垂直線時(shí)，點(diǎn)在下方點(diǎn)下部則點(diǎn)在線