高技术通讯
高技術通訊
고기술통신
HIGH TECHNOLOGY LETTERS
2011年
8期
810-816
,共7页
朱效民%刘焱%廖浩均%方金云
硃效民%劉焱%廖浩均%方金雲
주효민%류염%료호균%방금운
均匀条带划分法%射线法%点包含性测试%多边形%计算几何
均勻條帶劃分法%射線法%點包含性測試%多邊形%計算幾何
균균조대화분법%사선법%점포함성측시%다변형%계산궤하
提出了一个大量点与多边形关系计算的方法.该方法首先对多边形进行简单预处理,然后采用射线法对每个点进行包含性测试.预处理将多边形的最小包围矩形划分为相同大小的竖直条带,并计算每条边在哪些条带中,该预处理过程简单快速.利用预处理信息对点进行包含性测试时,只需用当前点构造的射线和点所在的条带包含的边进行相交测试即可.每个条带内包含的边的数目是有限的,常常接近一个常数,远远小于多边形的边数,因此相交测试计算次数显著减少,从而可以快速求得点与多边形的关系.该方法已经实现,并用人造数据和真实地理数据进行测试,测试结果证明该方法正确有效.
提齣瞭一箇大量點與多邊形關繫計算的方法.該方法首先對多邊形進行簡單預處理,然後採用射線法對每箇點進行包含性測試.預處理將多邊形的最小包圍矩形劃分為相同大小的豎直條帶,併計算每條邊在哪些條帶中,該預處理過程簡單快速.利用預處理信息對點進行包含性測試時,隻需用噹前點構造的射線和點所在的條帶包含的邊進行相交測試即可.每箇條帶內包含的邊的數目是有限的,常常接近一箇常數,遠遠小于多邊形的邊數,因此相交測試計算次數顯著減少,從而可以快速求得點與多邊形的關繫.該方法已經實現,併用人造數據和真實地理數據進行測試,測試結果證明該方法正確有效.
제출료일개대량점여다변형관계계산적방법.해방법수선대다변형진행간단예처리,연후채용사선법대매개점진행포함성측시.예처리장다변형적최소포위구형화분위상동대소적수직조대,병계산매조변재나사조대중,해예처리과정간단쾌속.이용예처리신식대점진행포함성측시시,지수용당전점구조적사선화점소재적조대포함적변진행상교측시즉가.매개조대내포함적변적수목시유한적,상상접근일개상수,원원소우다변형적변수,인차상교측시계산차수현저감소,종이가이쾌속구득점여다변형적관계.해방법이경실현,병용인조수거화진실지리수거진행측시,측시결과증명해방법정학유효.
