中国图象图形学报A
中國圖象圖形學報A
중국도상도형학보A
JOURNAL OF IMAGE AND GRAPHICS
2008年
12期
2400-2408
,共9页
毛定山%崔先国%李行%吴哲辉
毛定山%崔先國%李行%吳哲輝
모정산%최선국%리행%오철휘
关联多边形%最小矩形包围框(MBR)%三角化分割
關聯多邊形%最小矩形包圍框(MBR)%三角化分割
관련다변형%최소구형포위광(MBR)%삼각화분할
计算简单多边形间的最小距离,在所有与几何图形计算有关的领域中,一直以来都是一个基本问题.为了更快地求解简单多边形的最小距离.提出了一个基于关联多边形三角化分割的简单多边形间最小距离的求解算法.该算法的主要思想是:首先构造一个关联多边形把两个多边形联系起来,其目的是把最小距离限制在这个关联多边形内;然后根据两个多边形的最小边界矩形包嗣框间的不同位置关系,详细阐述了关联多边形的构造过程,同时论述了关联多边形是一个简单多边形.为了计算最小距离,首先要对关联多边形进行三角化分割,并使最小距离位于三角化分割结果中某一个三角形区域内,或者至多位于两个相邻三角形区域内;之后通过对所有三角形进行遍历来找出最小距离及其所在的位置.该算法的时间复杂度是线性的.
計算簡單多邊形間的最小距離,在所有與幾何圖形計算有關的領域中,一直以來都是一箇基本問題.為瞭更快地求解簡單多邊形的最小距離.提齣瞭一箇基于關聯多邊形三角化分割的簡單多邊形間最小距離的求解算法.該算法的主要思想是:首先構造一箇關聯多邊形把兩箇多邊形聯繫起來,其目的是把最小距離限製在這箇關聯多邊形內;然後根據兩箇多邊形的最小邊界矩形包嗣框間的不同位置關繫,詳細闡述瞭關聯多邊形的構造過程,同時論述瞭關聯多邊形是一箇簡單多邊形.為瞭計算最小距離,首先要對關聯多邊形進行三角化分割,併使最小距離位于三角化分割結果中某一箇三角形區域內,或者至多位于兩箇相鄰三角形區域內;之後通過對所有三角形進行遍歷來找齣最小距離及其所在的位置.該算法的時間複雜度是線性的.
계산간단다변형간적최소거리,재소유여궤하도형계산유관적영역중,일직이래도시일개기본문제.위료경쾌지구해간단다변형적최소거리.제출료일개기우관련다변형삼각화분할적간단다변형간최소거리적구해산법.해산법적주요사상시:수선구조일개관련다변형파량개다변형련계기래,기목적시파최소거리한제재저개관련다변형내;연후근거량개다변형적최소변계구형포사광간적불동위치관계,상세천술료관련다변형적구조과정,동시논술료관련다변형시일개간단다변형.위료계산최소거리,수선요대관련다변형진행삼각화분할,병사최소거리위우삼각화분할결과중모일개삼각형구역내,혹자지다위우량개상린삼각형구역내;지후통과대소유삼각형진행편력래조출최소거리급기소재적위치.해산법적시간복잡도시선성적.
