ABSTRACT (original article): Designing mechanical devices, called linkages, that draw a given plane curve has been a topic that interested engineers and mathematicians for hundreds of years, and recently also computer scientists. Already in 1876, Kempe proposed a procedure for solving the problem in full generality, but his constructions tend to be extremely complicated. We provide a novel algorithm that produces much simpler linkages, but works only for parametric curves. Our approach is to transform the problem into a factorization task over some noncommutative algebra. We show how to compute such a factorization, and how to use it to construct a linkage tracing a given curve. CITATION (original article): Matteo Gallet, Christoph Koutschan, Zijia Li, Georg Regensburger, Josef Schicho and Nelly Villamizar, Planar linkages following a prescribed motion, Math. Comp. 86 (2017), 473-506. http://dx.doi.org/10.1090/mcom/3120.
PREPRINT: https://arxiv.org/abs/1502.05623
PACKAGE HOMEPAGE: http://www.koutschan.de/data/link/
PREPRINT: https://arxiv.org/abs/1502.05623
PACKAGE HOMEPAGE: http://www.koutschan.de/data/link/
Demo
Demo
In[]:=
SetDirectory[NotebookDirectory[]];Get["PlanarLinkages.m"];
PlanarLinkages — Copyright © 2015 Christoph Koutschan
This program comes with absolutely no warranty; it is free software,
and you are welcome to redistribute it and/or modify it under the
terms of the GNU General Public License (http://www.gnu.org/licenses/).
This program comes with absolutely no warranty; it is free software,
and you are welcome to redistribute it and/or modify it under the
terms of the GNU General Public License (http://www.gnu.org/licenses/).
Arithmetic of motion polynomials
Arithmetic of motion polynomials
Motion polynomials are input using the symbol “eta”.
t+I+eta*(2-I)
(+t)+η·(2-)
When Times is used, eta is always interpreted to be on the left.
{I*eta,eta*I}
{0+η·,0+η·}
To specify the order of factors, use NonCommutativeMultiply.
{I**eta,eta**I}
{0-η·,0+η·}
In the same fashion, motion polynomials can be multiplied.
(t+1-eta)**(t^2+1+2I+eta*I*t)
((1+2)+(1+2)t++)+η·((-1-2)+t-(1-))
2
t
3
t
2
t
See how motion polynomials are represented internally.
z+eta*wFullForm[%]
z+η·w
MP[z,w]
Check the multiplication of motion polynomials (a+eta*b)*(c+eta*d).
MP[,]**MP[,]
z
1
w
1
z
2
w
2
z
1
z
2
z
1
w
2
w
1
z
2
Invert an element in SE2. Note that real numbers in K correspond to 1 in SE2.
FullSimplify[(z+eta*w)**(Conjugate[z]-eta*w)]
2
Abs[z]
Action of SE2
Action of
SE
2
?ActR2
ActR2[p, {x, y}] computes the result of applying the direct isometry given by p to the point {x, y}, where p is a (possibly constant) motion polynomial.
Action of SE2.
In[]:=
vec=ActR2[MP[+I*,+I*],{x,y}];Together[Simplify[vec,Element[{,,,},Reals]]]
x
1
x
2
y
1
y
2
x
1
x
2
y
1
y
2
Out[]=
+,+
x-2y-x+-
2
x
1
x
1
x
2
2
x
2
x
1
y
1
x
2
y
2
2
x
1
2
x
2
y+2x-y++
2
x
1
x
1
x
2
2
x
2
x
2
y
1
x
1
y
2
2
x
1
2
x
2
Product in SE2 is bilinear.
In[]:=
prod=ComplexExpand/@(MP[+I*,+I*]**MP['+I*','+I*'])
x
1
x
2
y
1
y
2
x
1
x
2
y
1
y
2
Out[]=
(-+(+))+η·(-+++(+-+))
x
1
′
x
1
x
2
′
x
2
x
2
′
x
1
x
1
′
x
2
y
1
′
x
1
y
2
′
x
2
x
1
′
y
1
x
2
′
y
2
y
2
′
x
1
y
1
′
x
2
x
2
′
y
1
x
1
′
y
2
TableForm[Flatten[CoefficientList[List@@prod/.Ii,i]]]
x 1 ′ x 1 x 2 ′ x 2 |
x 2 ′ x 1 x 1 ′ x 2 |
y 1 ′ x 1 y 2 ′ x 2 x 1 ′ y 1 x 2 ′ y 2 |
y 2 ′ x 1 y 1 ′ x 2 x 2 ′ y 1 x 1 ′ y 2 |
Fixpoint of a motion
Fixpoint of a motion
?FixPoint
FixPoint[p] computes the fixpoint of a simple revolution given by the linear normed motion polynomial p, i.e., p is of the form t - z + η*w where z and w are complex numbers with z being non-real.
Compute the fixpoint of a motion.
FixPoint[t+I-eta*0]
{0,0}
FixPoint[t+eta]
Throw::nocatch:Uncaught Throw[FixPoint: Input is not a normed bounded motion polynomial of degree 1.] returned to top level.
Hold[Throw[FixPoint: Input is not a normed bounded motion polynomial of degree 1.]]
Test fixpoint formula.
FixPoint[t-α-eta*β]FullSimplify[(First[%]+I*Last[%])-β/(Conjugate[α]-α)]
-,
Im[β]
2Im[α]
Re[β]
2Im[α]
0
Factorization of motion polynomials
Factorization of motion polynomials
Factor a motion polynomial into linear factors.
FactorMP[(t+I)^6+eta*t]
(+t)+η··(+t)-η··(+t)+η··(+t)+η··(+t)-η··(+t)+η·
1
32
3
32
1
16
1
16
3
32
1
32
Expand again.
Expand[%]
(-1+6t+15-20-15+6+)+η·t
2
t
3
t
4
t
5
t
6
t
Now with factored coefficients.
Factor/@%
6
(+t)
Data structure used for representing factored motion polynomials.
FactoredMP[eta,eta,eta]Expand[%]
(0+η)·(0+η)·(0+η)
0+η·0
This polynomial admits several factorizations (actually 5! = 120).
In[]:=
FactorMP[poly=Product[t-kI,{k,5}]+eta*(t+I)]
Out[]=
((-+t)+η·0)·(-2+t)-η··(-3+t)+η··(-4+t)-η··(-5+t)+η·
210
3
280
126
504
This is an other factorization using a different order of the roots.
In[]:=
FactorMP[poly,OrderTable[kI,{k,5,1,-1}]]
Out[]=
Hold[Throw[The given zeros must contain all zeros of Z (with multiplicity!).]]
Here not any permutation of the roots yields a factorization.
In[]:=
poly=(t^2+1)^2*(t+2I)+eta*(t+I)^2;FactorMP[poly]FactorMP[poly,Order{-I,-I,I,I,-2I}]
Out[]=
(-+t)+η·+·(-+t)+η·-+·((+t)-η·)·((+t)-η·)·(2+t)-η·
5
18
1
1
6
2
2
1
1
9
Out[]=
Hold[Throw[No solution found.]]
Elliptic translational motion.
The polynomial cannot be factored, unless we multiply it by t^2+1.
The polynomial cannot be factored, unless we multiply it by t^2+1.
In[]:=
poly=t^2+1+eta*(a*t-b*I)fact=FactorMP[poly]
Out[]=
(1+)+η·(-b+at)
2
t
2
t
Out[]=
(+t)+η·++·((-+t)-η·)·(-+t)+η·-+·((+t)-η·)
a
2
b
2
2
2
a
2
b
2
1
1
In[]:=
(*Dothisfactorization"by hand".*)ansatz=FactoredMP@@Table[t+(-1)^Ceiling[(k-1)/2]*I+eta*w[k],{k,4}](*Deriveasystemofequations.*)Union[CoefficientList[Last[Expand[ansatz]-(t^2+1)*poly],t]](*Testwhetherthecoefficientsoffact[[2]]satisfythesystem.*)Expand[%/.w[k_]fact[[k,2]]]
Out[]=
((+t)+η·w[1])·((-+t)+η·w[2])·((-+t)+η·w[3])·((+t)+η·w[4])
Out[]=
{b-w[1]-w[2]+w[3]+w[4],-a+w[1]+w[2]+w[3]+w[4]}
All 6 factorizations of a “random” degree 3 motion polynomial.
Show their linkages.
Animation of a motion
Animation of a motion
Animation of a simple revolution.
A horizontal translational motion.
A vertical translational motion.
Construction of linkages
Construction of linkages
Circular translation.
Show different decompositions of this motion depending on the choice of C[1].
Define a linkage by constructing its link graph.
A degree 6 motion polynomial that allows only a single factorization.
A different polynomial that produces basically the same curve.
Example 4.4 from the paper
Example 4.4 from the paper
Check cycle condition (with quick-and-dirty way of inverting P1 and P3).
Example: a simple quadratic motion polynomial
Example: a simple quadratic motion polynomial
A quadratic motion.
Now factor this quadratic polynomial into linear factors.
Test whether the factorization is correct.
Animation of the factored motion.
Different style of animation.
Compute the second factorization.
Show the corresponding linkage.
Create movie ToyExample.mp4
Example: elliptic translation
Example: elliptic translation
We consider the ellipse given by the equation (x+1)^2 + 4*y^2 1.
We use the following parametrization.
This translates into the following motion polynomial, realizing a translational motion along the ellipse.
To factor this motion polynomial, it is multiplied by t^2+1. We obtain a 2-parameter family of factorizations.
This is a factorization with different order of the roots.
Using the first factorization, we can construct a linkage which strongly realizes the translational motion along the ellipse.
Multiplying with t-I from the left also enables us to find a factorization. By doing so we change the motion (it is not any more a translational one). However, the orbit of the origin under this new motion is still the ellipse.
Choose some value for the parameter of this one-dimensional family of factorizations.
Use this factorization to construct a linkage. The second argument is a linear motion polynomial that can be chosen almost randomly. With some experiments, we found this one which gives a nice-looking linkage.
Rename the labels such that they agree with those in the paper.
Define some coloring of the links.
Now the motion produced by the end effector is not any more translational.
Define an order of the links. This produces 5 collisions at t=∞. This is the ordering produced by our code in ConstructLinkage. Also the pen collides only at t=∞.
Here is a different ordering, figured out by hand. It produces only 2 collisions, both at t=∞. Also the pen collides only at t=∞.
In order to build the linkage, compute integral lengths of the links. For each link the positions of the joints connected to it are given, namely their x-coordinates in the initial configuration of the linkage.
Create movie Ellipse.mp4
Create movie Ellipse3D.mp4
Create the picture shown in the paper.
Construct a collision-free linkage using some links of special shape.
Display the collision-free linkage.
Example: John Hancock’s “J”
Example: John Hancock’s “J”
Our parametrization {x/d, y/d} of Hancock’s J.
Choose values for the free parameters.
Construct the linkage and show the link graph.
Some options for drawing this linkage
2D animation
3D animation using a different style for the links
3D animation with a different ordering of the links
Produce the picture shown in the paper. Use “/200” for the steps in TraceMP.
The speed of the pen is not very uniform.
Use non-constant time steps.
Generate pictures for movie HancockJ.mp4.
If we stack the links according to their labels, we get lots of collisions.
Observe the 2nd and 3rd collision in the animation.
This ordering of the links has only 6 collisions, but the pen is not on top.
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Planar linkages following a prescribed motion
by Christoph Koutschan
Wolfram Community, STAFF PICKS, April 17 2023
https://community.wolfram.com/groups/-/m/t/2900251
by Christoph Koutschan
Wolfram Community, STAFF PICKS, April 17 2023
https://community.wolfram.com/groups/-/m/t/2900251