图学学报
圖學學報
도학학보
Journal of Graphics
2014年
4期
498-503
,共6页
多边形%孔洞%最小回路%布尔运算
多邊形%孔洞%最小迴路%佈爾運算
다변형%공동%최소회로%포이운산
polygon%hole%minimum circle%Boolean
提出了一种基于最小回路确定含孔洞多边形P和Q的交、并、差集的新方法.首先,初始化P和Q外环为逆时针方向,内环为顺时针方向,并通过连接内环极右顶点与其在外环上一可见点v,构造一条双向“桥边”,将内外多环转换为单环.其次,求出P和Q被转换为单环的边序列的交点,并对交点处的关联边进行排序.然后,沿着各个交点处正向边,依照最小转角原则搜索最小回路,并根据其中所含P和Q边所呈现的顺、逆时针方向进行分类.最后,P和Q的交、并、差集即对应不同类别的最小回路.算法简洁且几何意义明显,具有较好的适应性.
提齣瞭一種基于最小迴路確定含孔洞多邊形P和Q的交、併、差集的新方法.首先,初始化P和Q外環為逆時針方嚮,內環為順時針方嚮,併通過連接內環極右頂點與其在外環上一可見點v,構造一條雙嚮“橋邊”,將內外多環轉換為單環.其次,求齣P和Q被轉換為單環的邊序列的交點,併對交點處的關聯邊進行排序.然後,沿著各箇交點處正嚮邊,依照最小轉角原則搜索最小迴路,併根據其中所含P和Q邊所呈現的順、逆時針方嚮進行分類.最後,P和Q的交、併、差集即對應不同類彆的最小迴路.算法簡潔且幾何意義明顯,具有較好的適應性.
제출료일충기우최소회로학정함공동다변형P화Q적교、병、차집적신방법.수선,초시화P화Q외배위역시침방향,내배위순시침방향,병통과련접내배겁우정점여기재외배상일가견점v,구조일조쌍향“교변”,장내외다배전환위단배.기차,구출P화Q피전환위단배적변서렬적교점,병대교점처적관련변진행배서.연후,연착각개교점처정향변,의조최소전각원칙수색최소회로,병근거기중소함P화Q변소정현적순、역시침방향진행분류.최후,P화Q적교、병、차집즉대응불동유별적최소회로.산법간길차궤하의의명현,구유교호적괄응성.
