福建师范大学学报（自然科学版）
福建師範大學學報（自然科學版）
복건사범대학학보（자연과학판）
JOURNAL OF FUJIAN TEACHERS UNIVERSITY (NATURAL SCIENCE EDITION)
2000年
4期
17-21
,共5页
点集%多边形%排序%逐行扫描
點集%多邊形%排序%逐行掃描
점집%다변형%배서%축행소묘
提出一种基于点集排序,逐行(或逐列)扫描平面点集S,判定点集S中的点是否在多边形L内部的算法.该算法的时间复杂性在最坏情况下为:max(O(n log n),O(km log m))次比较和O(km)次乘法.其中n 为点集S的点数,m为多边形L的顶点数,k=min(u,v),其中u,v分别为点集S中的点分布的行数和列数.该算法思路简单,易实现,且在一般情况下,效率比已有的算法高.
提齣一種基于點集排序,逐行(或逐列)掃描平麵點集S,判定點集S中的點是否在多邊形L內部的算法.該算法的時間複雜性在最壞情況下為:max(O(n log n),O(km log m))次比較和O(km)次乘法.其中n 為點集S的點數,m為多邊形L的頂點數,k=min(u,v),其中u,v分彆為點集S中的點分佈的行數和列數.該算法思路簡單,易實現,且在一般情況下,效率比已有的算法高.
제출일충기우점집배서,축행(혹축렬)소묘평면점집S,판정점집S중적점시부재다변형L내부적산법.해산법적시간복잡성재최배정황하위:max(O(n log n),O(km log m))차비교화O(km)차승법.기중n 위점집S적점수,m위다변형L적정점수,k=min(u,v),기중u,v분별위점집S중적점분포적행수화렬수.해산법사로간단,역실현,차재일반정황하,효솔비이유적산법고.
