Browse Prior Art Database

Efficient Triangulation of Nonconvex Polygons with One Concave Vertex

IP.com Disclosure Number: IPCOM000112190D
Original Publication Date: 1994-Apr-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 2 page(s) / 61K

Publishing Venue

IBM

Related People

Erb, DJ: AUTHOR [+2]

Abstract

Disclosed is a method which simplifies the triangulation of nonconvex polygons with one concave vertex. This method takes almost zero computation time to decompose the polygon after the concave vertex has been identified; therefore, the whole filling process time is reduced. Nonconvex polygons with one concave vertex appear in many common and useful shapes, such as arrowheads and check marks. Thus, many graphics applications benefit from this method.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 60% of the total text.

Efficient Triangulation of Nonconvex Polygons with One Concave Vertex

      Disclosed is a method which simplifies the triangulation of
nonconvex polygons with one concave vertex.  This method takes almost
zero computation time to decompose the polygon after the concave
vertex has been identified; therefore, the whole filling process time
is reduced.  Nonconvex polygons with one concave vertex appear in
many common and useful shapes, such as arrowheads and check marks.
Thus, many graphics applications benefit from this method.

      While the triangulation a convex polygon is a very simple task,
efficient triangulation of a nonconvex polygon has been a known
problem in computational geometry for many years, due to the shape
complexity of the nonconvex polygon.  Most of the nonconvex
triangulation methods spend significant time doing the computation,
which is so expensive and inefficient that it is not practical to use
them in real applications.  In contrast, this disclosure provides a
simple way to decompose a nonconvex polygon with one concave vertex
which can be used in real applications.

      A nonconvex polygon is one in which no edges intersect but
contains at least one internal angle greater than 180 degrees, which
is referred to as a "concave vertex".  Nonconvex polygons can be very
complex or very simple.  The simplest nonconvex polygon is one that
has a single concave vertex.

      To determine whether a given nonconvex polygon has a singl...