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 polygonsintersectiongeometric algorithmstriangulations of polygons

Mathematics Subject Classification ID

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

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

(23)

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

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)