一種判斷點是否位於多邊形內的方法
2023-05-23 14:30:01 4
廣l，選擇度SD(SelectionDegree)=Min(PD，BD)，即PD和BD這兩個值中較小的那一個值就為SD的值。b)為每條直線計算其SD值，然後，以SD值最大的一條直線作為這個凸多邊形集合的劃分直線，將此集合分割成2個子集合，此時這2個子集合均要包含與該劃分直線相交的凸多邊形。這裡，計算PD的目的是要使與劃分直線相交的凸多邊形的個數儘可能少，以減少凸多邊形被重複處理的次數，以降低樹的高度，節省存儲空間和加速判斷計算；計算BD的目的是使樹的兩邊儘可能平衡，以提高判斷計算時相應的二分搜索的速度。所建立的平衡二叉樹，如圖3所示，其中樹的間結點記錄相關的劃分直線，而其葉子結點記錄相關的一個凸多邊形。2.第二階段的實現步驟如下(1)根據被檢測點的坐標，對二叉樹進行由頂至底的搜索，即先考察樹的根結點，看被檢測點位於其劃分直線的哪一邊，然後就以那一邊對應的子結點作為下一步考察的對象，如此迭代進行，直至到達葉結點，該葉節點中的凸多邊形就是所要找的凸多邊形。(2)對於葉結點中的凸多邊形，判斷被檢測點是否位於該凸多邊形內，首先將它的邊分成兩個單調邊序列，即找到這個凸多邊形中Y坐標值最大的一個頂點和Y坐標值最小的一個頂點，根據這兩個頂點將該多邊形的邊分成2個部分，每個部分都是順序連接的邊，且這些邊的頂點Y坐標值是順序增大的或減小的；然後，根據被檢測點的Y坐標值形成一條平行X軸的直線，如圖4所示，計算該直線與這個凸多邊形的兩個單調邊序列的兩個交點的X坐標值，比較被檢測點的X坐標值是否位於兩個交點的X坐標值之間。如果是，則該點位於這個凸多邊形內，也就是位於給定的多邊形內；否則，在給定的多邊形外。圖5是本發明判斷點是否位於多邊形內的整體流程圖。下面是本發明的一些實驗數據隨機生成4個多邊形以進行實驗，它們都有10000條邊，但它們的凹點所佔的比例分別為0%、10%、30%和50%。凹點比例為0%的多邊形就是凸多邊形。測試時，我們在多邊形的包圍盒內均勻分布1000個點進行檢測，將它們的平均檢測時間作為實驗數據。我們將新方法與國際上已知最快的隨機漸增梯形法(therandomizedincrementaltrapezoidation-basedalgorithm)進行了實驗對比，實驗數據見下列表中。實驗表明，新方法使用的凸多邊形個數少於隨機漸增梯形法所使用的梯形個數，新方法在存儲空間需求和檢測速度方面均好於隨機漸增梯形法。tableseeoriginaldocumentpage8實驗表明，與目前最快的基於梯形剖分的方法一増量梯形法相比，本發明的方法在多邊形的預處理的時間、空間需求和判斷計算等各個方面具有相同的複雜度，但是新方法所生成的凸多邊形要少於增量梯形法所生成的梯形，因此，新方法的空間需求要少，判斷速度要快。權利要求1、一種判斷點是否位於多邊形內的方法，其步驟包括1)將給定的多邊形剖分為單調多邊形集合；2)將上述單調多邊形中非凸的多邊形進行凸剖分，得到給定多邊形的凸多邊形集合；3)以凸多邊形的邊形成的直線作為劃分直線，基於每劃分直線兩側凸多邊形的個數建立平衡二叉樹，其中根節點和中間結點存放各自相應的劃分直線，葉節點存放相應的一凸多邊形；4)根據給定點與平衡二叉樹非葉子節點存放的劃分直線的位置關係對上述平衡二叉樹進行搜索，直至到達一葉節點；5)判斷給定點和上述葉節點對應的凸多邊形的位置關係，如果該點位於這個凸多邊形內，則該點位於給定的多邊形內；否則，該點位於給定的多邊形外。2、如權利要求l所述的判斷點是否位於多邊形內的方法，其特徵在於所述步驟1)為a)找到多邊形的所有上凹點和下凹點；b)對所有上凹點和下凹點，根據它們的Y坐標值排序；c)對每一個上凹點，將其與任一個Y坐標值小於它的下凹點或凸頂點連成一條邊，選取其中位於該多邊形內部且邊長最短的一條邊，將多邊形進行一次剖分；同理，對每一個下凹點，將其與任一個Y坐標值大於它的上凹點或凸頂點連成一條邊，選取其中位於該多邊形內部且邊長最短的一條邊，將多邊形進行一次剖分；d)重複c)的操作，上凹點和下凹點都要操作一次。3、如權利要求1或2所述的判斷點是否位於多邊形內的方法，其特徵在於所述步驟2)為a)找出單調多邊形中的凹點，將它們的Y坐標值由大到小進行排序；b)按照Y坐標值由大到小的順序依次處理凹點，將凹點與Y坐標值小於它的凹點或其它頂點進行連接，選取其中邊長最短且在該單調多邊形內的一條邊作為該單調多邊形的一次剖分；c)反覆進行b)的操作，直至各個剖分的多邊形中都沒有凹點為止。4、如權利要求1所述的判斷點是否位於多邊形內的方法，其特徵在於計算與劃分直線相交的當前凸多邊形集合中的凸多邊形的個數相對於集合中凸多邊形個數的比例，以及位於該劃分直線兩側的當前凸多邊形集合中的凸多邊形的個數的比例，來選定分割當前凸多邊形集合的劃分直線，其步驟如下1)設位於一條劃分直線兩側的凸多邊形集合分別為S,、SR、與該直線相交的凸多邊形集合為S,,它們所包含的凸多邊形個數分別為n,,n、n;計算3個參量;純淨度formulaseeoriginaldocumentpage3選擇度formulaseeoriginaldocumentpage32)選定SD值最大的一條劃分直線作為當前凸多邊形集合的劃分直線。5、如權利要求4所述的判斷點是否位於多邊形內的方法，其特徵在於如存在多條SD值最大的劃分直線，則任選一條作為當前凸多邊形集合的劃分直線。6、如權利要求1所述的判斷點是否位於多邊形內的方法，其特徵在於所述步驟4)為從二叉樹的根結點開始，判斷被檢測點位於它相關的劃分直線的哪一邊，並以這邊對應的子結點作為下一步考察的樹結點，沿著樹結點迭代地操作，直至達到一個葉結點。7、如權利要求1或6所述的判斷點是否位於多邊形內的方法，其特徵在於所述步驟5)為將該葉節點對應的凸多邊形的邊分成兩個單調邊序列；然後，根據給定點的Y坐標值形成一條平行X軸的直線，並計算該直線與這個凸多邊形的兩個單調邊序列的兩個交點的X坐標值；如果給定點的X坐標值位於這兩個交點的X坐標值之間，則這該點位於該凸多邊形內，也位於給定的多邊形內；否則該點位於該凸多邊形外，也位於給定的多邊形外。全文摘要本發明屬於計算機圖形技術和計算幾何
技術領域：
，是一種判斷點是否位於多邊形內的方法。本發明先對多邊形進行凸剖分，並建立二叉樹來管理這些凸多邊形；然後，根據被檢測點的坐標位置，對所建立的二叉樹進行考察，以找到該二叉數的一葉節點對應的凸多邊形，再檢測該點是否位於這個凸多邊形內，以判斷被檢測點是否位於給定的多邊形內。本發明的優點是計算速度快，比基於多邊形剖分的同類方法節省存儲空間，易於實現。適用於多個點要對同一個多邊形進行這種包含性判斷的情況。文檔編號G06T7/60GK101114379SQ20071012150公開日2008年1月30日申請日期2007年9月7日優先權日2007年9月7日發明者靜李,王文成申請人:中國科學院軟體研究所