How to cut corners and get bounded convex curvature

DOI10.1007/S00454-022-00404-WMaRDI QIDQ6045790zbMATH OpenWikidataFDO

Authors Mikkel Abrahamsen, Mikkel Thorup

Publication date 12 May 2023

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.02080

zbMATH Keywords

bounded curvaturecircular ray shootingpocket machining

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Analysis of algorithms (68W40)

Abstract: We describe an algorithm for solving an important geometric problem arising in computer-aided manufacturing. When cutting away a region from a solid piece of material -- such as steel, wood, ceramics, or plastic -- using a rough tool in a milling machine, sharp convex corners of the region cannot be done properly, but have to be left for finer tools that are more expensive to use. We want to determine a toolpath that maximizes the use of the rough tool. In order to formulate the problem in mathematical terms, we introduce the notion of bounded convex curvature. A region of points in the plane $Q$ has emph{bounded convex curvature} if for any point $xinpartialQ$, there is a unit disk $U$ and $varepsilon>0$ such that $xinpartialU$ and all points in $U$ within distance $varepsilon$ from $x$ are in $Q$. This translates to saying that as we traverse the boundary $partialQ$ with the interior of $Q$ on the left side, then $partialQ$ turns to the left with curvature at most $1$. There is no bound on the curvature where $partialQ$ turns to the right. Given a region of points $P$ in the plane, we are now interested in computing the maximum subset $QsubseteqP$ of bounded convex curvature. The difference in the requirement to left- and right-curvature is a natural consequence of different conditions when machining convex and concave areas of $Q$. We devise an algorithm to compute the unique maximum such set $Q$, when the boundary of $P$ consists of $n$ line segments and circular arcs of arbitrary radii. In the general case where $P$ may have holes, the algorithm runs in time $O(n^2)$ and uses $O(n)$ space. If $P$ is simply-connected, we describe a faster $O(nlogn)$ time algorithm.

Cites work

• A Pedestrian Approach to Ray Shooting: Shoot a Ray, Take a Walk
• Algebraic methods and arithmetic filtering for exact predicates on circle arcs
• An O(n log n) algorithm for the Voronoi diagram of a set of simple curve segments
• Curvature-Constrained Shortest Paths in a Convex Polygon
• Disks in curves of bounded convex curvature
• Finding the Maximum Subset with Bounded Convex Curvature
• Hierarchical decompositions and circular ray shooting in simple polygons
• scientific article; zbMATH DE number 1670669 (Why is no real title available?)
• scientific article; zbMATH DE number 3141684 (Why is no real title available?)
• scientific article; zbMATH DE number 5764825 (Why is no real title available?)
• Length minimising bounded curvature paths in homotopy classes
• Pocket machining based on contour-parallel tool paths generated by means of proximity maps
• Ray shooting in polygons using geodesic triangulations
• Reachability by paths of bounded curvature in a convex polygon
• Visibility and ray shooting queries in polygonal domains
• Voronoi diagrams and offset curves of curvilinear polygons.

This page was built for publication: How to cut corners and get bounded convex curvature

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