A simple linear algorithm for intersecting convex polygons

Godfried T. Toussaint

doi:10.1007/BF01898355

A simple linear algorithm for intersecting convex polygons

Godfried T. Toussaint

Computer Science

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

Abstract

Let P and Q be two convex polygons with m and n vertices, respectively, which are specified by their cartesian coordinates in order. A simple O(m+n) algorithm is presented for computing the intersection of P and Q. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.

Original language	English (US)
Pages (from-to)	118-123
Number of pages	6
Journal	The Visual Computer
Volume	1
Issue number	2
DOIs	https://doi.org/10.1007/BF01898355
State	Published - Aug 1985

Keywords

Algorithms
Complexity
Computational geometry
Convex polygons
Intersection

ASJC Scopus subject areas

Software
Computer Vision and Pattern Recognition
Computer Graphics and Computer-Aided Design

Access to Document

10.1007/BF01898355

Cite this

@article{bfa9cd88b80846f69426809b666b3fe2,

title = "A simple linear algorithm for intersecting convex polygons",

abstract = "Let P and Q be two convex polygons with m and n vertices, respectively, which are specified by their cartesian coordinates in order. A simple O(m+n) algorithm is presented for computing the intersection of P and Q. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.",

keywords = "Algorithms, Complexity, Computational geometry, Convex polygons, Intersection",

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

year = "1985",

month = aug,

doi = "10.1007/BF01898355",

language = "English (US)",

volume = "1",

pages = "118--123",

journal = "The Visual Computer",

issn = "0178-2789",

publisher = "Springer Verlag",

number = "2",

}

TY - JOUR

T1 - A simple linear algorithm for intersecting convex polygons

AU - Toussaint, Godfried T.

PY - 1985/8

Y1 - 1985/8

N2 - Let P and Q be two convex polygons with m and n vertices, respectively, which are specified by their cartesian coordinates in order. A simple O(m+n) algorithm is presented for computing the intersection of P and Q. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.

AB - Let P and Q be two convex polygons with m and n vertices, respectively, which are specified by their cartesian coordinates in order. A simple O(m+n) algorithm is presented for computing the intersection of P and Q. Unlike previous algorithms, the new algorithm consists of a two-step combination of two simple algorithms for finding convex hulls and triangulations of polygons.

KW - Algorithms

KW - Complexity

KW - Computational geometry

KW - Convex polygons

KW - Intersection

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

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

U2 - 10.1007/BF01898355

DO - 10.1007/BF01898355

M3 - Article

AN - SCOPUS:0022138308

SN - 0178-2789

VL - 1

SP - 118

EP - 123

JO - The Visual Computer

JF - The Visual Computer

IS - 2

ER -

A simple linear algorithm for intersecting convex polygons

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this