计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2009年
2期
185-186,196
,共3页
点%简单多边形%射线%算法%斜率
點%簡單多邊形%射線%算法%斜率
점%간단다변형%사선%산법%사솔
基于射线法提出了一种新的判断点与简单多边形位置关系的算法.该算法是通过查找简单多边形所有顶点在确定区域内中斜率最小点,以此点确定一条射线,使得这条射线不穿过简单多边形的顶点.此算法不但保持了原来射线法相对其它方法有容易理解、计算简单等优势,并在此基础上排除了射线法中特殊的射线与简单多边形的顶点相交或射线过简单多边形边的特殊情况,大大地降低了算法的时间复杂度,提高了检测速度.
基于射線法提齣瞭一種新的判斷點與簡單多邊形位置關繫的算法.該算法是通過查找簡單多邊形所有頂點在確定區域內中斜率最小點,以此點確定一條射線,使得這條射線不穿過簡單多邊形的頂點.此算法不但保持瞭原來射線法相對其它方法有容易理解、計算簡單等優勢,併在此基礎上排除瞭射線法中特殊的射線與簡單多邊形的頂點相交或射線過簡單多邊形邊的特殊情況,大大地降低瞭算法的時間複雜度,提高瞭檢測速度.
기우사선법제출료일충신적판단점여간단다변형위치관계적산법.해산법시통과사조간단다변형소유정점재학정구역내중사솔최소점,이차점학정일조사선,사득저조사선불천과간단다변형적정점.차산법불단보지료원래사선법상대기타방법유용역리해、계산간단등우세,병재차기출상배제료사선법중특수적사선여간단다변형적정점상교혹사선과간단다변형변적특수정황,대대지강저료산법적시간복잡도,제고료검측속도.
