資源描述：
《淺談多邊形與多邊形關(guān)系的判斷》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。
1、淺談多邊形與多邊形關(guān)系的判斷一、區(qū)域與多邊形我們這里所說的區(qū)域是指由邊界形成的一個封閉的區(qū)域（閉域），區(qū)域內(nèi)的點是連貫的，即內(nèi)部任意兩點都可以通過一條折線連接在一起。我們所說的多邊形由線段依次首尾相連，組成一個封閉的區(qū)域，且線段之間除首尾相連外與其他線段沒有任何連接。沿著組成多邊形的線段一個方向行走，多邊形所組成的封閉區(qū)域內(nèi)部的點都在線段的一側(cè)。線段兩側(cè)分別是區(qū)域內(nèi)點和區(qū)域外點。二、幾何分析（一）區(qū)域與區(qū)域我們比對區(qū)域，區(qū)域主要有相同、相離、相切（內(nèi)切、外切）、相交、包含幾種關(guān)系。表一區(qū)域與區(qū)域的關(guān)系序號類型特點備注1相同組成兩個區(qū)域的點是同序或反序相連的
2、2相離區(qū)域之間沒有交點，且任何一個區(qū)域的任何一個頂點都不在另外區(qū)域的邊上和內(nèi)部點都在對方區(qū)域外部，且邊不相交。3外切兩個區(qū)域的邊有共同點，但是任何一個區(qū)域的頂點都不在另一個區(qū)域內(nèi)部（頂點在線端上我們認為也是相切）。兩個區(qū)域的邊有共同點，且任何一個區(qū)域的點都不在另外一個區(qū)域內(nèi)部，同時沒有邊相交。4相交兩個區(qū)域有共有部分，且有非共有部分。兩個區(qū)域的線段之間有交點；或者一個區(qū)域的頂點在另一個區(qū)域內(nèi)外都有5內(nèi)切兩個區(qū)域的邊有共同點，但是其中一個區(qū)域的頂點在另一個區(qū)域內(nèi)部（頂點在線端上我們認為也是相切）。6包含一個區(qū)域的所有頂點都在另外一個區(qū)域內(nèi)部，且邊沒有相交。為
3、了便于分析，我們設(shè)定區(qū)域都是按照順時針方向排列頂點，即所有區(qū)域的內(nèi)部都在當(dāng)前邊的右側(cè)。我們首先判斷區(qū)域相交的情況，區(qū)域相交必定是兩個區(qū)域存在同時包含和互補包含的部分，又因為區(qū)域內(nèi)部點是有邊界（即線段）來分割的，在區(qū)域的相交必定是邊界的相交，即是在一個區(qū)域的邊界的左右兩邊同時出現(xiàn)另一個區(qū)域的邊界。通過分析，我們可以發(fā)現(xiàn)只有以下幾種情況，表二區(qū)域相交情況序號類型特點例圖1普通相交組成兩個區(qū)域的線段相交2頂點與邊相交組成一個區(qū)域的其中一個線段的端點在組成另一個區(qū)域的線段上。3頂點相交兩個區(qū)域的線有共同頂點，且頂點處組成兩個區(qū)域的線段是依次在交點交錯分布的。4共同
4、邊相交組成兩個區(qū)域的線段有共同部分，且一個區(qū)域的邊界左右分布了另一個區(qū)域的邊界。從表二我們可以看出，區(qū)域相交就是多邊形相交，可以轉(zhuǎn)換為線段與線段的關(guān)系。區(qū)域相切，我們分為內(nèi)切、外切。當(dāng)區(qū)域內(nèi)切時，內(nèi)部區(qū)域被外部區(qū)域包裹，并且內(nèi)部區(qū)域與外部區(qū)域有共同點或邊。當(dāng)外切時，兩個區(qū)域都不包含對方區(qū)域內(nèi)容，但是兩個區(qū)域有共同的邊或點。當(dāng)區(qū)域內(nèi)切或外切的同時又有相交部分時，我們認為兩個區(qū)域是相交的。表三區(qū)域內(nèi)、外切序號類型條件一條件二條件三例圖1內(nèi)切當(dāng)A、B區(qū)域沒有相交部分時，如果A區(qū)域和B區(qū)域有共同的頂點或共同邊或一個區(qū)域的頂點在另一個區(qū)域邊上A區(qū)域另一部分頂點在B區(qū)
5、域內(nèi)部B區(qū)域另一部頂點在A區(qū)域外部，2如A區(qū)域所有頂點都在B區(qū)域邊上或頂點，B區(qū)域另一部頂點在A區(qū)域外部當(dāng)A區(qū)域存在內(nèi)部點也在B區(qū)域內(nèi)部時，兩區(qū)域內(nèi)切3外切當(dāng)A區(qū)域存在內(nèi)部點不在B區(qū)域內(nèi)部時4A區(qū)域另一部端點在B區(qū)域外部B區(qū)域另一部端點在A區(qū)域外部當(dāng)一個區(qū)域的所有頂點在另一個區(qū)域邊（端點）上時，我們無法利用區(qū)域具有線段和頂點之間的關(guān)系來判斷兩個區(qū)域是內(nèi)切或外切。因為一個區(qū)域所有端點在另一個區(qū)域上，所以一個區(qū)域必是被另一個區(qū)域包圍（外切）或包裹（內(nèi)切），如果被包圍（被包裹）的區(qū)域的任何一點在外部區(qū)域內(nèi)，說明兩個區(qū)域有共同內(nèi)部點，則兩個區(qū)域必是內(nèi)切，否則兩個區(qū)
6、域必是外切。我們需要從被包圍（被包裹）的區(qū)域內(nèi)找到一點。我們可以利用一條通過該區(qū)域最大橫軸值和最小橫軸值中間點的直線與該區(qū)域所有邊（線段）的交點，按照交點的縱軸值從大（?。┑叫。ù螅┮来闻判?，然后依序選擇點與點之間的中間值，則該中間值集與橫軸中間點組成的點集必存在一個該區(qū)域內(nèi)部的點（即使該過中間點直線經(jīng)過了該區(qū)域的一條是垂直橫軸的邊，該結(jié)論也是成立的），找到這個點就可以與外部區(qū)域進行判斷，以確定是外切還是內(nèi)切。通過以上分析，我們可以知道區(qū)域與區(qū)域的關(guān)系，我們可以利用線段與線段、點與區(qū)域的關(guān)系來判斷。（二）線段與線段我們將線段與線段的關(guān)系分為五種，相同、相交
7、、相連、和相切、相離。相同即兩條線段有共同的端點。相交即兩個線段之間有交點，但交點不在兩個線段的共同端點。相連即兩條線段通過端點首尾相連。相切，我們認為一個線段的端點在另外一個線段的上，且在端點之間。相離即兩條線段之間沒有任何共同的部分。我們利用線段之間的關(guān)系來判斷區(qū)域之間的關(guān)系時，只是利用線段是否相交這一特性，區(qū)域相切我們是利用點與區(qū)域之間的關(guān)系來判斷的，所以，這里我們只討論線段與線段相交如何判斷。判斷線段是否相交，有許多方法，在程序設(shè)計中，我們一般不采用除法算法，避免溢出，在這里我們選取容易理解并且執(zhí)行效率相等較高的向量叉積判斷法。我們認為兩條線段是有
8、向的線段即向量。向量的叉積是以兩條向量為鄰邊的平行四邊形的面積。由
