A simple linear algorithm for intersecting convex polygons

DOI10.1007/BF01898355MaRDI QIDQ1822240zbMATH OpenOpenAlexFDO

Authors Godfried Toussaint

Publication date 1985

Published in The Visual Computer (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01898355

zbMATH Keywords

computational geometryconvex hullsconvex polygonsgeometric algorithmsintersectiontriangulations of polygons

Mathematics Subject Classification ID

Convex sets in (2) dimensions (including convex curves) (52A10) Polytopes and polyhedra (52Bxx) Analysis of algorithms and problem complexity (68Q25)

Review text

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.

Recommendations

• A new linear algorithm for intersecting convex polygons
• A new O(n \,n) algorithm for computing the intersection of convex polygons
• scientific article; zbMATH DE number 6789228
• A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
• scientific article; zbMATH DE number 3926242

Cites work

• A new linear algorithm for intersecting convex polygons
• An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons
• Polygons Have Ears
• Triangulating a simple polygon

Cited in

(24)

• A new O(n \,n) algorithm for computing the intersection of convex polygons
• Detecting the intersection of convex objects in the plane
• A robust method for calculating the simplicity and orientation of planar polygons
• Efficient algorithms for testing membership of a point in polygons and polyhedra
• A novel approach for ellipsoidal outer-approximation of the intersection region of ellipses in the plane
• An algorithm for the numerical detection of simplex overlap
• All convex polyhedra can be clamped with parallel jaw grippers
• Efficient algorithms for counting and reporting pairwise intersections between convex polygons
• A new linear algorithm for intersecting convex polygons
• scientific article; zbMATH DE number 3890752 (Why is no real title available?)
• A linear algorithm for determining the separation of convex polyhedra
• scientific article; zbMATH DE number 3926242 (Why is no real title available?)
• scientific article; zbMATH DE number 3945383 (Why is no real title available?)
• scientific article; zbMATH DE number 1190951 (Why is no real title available?)
• Linear algorithm to find the largest intriangles of a planar convex polygon
• scientific article; zbMATH DE number 1318519 (Why is no real title available?)
• EDGE ADVANCING RULES FOR INTERSECTING SPHERICAL CONVEX POLYGONS
• An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
• Three-dimensional discrete element simulation for granular materials
• scientific article; zbMATH DE number 6789228 (Why is no real title available?)
• SignedIntersection -- a new algorithm for finding the intersection of two simple polygons
• Using sentinels to detect intersections of convex and nonconvex polygons
• Reasoning in OWL 2 EL with hierarchical concrete domains
• A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions

This page was built for publication: A simple linear algorithm for intersecting convex polygons

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1822240)