How to Cut Corners and Get Bounded Convex Curvature
Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Standard
How to Cut Corners and Get Bounded Convex Curvature. / Abrahamsen, Mikkel; Thorup, Mikkel.
I: Discrete and Computational Geometry, Bind 69, 2023, s. 1195–1231,.Publikation: Bidrag til tidsskrift › Tidsskriftartikel › Forskning › fagfællebedømt
Harvard
APA
Vancouver
Author
Bibtex
}
RIS
TY - JOUR
T1 - How to Cut Corners and Get Bounded Convex Curvature
AU - Abrahamsen, Mikkel
AU - Thorup, Mikkel
N1 - Publisher Copyright: © 2022, The Author(s), under exclusive licence to Springer Science+Business Media, LLC, part of Springer Nature.
PY - 2023
Y1 - 2023
N2 - 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 bounded convex curvature if for any point x∈ ∂Q, there is a unit disk U and ε> 0 such that x∈ ∂U and all points in U within distance ε from x are in Q. This translates to saying that as we traverse the boundary ∂Q with the interior of Q on the left side, then ∂Q turns to the left with curvature at most 1. There is no bound on the curvature where ∂Q turns to the right. Given a region of points P in the plane, we are now interested in computing the maximum subset Q⊆ P 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(n2) and uses O(n) space. If P is simply-connected, we describe a faster O(nlog n) time algorithm.
AB - 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 bounded convex curvature if for any point x∈ ∂Q, there is a unit disk U and ε> 0 such that x∈ ∂U and all points in U within distance ε from x are in Q. This translates to saying that as we traverse the boundary ∂Q with the interior of Q on the left side, then ∂Q turns to the left with curvature at most 1. There is no bound on the curvature where ∂Q turns to the right. Given a region of points P in the plane, we are now interested in computing the maximum subset Q⊆ P 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(n2) and uses O(n) space. If P is simply-connected, we describe a faster O(nlog n) time algorithm.
KW - Bounded curvature
KW - Circular ray shooting
KW - Pocket machining
U2 - 10.1007/s00454-022-00404-w
DO - 10.1007/s00454-022-00404-w
M3 - Journal article
AN - SCOPUS:85134321506
VL - 69
SP - 1195–1231,
JO - Discrete & Computational Geometry
JF - Discrete & Computational Geometry
SN - 0179-5376
ER -
ID: 316818646