A new linear algorithm for intersecting convex polygons

DOI10.1016/0146-664X(82)90023-5zbMATH Open0533.52001OpenAlexW2043952582MaRDI QIDQ3316124FDOQ3316124

Authors: Joseph O'Rourke, Chi-Bin Chien, Thomas Olson, David Naddor 

Publication date: 1982

Published in: Computer Graphics and Image Processing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0146-664x(82)90023-5

Recommendations

• A simple linear algorithm for intersecting convex polygons
• A new O(n\(\cdot \log \,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
• Detecting the intersection of convex objects in the plane

zbMATH Keywords

angular sectorskernel of a polygon

Mathematics Subject Classification ID

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

Cited In (33)

• SignedIntersection -- a new algorithm for finding the intersection of two simple polygons
• An Optimal Algorithm for the Intersection Radius of a Set of Convex Polygons
• Linear algorithm to find the largest intriangles of a planar convex polygon
• A two-dimensional ellipse-rectangle intersection test
• A new O(n\(\cdot \log \,n)\) algorithm for computing the intersection of convex polygons
• Title not available (Why is that?)
• Title not available (Why is that?)
• An optimal algorithm for computing the minimum vertex distance between two crossing convex polygons
• A novel approach for ellipsoidal outer-approximation of the intersection region of ellipses in the plane
• A local search algorithm for ray-convex polyhedron intersection
• A simple linear algorithm for intersecting convex polygons
• Title not available (Why is that?)
• Developing scheduling systems for Daewoo shipbuilding: DAS project
• An improved algorithm for intersecting convex polygons
• A simpler linear-time algorithm for intersecting two convex polyhedra in three dimensions
• Title not available (Why is that?)
• Investigation of modeling non-spherical particles by using spherical discrete element model with rolling friction
• Predicting mesh density for adaptive modelling of the global atmosphere
• Optimal output-sensitive convex hull algorithms in two and three dimensions
• Title not available (Why is that?)
• Restricted center problems under polyhedral gauges
• An efficient algorithm for the computation of the metric average of two intersecting convex polygons, with application to morphing
• Fixed-radius near neighbors search algorithms for points and segments
• A Minkowski difference‐based advancing front packing technique for generating convex noncircular particles in complex domains
• Title not available (Why is that?)
• EDGE ADVANCING RULES FOR INTERSECTING SPHERICAL CONVEX POLYGONS
• An application of the onion peeling algorithm for fingerprint verification purposes
• Common intersections of polygons
• Detecting the intersection of convex objects in the plane
• A linear algorithm for determining the separation of convex polyhedra
• Intersection of unit-balls and diameter of a point set in \(\mathbb R^3\).
• Parallel computation of bivariate point data depths and display of intrinsic depth segments
• A SIMPLE FACTOR-2/3 APPROXIMATION ALGORITHM FOR TWO-CIRCLE POINT LABELING

This page was built for publication: A new 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 Q3316124)