서지주요정보
Chain visibility and linear-time triangulation of some polygon classes = 체인의 가시성과 선형시간으로 삼각분할되는 다각형 부류에 관한 연구
서명 / 저자 Chain visibility and linear-time triangulation of some polygon classes = 체인의 가시성과 선형시간으로 삼각분할되는 다각형 부류에 관한 연구 / Sang-Ho Lee.
저자명 Lee, Sang-Ho ; 이상호
발행사항 [서울 : 한국과학기술원, 1987].
Online Access 원문보기 원문인쇄

등록번호

4104685

소장위치/청구기호

학술문화관(문화관) 보존서고

DCS 8703

도서상태

이용가능

반납예정일

#### 초록정보

In this thesis, the notions of the visibility in a simple polygon are extended, the polygon hierarchy according to its visibility properties is established and it is shown that polygons having such properties can be easily triangulated. First, after introducing the convex chain visible polygon and the reflex chain visible polygon we show that whether or not a polygon is visible from a given convex or reflex chain can be determined in linear-time, respectively. Also, linear-time algorithms for finding all convex or reflex chains, if any, from which a given polygon is visible are presented. Second, new classes of polygons, intersection free polygons and generalized intersection free polygons are introduced and linear-time algorithms for determining whether or not a polygon is an intersection free polygon or a generalized intersection free polygon from a given point are presented. Also, it is shown that many polygon classes previously known with some visibility properties are subclasses of intersection free polygons or generalized intersection free polygons. Based on our definitions of polygon classes, the hierarchy of some polygon classes is suggested. Finally, the problem of polygon triangulations is considered. Linear-time algorithms for triangulating convex chain visible polygons, reflex chain visible polygons, intersection free polygons and generalized intersection free polygons are given. Also, we present an improved algorithm for triangulating point visible polygons without decomposition, which is simpler to implement and easier to understand.

일반적으로 그래픽스, CAD/CAM, VLSI, 패턴 인식등의 분야에서 자주 나타나는 기하학적인 문제를 컴퓨터를 이용하여 해결할 때 그 효율성은 문제의 대상(object)이 지니는 성질에 크게 좌우가 된다. 그 중에서도 대상이 다각형일 때 가시성(visibility)은 다각형의 기본적인 성질중 하나이며 주어진 다각형의 성질이 이미 알려져 있는 가시성질을 가지고 있으면 그에 대한 기하학적인 작업(operation)을 일반 다각형 보다는 좀 더 효율적으로 해결할 수 있다. 따라서 가시성에 대한 다각형 부류의 확장은 매우 필요하다고 할 수 있다. 본 논문에서는 다각형의 가시성에 대한 개념을 점(point)과 선분(edge)으로 부터 체인(chain)으로 확장하였고, 가시성과 관련 있는 새로운 다각형의 부류들을 소개하였으며, 기존의 다각형 부류들과의 계층 구조를 구축하였고, 이러한 가시 성질(visibility property)을 이용하여 기하학적인 작업 중 하나인 삼각 분할(triangulation)이 쉽게 해결 될 수 있음을 보였다.

#### 서지기타정보

청구기호 {DCS 8703 x, 104 p. : 삽도 ; 26 cm 영어 저자명의 한글표기 : 이상호 지도교수의 영문표기 : Kyung-Yong Chwa 지도교수의 한글표기 : 좌경룡 학위논문(박사) - 한국과학기술원 : 전산학과, Reference : p. 96-102 Visibility. Image processing. 화상 처리. --과학기술용어시소러스 Polygons. Triangulation.
QR CODE