作者shininglion (lionking - 辛巴)
站內Prob_Solve
標題[問題] 如何判斷多邊形的座標點順序
時間Fri Jul 20 21:12:18 2012
標題非常簡略所以可能很難懂...抱歉
---------------------------------------------
以下是前情提要：
1. 我有一個演算法是針對多邊形做一些處理，而多邊形的輸入格式為
以逆時針方向依序給定多邊形的每個座標點
2. 被處理的多邊形不會有中空的情形
並且這多邊形的每個轉角都是直角
3. 我要處理的多邊形的量非常多(數量級至少以百萬做單位)
----------------------------------------------
以下是我遇到的問題：
因為該演算法只能吃以逆時針方向給做標點
所以遇到有順時針給點的座標點我會預先把它處理成逆時針方向
但現在遇到的問題是我有一個 case 他裡面的多邊形
有些是順時針有些是逆時針
偏偏數量太多我不可能一個一個抓出來檢查到底是順時針還逆時針
想請問有沒有什麼方法可以判斷他給座標點的順序是順時針還是逆時針呢?
謝謝!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.135.238.148
※ 編輯: shininglion 來自: 220.135.238.148 (07/20 21:13)
→ Angrybird11:算叉積? 07/20 21:18
→ suhorng:判斷算出來的面積是正的還是負的 07/20 22:01
→ suhorng:如果是凸多邊形,隨便抓三個連續點判斷就好 07/20 22:01
→ shininglion:不是凸多邊形，有可能凹進去 07/20 22:04
→ shininglion:不過算面積應該可行! 也不會太麻煩~感謝! 07/20 22:05
→ tkcn:找 Y 座標最小的那條，判斷是往上還是往下即可。 07/20 22:28
→ rifiz:先sort, 用最左下的點先找第一組逆時鐘的 07/21 07:41
推 DJWS:找到最下再最左的頂點，判斷下一個頂點是往上還是往右即可 07/21 07:55
→ DJWS:寫個 for + if 就可以判斷了 不需要排序 07/21 07:57
→ shininglion:感謝樓上提供的好方法! 以解決 07/21 22:36