Content deleted Content added
m Task 18 (cosmetic): eval 20 templates: hyphenate params (1×); |
→Parallel curves of an implicit curve: parabola |
||
| (36 intermediate revisions by 25 users not shown) | |||
Line 1:
{{Short description|Generalization of the concept of parallel lines}}
{{
[[File:Offset-curves-of-sinus-curve.svg|300px|thumb|Parallel curves of the graph of <math>y=1.5 \sin(x)</math> for distances <math>d = 0.25, \dots, 1.5 </math>]]▼
[[File:Offset-definition-poss.svg|300px|thumb|Two definitions of a parallel curve: 1) envelope of a family of congruent circles, 2) by a fixed normal distance]]
[[File:Offset-of-a-circle.svg|thumb|The parallel curves of a circle (red) are circles, too]]▼
It generalises the concept of ''[[parallel (geometry)|parallel (straight) lines]]''. It can also be defined as a curve whose points are at a constant ''[[normal distance]]'' from a given curve.<ref name="Willson">{{cite book▼
▲*[[envelope (mathematics)|envelope]] of a family of congruent [[circle]]s centered on the curve.
▲It generalises the concept of [[parallel (geometry)|parallel lines]]. It can also be defined as a
|title=Theoretical and Practical Graphics
|first1=Frederick Newton
Line 19 ⟶ 16:
These two definitions are not entirely equivalent as the latter assumes [[smoothness]], whereas the former does not.<ref name="DevadossO'Rourke2011">{{cite book|first1=Satyan L.|last1= Devadoss|author1-link= Satyan Devadoss |first2=Joseph |last2=O'Rourke|author2-link=Joseph O'Rourke (professor)|title=Discrete and Computational Geometry|url=https://books.google.com/books?id=InJL6iAaIQQC&pg=PA128|year=2011|publisher=Princeton University Press|isbn=978-1-4008-3898-1|pages=128–129}}</ref>
▲[[File:Offset-of-a-circle.svg|thumb|The parallel curves of a circle (red) are
In [[computer-aided design]] the preferred term for a parallel curve is '''offset curve'''.<ref name="DevadossO'Rourke2011"/><ref name="SendraWinkler2007"/><ref name="Agoston2005m">{{cite book|first=Max K.|last= Agoston|title=Computer Graphics and Geometric Modelling: Mathematics|url=https://books.google.com/books?id=LPsAM-xuGG8C&pg=PA586|year=2005|publisher=Springer Science & Business Media|isbn=978-1-85233-817-6|page=586}}</ref> (In other geometric contexts, the term [[offset (disambiguation)|
In the area of 2D [[computer graphics]] known as [[vector graphics]], the (approximate) computation of parallel curves is involved in one of the fundamental drawing operations, called stroking, which is typically applied to [[polyline]]s or [[polybezier]]s (themselves called paths) in that field.<ref name="Kilgard">
▲[[File:Offset-curves-of-sinus-curve.svg|300px|thumb|Parallel curves of the graph of <math>y=1.5 \sin(x)</math> (in red) for distances <math>d = 0.25, \dots, 1.5 </math>]]
Except in the case of a line or [[circle]], the parallel curves have a more complicated mathematical structure than the progenitor curve.<ref name="Willson"/> For example, even if the progenitor curve is [[Smooth function|smooth]], its offsets may not be so; this property is illustrated in the top figure, using a [[sine curve]] as progenitor curve.<ref name="DevadossO'Rourke2011"/> In general, even if a curve is [[rational curve|rational]], its offsets may not be so. For example, the offsets of a parabola are rational curves, but the offsets of an [[ellipse]] or of a [[hyperbola]] are not rational, even though these progenitor curves themselves are rational.<ref name="SendraWinkler2007">{{cite book|first1=J. Rafael |last1=Sendra|first2=Franz|last2= Winkler|first3=Sonia |last3=Pérez Díaz|title=Rational Algebraic Curves: A Computer Algebra Approach|url=https://books.google.com/books?id=puWxs7KG2D0C&pg=PA10|year=2007|publisher=Springer Science & Business Media|isbn=978-3-540-73724-7|page=10}}</ref>
The notion also generalizes to 3D [[surface (mathematics)|surface]]s, where it is called an '''offset surface''' or '''parallel surface'''.<ref name="Agoston2005"/> Increasing a [[solid (geometry)|solid]] volume by a (constant) distance offset is sometimes called ''dilation'' (similar to the [[dilation (morphology)|dilation]] image operation).<ref name="jarek">http://www.cc.gatech.edu/~jarek/papers/localVolume.pdf, p. 3</ref> The opposite operation is sometimes called ''shelling''.<ref name="Agoston2005">{{cite book|first=Max K.|last= Agoston|title=Computer Graphics and Geometric Modelling|url=https://books.google.com/books?id=fGX8yC-4vXUC&pg=PA645|year=2005|publisher=Springer Science & Business Media|isbn=978-1-85233-818-3|pages=638–645}}</ref> Offset surfaces are important in
== Parallel curve of a parametrically given curve ==
Line 35 ⟶ 34:
:<math> y_d(t)= y(t)-\frac{d\; x'(t)}{\sqrt {x'(t)^2+y'(t)^2}} \ .</math>
===Geometric properties:<ref name="hart30">E. Hartmann: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf ''Geometry and Algorithms for COMPUTER AIDED DESIGN.''] S. 30.</ref>===
Line 41 ⟶ 40:
*<math>k_d(t)=\frac{k(t)}{1+dk(t)},\quad</math> with <math>k(t)</math> the [[curvature]] of the given curve and <math>k_d(t)</math> the curvature of the parallel curve for parameter <math>t</math>.
*<math>R_d(t)=R(t) + d,\quad</math> with <math>R(t)</math> the [[curvature#Curvature of plane curves|radius of curvature]] of the given curve and <math>R_d(t)</math> the radius of curvature of the parallel curve for parameter <math>t</math>.
* When they exist, the [[Osculating circle|osculating circles]] to parallel curves at corresponding points are concentric. <ref>Fiona O'Neill: [https://fionasmathblog.com/2022/04/26/planar-bertrand-curves-with-pictures/ ''Planar Bertrand Curves (with Pictures!).''] {{Webarchive|url=https://web.archive.org/web/20221011143632/https://fionasmathblog.com/2022/04/26/planar-bertrand-curves-with-pictures/ |date=2022-10-11 }}</ref>
*As for [[parallel (geometry)|parallel lines]], a normal line to a curve is also normal to its parallels.
*When parallel curves are constructed they will have [[Cusp (singularity)|cusp]]s when the distance from the curve matches the radius of [[curvature]]. These are the points where the curve touches the [[evolute]].
*If the progenitor curve is a boundary of a planar set and its parallel curve is without self-intersections, then the latter is the boundary of the [[Minkowski sum]] of the planar set and the disk of the given radius.
If the given curve is polynomial (meaning that <math>x(t)</math> and <math>y(t)</math> are polynomials), then the parallel curves are usually not polynomial. In CAD area this is a drawback, because CAD systems use polynomials or rational curves. In order to get at least rational curves, the square root of the representation of the parallel curve has to be solvable. Such curves are called
''Pythagorean-Hodograph Curves: Algebra and Geometry Inseparable (Geometry and Computing).'' Springer, 2008, {{ISBN|978-3-540-73397-3}}.</ref>
== Parallel curves of an implicit curve ==
[[File:Offset-of-implicit-curve-c4.svg|250px|thumb|Parallel curves of
For example:
: ''Line'' <math>\; f(x,y)=x+y-1=0\; </math> → distance function: <math>\; h(x,y)=\frac{x+y-1}{\sqrt{2}}=d\; </math> (Hesse normalform)
: ''Circle'' <math>\; f(x,y)=x^2+y^2-1=0\;</math> →
In general, presuming certain conditions, one can prove the existence of an [[oriented distance function]] <math>h(x,y)</math>. In practice one has to treat it numerically.<ref>E. Hartmann: [http://www.mathematik.tu-darmstadt.de/~ehartmann/cdgen0104.pdf ''Geometry and Algorithms for COMPUTER AIDED DESIGN.''] S. 81, S. 30, 41, 44.</ref> Considering parallel curves the following is true:
* The parallel curve for distance d is the [[level set]] <math>h(x,y)=d</math> of the corresponding oriented distance function <math>h</math>.
===Properties of the distance function:<ref name="hart30" />
*<math>| \operatorname{grad} h (\vec x)|=1 \; ,</math>
* <math> h(\vec x+d\operatorname{grad} h (\vec x)) = h(\vec x)+d \; ,</math>
Line 64:
'''Example:'''<br />
The diagram shows parallel curves of the implicit curve with equation <math>\; f(x,y)=x^4+y^4-1=0\; .</math> <br />
''Remark:''
The curves <math>\; f(x,y)=x^4+y^4-1=d\; </math> are not parallel curves, because <math>\; | \operatorname{grad} f (x,y)|=1 \;</math> is not true in the area of interest.
Line 72:
*The [[involute]]s of a given curve are a set of parallel curves. For example: the involutes of a circle are parallel spirals (see diagram).
And:<ref name="farouki-slides">http://faculty.engineering.ucdavis.edu/farouki/wp-content/uploads/sites/41/2013/02/Introduction-to-PH-curves.pdf {{Webarchive|url=https://web.archive.org/web/20150605214546/http://faculty.engineering.ucdavis.edu/farouki/wp-content/uploads/sites/41/2013/02/Introduction-to-PH-curves.pdf |date=2015-06-05 }}, p. 16 "taxonomy of offset curves"</ref>
* A [[parabola]] has as (two-sided) offsets [[rational curve]]s of degree 6.
* A [[hyperbola]] or an [[ellipse]] has as (two-sided) offsets an [[algebraic curve]] of degree 8.
* A [[Bézier curve]] of degree {{mvar|n}} has as (two-sided) offsets [[algebraic curve]]s of degree {{math|4''n'' − 2}}. In particular, a cubic
==Parallel curve to a curve with a corner==
Line 81:
When determining the cutting path of part with a sharp corner for [[machining]], you must define the parallel (offset) curve to a given curve that has a discontinuous normal at the corner. Even though the given curve is not smooth at the sharp corner, its parallel curve may be smooth with a continuous normal, or it may have [[Cusp (singularity)|cusp]]s when the distance from the curve matches the radius of [[curvature]] at the sharp corner.
===Normal fans===
As described [[#Parallel curve of a parametrically given curve|above]], the parametric representation of a parallel curve, <math>\vec x_d(t)</math>, to a given curver, <math>\vec x(t)</math>, with distance <math>|d|</math> is:
Line 101:
== Algorithms ==
{{expand section|date=August 2014}}
An efficient algorithm for offsetting is the level approach described by▼
In general, the parallel curve of a [[Bézier curve]] is not another Bézier curve, a result proved by Tiller and Hanson in 1984.<ref>{{cite journal |last1=Tiller |first1=Wayne |last2=Hanson |first2=Eric |title=Offsets of Two-Dimensional Profiles |journal=IEEE Computer Graphics and Applications |year=1984 |volume=4 |issue=9 |pages=36–46 |doi=10.1109/mcg.1984.275995|s2cid=9046817 }}</ref> Thus, in practice, approximation techniques are used. Any desired level of accuracy is possible by repeatedly subdividing the curve, though better techniques require fewer subdivisions to attain the same level of accuracy. A 1997 survey by Elber, Lee and Kim<ref>{{cite journal |last1=Elber |first1=Gershon |last2=Lee |first2=In-Kwon |last3=Kim |first3=Myung-Soo
|doi=10.1109/38.586019 |title=Comparing offset curve approximation methods |journal=IEEE Computer Graphics and Applications |volume=17 |issue=3 |pages=62–71 |date=May–Jun 1997}}</ref> is widely cited, though better techniques have been proposed more recently. A modern technique based on [[curve fitting]], with references and comparisons to other algorithms, as well as open source JavaScript source code, was published in a blog post<ref>{{cite web |url=https://raphlinus.github.io/curves/2022/09/09/parallel-beziers.html |title=Parallel curves of cubic Béziers |last=Levien |first=Raph |date=September 9, 2022 |access-date=September 9, 2022}}</ref> in September 2022.
[[Ron Kimmel|Kimmel]] and Bruckstein (1993).<ref>{{cite journal | last1=Kimmel | first1=R. | last2=Bruckstein | first2=A.M. | title=Shape offsets via level sets | journal=Computer-Aided Design | publisher=Elsevier BV | volume=25 | issue=3 | year=1993 | issn=0010-4485 | doi=10.1016/0010-4485(93)90040-u | pages=154–162 | s2cid=8434463 |url=https://www.cs.technion.ac.il/~ron/PAPERS/offsets_cad1993.pdf}}</ref>
== Parallel (offset) surfaces ==
Line 122 ⟶ 119:
*<math>{\partial \vec x_d \over \partial u} \parallel {\partial \vec x \over \partial u}, \quad {\partial \vec x_d \over \partial v} \parallel {\partial \vec x \over \partial v}, \quad</math> that means: the tangent vectors for fixed parameters are parallel.
*<math>\vec n_d(u,v) = \pm\vec n(u,v), \quad</math> that means: the normal vectors for fixed parameters match direction.
*<math>S_d = (1 + d S)^{-1} S, \quad</math> where <math>S_d</math> and <math>S</math> are the [[
:The principal curvatures are the [[Eigenvalues and eigenvectors|eigenvalues]] of the [[
*<math>S_d^{-1} = S^{-1} + d I, \quad</math> where <math>S_d^{-1}</math> and <math>S^{-1}</math> are the inverses of the [[
:The principal radii of curvature are the [[Eigenvalues and eigenvectors|eigenvalues]] of the inverse of the [[
Note the similarity to the geometric properties of [[#Parallel curve of a parametrically given curve|parallel curves]].
== Generalizations ==
The problem generalizes fairly obviously to higher dimensions e.g. to offset surfaces, and slightly less trivially to [[pipe surface]]s.<ref name="PottmannWallner2001">{{cite book|first1=Helmut|last1=Pottmann|first2=Johannes|last2=Wallner|title=Computational Line Geometry|url=https://books.google.com/books?id=6ZrqcYKgtE0C&pg=PA303|year=2001|publisher=Springer Science & Business Media|isbn=978-3-540-42058-3|pages=303–304}}</ref> Note that the terminology for the higher-dimensional versions varies even more widely than in the planar case, e.g. other authors speak of parallel fibers, ribbons, and tubes.<ref name="Chirikjian2009">{{cite book|author1-link=Gregory S. Chirikjian|first=Gregory S.|last=Chirikjian|title=Stochastic Models, Information Theory, and Lie Groups, Volume 1: Classical Results and Geometric Methods|year=2009|publisher=Springer Science & Business Media|isbn=978-0-8176-4803-9|pages=171–175}}</ref> For curves embedded in 3D surfaces the offset may be taken along a [[geodesic]].<ref name="Sarfraz2003">{{cite book|editor-first=Muhammad|editor-last=Sarfraz|title=Advances in geometric modeling|url=https://books.google.com/books?id=kfZQAAAAMAAJ&pg=PA72|year=2003|publisher=Wiley|isbn=978-0-470-85937-7|page=72}}</ref>
Another way to generalize it is (even in 2D) to consider a variable distance, e.g. parametrized by another curve.<ref name="barn"/> One can for example stroke (envelope) with an ellipse instead of circle<ref name="barn"/> as it is possible for example in [[METAFONT]].<ref>{{Cite journal |last=Kinch |first=Richard J. |date=1995 |title=MetaFog: Converting METAFONT Shapes to Contours |url=https://www.tug.org/TUGboat/tb16-3/tb48kinc.pdf |journal=TUGboat |volume=16 |issue=3 |pages=233–243}}</ref>
[[File:Envelope of ellipses.png|thumb|An envelope of ellipses forming two general offset curves above and below a given curve]]
More recently [[Adobe Illustrator]] has added somewhat similar facility in version [[CS5]], although the control points for the variable width are visually specified.<ref>http://design.tutsplus.com/tutorials/illustrator-cs5-variable-width-stroke-tool-perfect-for-making-tribal-designs--vector-4346 application of the generalized version in Adobe Illustrator CS5 (also [http://tv.adobe.com/watch/learn-illustrator-cs5/using-variablewidth-strokes/ video])</ref> In contexts where it's important to distinguish between constant and variable distance offsetting the acronyms CDO and VDO are sometimes used.<ref name="jarek"/>
Line 140 ⟶ 137:
:<math> \vec x_d(t)=\vec x(t)+ \vec d(\vec n(t)), \quad</math> where <math>\vec n(t)</math> is the unit normal of <math>\vec x(t)</math>.
Note that the trival offset, <math>\vec d(\vec n) = d\vec n</math>, gives you ordinary parallel (aka, offset) curves.
====Geometric properties:<ref name="barn"/>====
*<math>\vec x'_d(t) \parallel \vec x'(t),\quad</math> that means: the tangent vectors for a fixed parameter are parallel.
Line 152 ⟶ 150:
:<math> \vec x_d(u,v)=\vec x(u,v)+ \vec d(\vec n(u,v)), \quad</math> where <math>\vec n(u,v)</math> is the unit normal of <math>\vec x(u,v)</math>.
Note that the trival offset, <math>\vec d(\vec n) = d\vec n</math>, gives you ordinary parallel (aka, offset) surfaces.
====Geometric properties:<ref name="barn"/>====
*As for [[parallel (geometry)|parallel lines]], the tangent plane of a surface is parallel to the tangent plane of its general offsets.
*As for [[parallel (geometry)|parallel lines]], a normal to a surface is also normal to its general offsets.
*<math>S_d = (1 + SS_n^{-1})^{-1} S, \quad</math> where <math>S_d, S,</math> and <math>S_n</math> are the [[
:The principal curvatures are the [[Eigenvalues and eigenvectors|eigenvalues]] of the [[
*<math>S_d^{-1} = S^{-1} + S_n^{-1}, \quad</math> where <math>S_d^{-1}, S^{-1}</math> and <math>S_n^{-1}</math> are the inverses of the [[
:The principal radii of curvature are the [[Eigenvalues and eigenvectors|eigenvalues]] of the inverse of the [[
Note the similarity to the geometric properties of [[#General offset curves|general offset curves]].
Line 170 ⟶ 169:
Notice, the tangent vectors for <math>\vec x_d</math> are the sum of tangent vectors for <math>\vec x(\vec u)</math> and its offset <math> \vec d(\vec n)</math>, which share the same unit normal. Thus, '''the general offset surface shares the same tangent plane and normal with''' <math>\vec x(\vec u)</math> and <math>\vec d(\vec n(\vec u))</math>. That aligns with the nature of envelopes.
We now consider the [[Weingarten equations]] for the [[
Substituting into the equation for the differential of <math>\vec x_d</math>, we get:
Line 192 ⟶ 191:
==References==
{{
* Josef Hoschek: ''Offset curves in the plane.'' In: ''CAD.'' 17 (1985), S. 77–81.
* Takashi Maekawa: ''An overview of offset curves and surfaces.'' In: ''CAD.'' 31 (1999), S. 165–173.
Line 201 ⟶ 200:
* {{cite book|first=Ian R. |last=Porteous|title=Geometric Differentiation: For the Intelligence of Curves and Surfaces|year=2001|publisher=Cambridge University Press|isbn=978-0-521-00264-6|pages=1–25|edition=2nd}}
* {{cite book|first1=Nicholas M. |last1=Patrikalakis|first2=Takashi |last2=Maekawa|title=Shape Interrogation for Computer Aided Design and Manufacturing|year=2010|orig-year=2002|publisher=Springer Science & Business Media|isbn=978-3-642-04074-0|at=Chapter 11. Offset Curves and Surfaces}} [http://web.mit.edu/hyperbook/Patrikalakis-Maekawa-Cho/node210.html Free online version].
* {{cite conference |
* {{cite book |first=Rida T. |last=Farouki |title=Pythagorean-Hodograph Curves: Algebra and Geometry Inseparable |year=2008 |publisher=Springer Science & Business Media |isbn=978-3-540-73397-3 |
* {{cite book |editor-first=Y.-S. |editor-last=Ma |title=Semantic Modeling and Interoperability in Product and Process Engineering: A Technology for Engineering Informatics |year=2013 |publisher=Springer Science & Business Media |isbn=978-1-4471-5073-2 |chapter=Computation of Offset Curves Using a Distance Function: Addressing a Key Challenge in Cutting Tool Path Generation |first1=C. K. |last1=Au |first2=Y.-S. |last2=Ma |pages=259–273}}
Line 208 ⟶ 207:
*[http://mathworld.wolfram.com/ParallelCurves.html Parallel curves on MathWorld]
*[http://xahlee.org/SpecialPlaneCurves_dir/Parallel_dir/parallel.html Visual Dictionary of Plane Curves] Xah Lee
{{Differential transforms of plane curves}}
{{Authority control}}
{{DEFAULTSORT:Parallel Curve}}
| |||