Snake Problem
Kevin Hamer
isn't. I was trying to figure out how to make a snake robot follow a curve,
by finding all of the angles in between the segments of the robot. So, most
of the problem isn't that difficult, but here is the hard first step:
I want to fit the snake on [0,2*Pi] to y=sin(x). The snake has n segments.
if the first 'joint' of the snake is at (0,0), and the last one is at
(0,2*Pi), what is the angle between the X-axis and the first segment of the
snake based upon n if all the snake segments are the same length?
Example:
If n=1, the angle is 0, and it's 1 flat line segment.
If n=2, the angle is 0, and it's 2 flat line segments.
if n=4, the angle is 2/Pi, going from (0,0) to (Pi/2,1) (to (Pi,0) etc)
Jon and Mary Miller
Why isn't this for n=2? Does the snake go /\ for n=2, or does it have
to wait for n=4 and go _/\_ ?
I'll wait for the answer for this one before I go any further.
Jon Miller
Craig
n = 1, 2, 4 are trivial (and follow immediately from symmetry).
n = 3. 0, x, 2pi-x, 2pi
sin(0) = 0
sin(2pi) = 0
sin(2pi-x) = -sin(x)
[sin(x) - sin(0)]^2 + [x - 0]^2 = [sin(x) - sin(2pi-x)]^2 + [x -
(2pi-x)]^2
sin(x)^2 + x^2 = [2 sin(x)]^2 + [2x - 2pi]^2
sin(x)^2 + x^2 = 4 sin(x)^2 + 4 [x - pi]^2
x^2 = 3 sin(x)^2 + 4 [x - pi]^2
x^2 = 3 sin(x)^2 + 4 [x^2 - 2 x pi + pi^2]
x^2 = 3 sin(x)^2 + 4 x^2 - 8 x pi + 4 pi^2
0 = 3 sin(x)^2 + 3 x^2 - 8 x pi + 4 pi^2
There is no exact solution for this (with normal functions), but the
approximate solution is 2.2454338641036545240. The other point is
then 4.0377514430759319530.
The approach is straightforward. The first and last are obvious. The
second half are 2pi minus the first half. This gives you floor(n/2 -
1) variables in that many equations.
Kevin Hamer
on 0 to 2*Pi its more of a ^v than a ^.
Kevin Hamer
news:15612c7d.0307...@posting.google.com...
I know how to use Pythag to solve any specific case, by setting lengths
equal. However, it isn't what I am looking for/was trying to find: I want,
in terms of n, a formula that will work for any n, not a table of values for
each n. Or something close to a general formula. Even if it only works for
some infinite set or something... whatever.
Proginoskes
> Kevin Hamer wrote:
> >I want to fit the snake on [0,2*Pi] to y=sin(x). The snake has n segments.
> >if the first 'joint' of the snake is at (0,0), and the last one is at
> >(0,2*Pi), what is the angle between the X-axis and the first segment of the
> >snake based upon n if all the snake segments are the same length?
> >
> >Example:
> >If n=1, the angle is 0, and it's 1 flat line segment.
> >If n=2, the angle is 0, and it's 2 flat line segments.
> >if n=4, the angle is 2/Pi, going from (0,0) to (Pi/2,1) (to (Pi,0) etc)
> >
> >
> Why isn't this for n=2? Does the snake go /\ for n=2, or does it have
> to wait for n=4 and go _/\_ ?
The graph of the sine function, going from 0 to 2 Pi, looks (sort of) like:
_
/ \
\_/
Now, back to the original problem ...
I don't like the looks of it. (I'm typing in as I'm going.) If you
want the segments of the snake to all have the same length, you are looking
for numbers x(0), x(1), ..., x(n), where x0 = 0, x(n) = 2 Pi, and
sqrt((x(i)-x(i-1))^2 + (sin x(i) - sin x(i-1))^2)
is the same for all values of i (from 1 to n). Life gets easier because
all you have to do is make sure that the square of this distance:
D(i) = (x(i) - x(i-1))^2 + (sin x(i) - sin x(i-1))^2
is the same for all values of i. I have no idea how to go about solving
for the x's, unless you do the following (simulation):
(A1) Choose x(1). Set i = 1, calculate D = D(1) = x(i)^2 + sin^2 (x(i)).
(A2) Solve the equation D(i + 1) = D, numerically. Certainly you must have
x(i) < x(i + 1) <= x(i) + D, so you can do a "binary search" for the
(approximate) solution. (I'll provide details if asked for.)
(A3) Increase i by 1. If i < n, go back to step A2.
If x(n) > 2 Pi, you made x(1) too big. Make it smaller. If x(n) < 2 Pi,
choose another value of x(1) which is bigger. Repeat until | x(n) - 2 Pi |
is as small as you want (like 10^(-8)).
You can also decide your guess for x(1) using a binary search; clearly,
0 < x(1) < 2 Pi.
Okay, here's the algorithm for a binary search. Suppose you have a continuous
function f(x) on [a,b] (which is 1-1 on that interval), and you want to
approximate the unique number t so that f(t) is approximately y, which is
between f(c) and f(d). The binary search algorithm would be:
(B1) Let c = a, b = d.
(B2) If | f(c) - f(d) | is small enough for you (such as 10^(-8)),
let t = c, and exit the algorithm.
(B3) Otherwise let e = (c + d)/2. If f(e) = y, let t = e, and exit the
algorithm.
(B4) If f(c) < f(d), then let your new value of c be e if f(e) > y, and
let your new value of d be e if f(e) < y. (This is if f(x) is
increasing.)
(B4') If f(c) > f(d), then let your new value of c be e if f(e) < y, and
let your new value of d be e if f(e) > y. (This is if f(x) is
decreasing.)
(B5) Go to step (B2).
Hopefully this will be enough to get you started.
-- Christopher Heckman
P.S. If you want the lengths of the _arc_ between x(i) and x(i+1) to be
the same for all i, the process is actually easier, provided you can
integrate sqrt(1 + cos^2 t):
Suppose F(t) is an antiderivative, and not too messy to manipulate.
First find L = F(2 Pi) - F(0); this is the total length of the arc. Let
x(0) = 0, and do the following for i = 1, 2, ..., n:
Solve F(x) - F(x(i-1)) = L/n; then let x(i) = x.
Macavity
wrote:
Let L(n) be the length of the segment.
For finding L, you have the equations
L = [x_(i+1) - x_i]^2 + [sin(x_(i+1))- sin(x_i)]^2
for i = 1 to n, with
x_0 = 0 and x_n = 2 Pi
This is n equations with n unknowns, and hopefully has a solution.
Then, the angle you seek is the solution of
Angle = atan(sin(x)/x) where
x^2 + sin(x)^2 = L
Not that any of this is easy to solve in general.
Proginoskes
> [...]
> Angle = atan(sin(x)/x) where
> x^2 + sin(x)^2 = L
Actually, once you have x(0), x(1), ..., x(n), you can calculate the
slopes of segment i by
m(i) = (sin x(i) - sin x(i-1)) / (x (i) - x(i-1))
and the angle between the i-th and (i+1)-th segments is
atan(m(i+1)) - atan(m(i)).
-- Christopher Heckman
Macavity
wrote:
You are right.
But of course, for a chap who chews the first set of equations for
breakfast, my last one must be a breeze... ;)
Craig
What about an algorithm capable of (Efficiently) calculating these
values to arbitrary precision for arbitrary n?
Proginoskes
> [...]
> But of course, for a chap who chews the first set of equations for
> breakfast, my last one must be a breeze... ;)
Yes. I originally forgot the last part, too (with the angles). 8-)
-- Christopher Heckman