福建师范大学学报(自然科学版)
福建師範大學學報(自然科學版)
복건사범대학학보(자연과학판)
JOURNAL OF FUJIAN TEACHERS UNIVERSITY（NATURAL SCIENCE）
2001年
3期
18-24
,共7页
点集%多边形%平面区域%二分法
點集%多邊形%平麵區域%二分法
점집%다변형%평면구역%이분법
提出一种基于二分法判定点集是否在多边形内部的算法,根据多边形L的顶点和边分布的情况,分割平面为一组平面区域的有序集合R,判定R中每个区域是否在多边形L内部;对于点集S中的点p,用二分法搜索R,找到点p所属的平面区域,从而判定出点p是否在多边形内部.该算法在最坏情况下的时间复杂性为max(O(n log m),O(tm log m)),其中n为点集S的点数,m为多边形L的顶点数,t为多边形L所有顶点的X坐标的不同取值个数.在一般情况下该算法比已有的算法效率更高.
提齣一種基于二分法判定點集是否在多邊形內部的算法,根據多邊形L的頂點和邊分佈的情況,分割平麵為一組平麵區域的有序集閤R,判定R中每箇區域是否在多邊形L內部;對于點集S中的點p,用二分法搜索R,找到點p所屬的平麵區域,從而判定齣點p是否在多邊形內部.該算法在最壞情況下的時間複雜性為max(O(n log m),O(tm log m)),其中n為點集S的點數,m為多邊形L的頂點數,t為多邊形L所有頂點的X坐標的不同取值箇數.在一般情況下該算法比已有的算法效率更高.
제출일충기우이분법판정점집시부재다변형내부적산법,근거다변형L적정점화변분포적정황,분할평면위일조평면구역적유서집합R,판정R중매개구역시부재다변형L내부;대우점집S중적점p,용이분법수색R,조도점p소속적평면구역,종이판정출점p시부재다변형내부.해산법재최배정황하적시간복잡성위max(O(n log m),O(tm log m)),기중n위점집S적점수,m위다변형L적정점수,t위다변형L소유정점적X좌표적불동취치개수.재일반정황하해산법비이유적산법효솔경고.
