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)이 쉽게 해결 될 수 있음을 보였다.
