计算机与现代化
計算機與現代化
계산궤여현대화
COMPUTER AND MODERNIZATION
2013年
1期
53-56,60
,共5页
计算机图形%斜率%简单多边形%内外点判别
計算機圖形%斜率%簡單多邊形%內外點判彆
계산궤도형%사솔%간단다변형%내외점판별
多边形的内外点判别是图形学的一个基础算法,为了更大限度地降低其算法复杂度和运算量,提出一种基于斜率的点与多边形位置关系的快速判别法.该方法只需计算该点到多边形各顶点的斜率,然后与多边形各顶点的邻边的斜率进行比较,即可对多边形的内外点快速做出判别.该算法无需复杂的点乘、叉乘、求交、三角函数等运算,在判别过程中仅需平均2n次减法运算和n/2次的除法运算,以及一些比较运算,即可对简单n多边形的内外点做出判别.经测试,该算法快速有效.
多邊形的內外點判彆是圖形學的一箇基礎算法,為瞭更大限度地降低其算法複雜度和運算量,提齣一種基于斜率的點與多邊形位置關繫的快速判彆法.該方法隻需計算該點到多邊形各頂點的斜率,然後與多邊形各頂點的鄰邊的斜率進行比較,即可對多邊形的內外點快速做齣判彆.該算法無需複雜的點乘、扠乘、求交、三角函數等運算,在判彆過程中僅需平均2n次減法運算和n/2次的除法運算,以及一些比較運算,即可對簡單n多邊形的內外點做齣判彆.經測試,該算法快速有效.
다변형적내외점판별시도형학적일개기출산법,위료경대한도지강저기산법복잡도화운산량,제출일충기우사솔적점여다변형위치관계적쾌속판별법.해방법지수계산해점도다변형각정점적사솔,연후여다변형각정점적린변적사솔진행비교,즉가대다변형적내외점쾌속주출판별.해산법무수복잡적점승、차승、구교、삼각함수등운산,재판별과정중부수평균2n차감법운산화n/2차적제법운산,이급일사비교운산,즉가대간단n다변형적내외점주출판별.경측시,해산법쾌속유효.
