[發明專利]一種面面疊加環構造方法

有效

• 申請號: 200810057537.6
• 申請日: 2008-02-02
• 公開（公告）號: CN101499082A
• 公開（公告）日: 2009-08-05
• 發明（設計）人: 閆杰;朱效民;郎兵;方金云
• 申請（專利權）人: 中國科學院計算技術研究所
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京泛華偉業知識產權代理有限公司
• 代理人: 王 勇

1.一種應用于GIS中的面面疊加環構造方法，包括對兩個多邊形組 中的多邊形進行交操作，以及對兩個多邊形組中的多邊形進行差操作；其 中，

所述的對兩個多邊形組中的多邊形進行交操作包括：

步驟1)、對產生交點的多邊形環通過交點的出入屬性查找屬于所述多 邊形環上的所有交點，根據所查找到的交點得到相應的多邊形環；根據所 得到多邊形環是內環還是外環將所得到的多邊形環插入交結果的內環集 合或交結果的外環集合中；

步驟2)、在一個多邊形組中，在沒有交點的多邊形的內環和/或外環 上分別選擇邊界點作為代表點，將所選擇的邊界點與另一組多邊形中的各 個多邊形進行比較，若該邊界點在另一多邊形組的多邊形內部，則執行： 將所述邊界點所在的環寫入交結果中，若所述邊界點是外環上的邊界點， 則將環寫入交結果的外環集合中，若所述邊界點是內環上的邊界點，則將 環寫入交結果的內環集合中，然后結束操作；若該邊界點在另一多邊形組 的多邊形外部，則執行：將所述邊界點所在的環放棄，不寫入交結果中， 結束操作；

所述的對兩個多邊形組中的多邊形進行差操作包括：

步驟3)、對兩個多邊形組中的多邊形進行分類，分為存在異色交點的 多邊形，只存在同色交點的多邊形，以及不存在任何交點的多邊形；

步驟4)、對上一步驟中分類得到的只存在同色交點的多邊形以及不存 在任何交點的多邊形進行插入操作，得到差結果的內環集合、差結果的外 環集合以及一個待拆分的內環集合，具體包括對作為被減數的源多邊形組 上的環的操作，以及作為減數的擦除多邊形組上的環的操作，

其中所述對作為被減數的源多邊形組上的環的操作包括：

步驟4-1-1)、在源多邊形組中，在多邊形的內環和/或外環上選擇邊界 點；

步驟4-1-2)、將所選擇的邊界點與擦除多邊形組中的各個多邊形進行 比較，若該邊界點在擦除多邊形組的多邊形內部，則執行下一步，若該邊 界點在擦除多邊形組的多邊形外部，則執行步驟4-1-4)；

步驟4-1-3)、將所述邊界點所在的環放棄，不寫入結果中，結束操作；

步驟4-1-4)、將所述邊界點所在的環寫入結果中，若所述邊界點是外 環上的邊界點，則將環寫入差結果的外環集合中，若所述邊界點是內環上 的邊界點，則將環寫入差結果的內環集合中；最后結束操作；

所述作為減數的擦除多邊形組上的環的操作包括：

步驟4-2-1)、在擦除多邊形組中，在多邊形的內環、外環上分別選擇 邊界點；

步驟4-2-2)、將所選擇的邊界點與源多邊形組中的各個多邊形進行比 較，若該邊界點在源多邊形組的多邊形內部，則執行下一步，若該邊界點 在源多邊形組的多邊形外部，則執行步驟4-2-6)；

步驟4-2-3)、對多邊形的類型進行判斷，若所述多邊形中沒有任何交 點，則執行步驟4-2-4)，若所述多邊形中只有同色交點，則執行步驟4-2-5)；

步驟4-2-4)、將所述邊界點所在的環寫入結果中，若所述邊界點是外 環上的邊界點，則將環寫入差結果的內環集合中，若所述邊界點是內環上 的邊界點，則將環寫入差結果的外環集合中；最后結束操作；

步驟4-2-5)、將所述邊界點所在的環寫入結果中，若所述邊界點是外 環上的邊界點，則將環寫入待拆分內環集合中，若所述邊界點是內環上的 邊界點，則將環寫入差結果的外環集合中；最后結束操作；

步驟4-2-6)、將所述邊界點所在的環放棄，不寫入結果中，結束操作；

步驟5)、根據同色交點和異色交點以及待拆分的內環集合求差操作， 將所得到的結果插入差結果的外環集合中；進一步包括：

步驟5-1)、得到屬于同一個多邊形的所有異色交點，判斷所述異色交 點是否是完全重合的交點，若是，則根據對特殊類型交點處理的方法對其 進行處理，否則，執行下一步；

步驟5-2)、根據異色交點的出入屬性求作為被減數的源多邊形中位于 作為減數的擦除多邊形外部的線段；

步驟5-3)、根據異色交點的出入屬性求擦除多邊形位于源多邊形內部 的線段；

步驟5-4)、判斷對于源多邊形的待拆分內環集合是否為空，若為空， 則直接執行下一步，否則，對待拆分內環集合中的待拆分內環按照環上的 同色交點進行打斷，生成各條線段；

步驟5-5)、對步驟5-3)所生成的線段，判斷線段上是否存在同色交 點，若存在同色交點，則根據同色交點將線段打斷；

步驟5-5)、對上述步驟5-4)、5-5)所得到的所有被打斷的線段進行 重疊抵消操作，抵消具有重疊的線段；

步驟5-6)、將取消重疊部分后的所有被打斷的線段按照順序依次連 接，得到差結果的外環部分，并添加到差結果的外環集合中去；

由所述兩個多邊形組中的多邊形做所述交操作或差操作的結果，生成 所述兩個多邊形組間的面面疊加環。