A new linear algorithm for triangulating monotone polygons

Godfried T. Toussaint

doi:10.1016/0167-8655(84)90039-4

A new linear algorithm for triangulating monotone polygons

Godfried T. Toussaint

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

Let P = (p₁, p₂,...,p_n) be a monotone polygon whose vertices are specified in terms of cartesian coordinates in order. A new simple two-step procedure is presented for triangulating P, without the addition of new vertices, in O(n) time. Unlike the previous algorithm no specialized code is needed since the new approach uses well-known existing algorithms for first decomposing P into edge-visible polygons and subsequently triangulating these.

Original language	English (US)
Pages (from-to)	155-158
Number of pages	4
Journal	Pattern Recognition Letters
Volume	2
Issue number	3
DOIs	https://doi.org/10.1016/0167-8655(84)90039-4
State	Published - Mar 1984

Keywords

Algorithms
complexity
computational geometry
computer graphics
edge-visible polygons
image processing
monotone polygons
pattern recognition
polygon decomposition
simple polygons
triangulation
visibility

ASJC Scopus subject areas

Software
Signal Processing
Computer Vision and Pattern Recognition
Artificial Intelligence

Access to Document

10.1016/0167-8655(84)90039-4

Cite this

@article{8738375634ee4418b4d70fc15e326009,

title = "A new linear algorithm for triangulating monotone polygons",

abstract = "Let P = (p1, p2,...,pn) be a monotone polygon whose vertices are specified in terms of cartesian coordinates in order. A new simple two-step procedure is presented for triangulating P, without the addition of new vertices, in O(n) time. Unlike the previous algorithm no specialized code is needed since the new approach uses well-known existing algorithms for first decomposing P into edge-visible polygons and subsequently triangulating these.",

keywords = "Algorithms, complexity, computational geometry, computer graphics, edge-visible polygons, image processing, monotone polygons, pattern recognition, polygon decomposition, simple polygons, triangulation, visibility",

author = "Toussaint, {Godfried T.}",

year = "1984",

month = mar,

doi = "10.1016/0167-8655(84)90039-4",

language = "English (US)",

volume = "2",

pages = "155--158",

journal = "Pattern Recognition Letters",

issn = "0167-8655",

publisher = "Elsevier",

number = "3",

}

TY - JOUR

T1 - A new linear algorithm for triangulating monotone polygons

AU - Toussaint, Godfried T.

PY - 1984/3

Y1 - 1984/3

N2 - Let P = (p1, p2,...,pn) be a monotone polygon whose vertices are specified in terms of cartesian coordinates in order. A new simple two-step procedure is presented for triangulating P, without the addition of new vertices, in O(n) time. Unlike the previous algorithm no specialized code is needed since the new approach uses well-known existing algorithms for first decomposing P into edge-visible polygons and subsequently triangulating these.

AB - Let P = (p1, p2,...,pn) be a monotone polygon whose vertices are specified in terms of cartesian coordinates in order. A new simple two-step procedure is presented for triangulating P, without the addition of new vertices, in O(n) time. Unlike the previous algorithm no specialized code is needed since the new approach uses well-known existing algorithms for first decomposing P into edge-visible polygons and subsequently triangulating these.

KW - Algorithms

KW - complexity

KW - computational geometry

KW - computer graphics

KW - edge-visible polygons

KW - image processing

KW - monotone polygons

KW - pattern recognition

KW - polygon decomposition

KW - simple polygons

KW - triangulation

KW - visibility

UR - http://www.scopus.com/inward/record.url?scp=0021363943&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021363943&partnerID=8YFLogxK

U2 - 10.1016/0167-8655(84)90039-4

DO - 10.1016/0167-8655(84)90039-4

M3 - Article

AN - SCOPUS:0021363943

SN - 0167-8655

VL - 2

SP - 155

EP - 158

JO - Pattern Recognition Letters

JF - Pattern Recognition Letters

IS - 3

ER -

A new linear algorithm for triangulating monotone polygons

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this