Dividing a curve into chords of equal length

I've been researching into this for quite a while, but I seem to be getting only answers involving some programming language of which I do not have any background knowledge. Let me explain the problem:

I think "equal length subdivision" of the image should be a straightforward visualization of the problem. I have a curve (a parametric Bezier curve, to be more specific) that I want to divide such that any two consecutive points of division have equal Euclidean distances between each other. The first and the last chords have to be on the beginning and the end of the curve respectively, and all points of division should be on the curve.

Ideally I would like to have a mathematical solution (i.e. no programming) in which I can specify the number of chords to obtain the resulting division points. I am perfectly fine with calculus and ready to learn more if needed.

Thanks.

[1]: https://i.stack.imgur.com/6RkAp.jpg

Solution 1:

If you have some curve $c:[0,1]\to\Bbb R^n$ you will have to reparametrize it to arc length. Assuming your curve is parametrized by arc length, it holds that the length of the curve between $c(a)$ and $c(b)$ is simply $b-a$.

For such a curve, you desired partition into $n$ arcs is simply cutting the curve at the points $c(L\cdot i/n)$ for $i=0,...,n$ and $L$ the length of $c$.

Some details:

The arc length of a curve $c$ between $a,b\in\Bbb R$ is

$$L_c(a,b)=\int_a^b\sqrt{1+\|c'(t)\|^2} \;\mathrm{d}t.$$

Reparametrizing your curve via $\hat c(t)=c(\varphi(t))$ for some $\varphi:[0,L]\to[0,1]$ with $L=L_c(0,1)$ is called parametrization by arc length if $L_{\hat c}(a,b)=b-a$. Now the parametrization of the curve perfectly mirrors its length. This gives you perfect control on how long your arcs will be.

How to find such a reparametrization? You will have to compute

$$\Phi(t)=L_c(0,t)$$

explicitely. Invert it to $\varphi=\Phi^{-1}$ and apply to build $\hat c=c\circ \varphi$.

Solution 2:

Assuming you really want equal chord lengths rather than arc lengths, the expression will be recursive.

Assume the curve equation to be represented by $B(t)$.

From the current point, localted by the parameter value $t_k(s)$, let us find the first point which is at distance $s$, if it exists.

$$t_{k+1}(s):=\min\{t:t>t_n:d(B(t_k(s)),B(t))=s\}.$$

The recurrence is initiated with

$$t_0(s)=t_a$$

and this defines $t_n(s)$, an increasing function.

Now if you want exactly $n$ chords, you must ensure

$$t_n(s^*)=t_b$$ and solve this equation for $s^*$.

Needless to say, in most cases there will be no tractable closed-form for the $t_k(s^*)$ you are dreaming of.

Update:

When there are several solutions to the "$s$-distance" equation, choosing the first $t$ may lead to deadlocks.

Solution 3:

I do not know whether this is a solution for you, but I can now prove the existence of such an equichordal partition for any (continuous) curve $c:[0,1]\to\Bbb R^m$ into $n\in \Bbb N$ segments.

First, let's fix some definitions:

Definition. Let $c:[a,b]\to\Bbb R^m$ be a curve and $n\in\Bbb N$. An equichordal partition of $c$ into $n$ segments is a sequence $t_0,...,t_n\in[a,b]$ with $t_0\leq \cdots\leq t_n$ and

$$t_0=a,\quad t_n=b,\quad \|c(t_i)-c(t_{i-1})\|=\Delta,\quad\text{for all $i=1,...,n$}$$

and some some chord length $\Delta\geq 0$.

Now we can formulate what we want to show. Actually, we have to prove a stronger statement for the sake of the inductive proof. The proof will not be able to directly construct this partition. Instead it start with partitioning just some part of the curve. Subsequently we are going to move the division points in a continuously fashion, so that the partition will finally cover the whole curve. The hard part is to ensure that the curve stay equichordal during the whole process.

Theorem. For any curve $c:[0,1]\to\Bbb R^m$ and any $n\in \Bbb N$, there are continuous functions $t_i(\tau),i=0,...,n$ for $\tau\in[0,1]$ with

• $t_n(0)=0$ and $t_n(1)=1$,
• the $t_i(\tau)$ are an equichordal partition of the curve $c$ on $[0,t_n(\tau)]$ into $n$ segments.

Read it carefully. It states that we not only have an equichordal partition, but a continuum of such partitions. For $\tau=0$ all partition points sit in $c(0)$. This is a trivial partition of the empty curve with chord length $\Delta(0) =0$. For $\tau = 1$ we have a partition of the whole curve. All other values of $\tau$ blend between these two states $-$ and thats important $-$ in a continuous fashion.

Proven this, your desired partition is given by the values $t_i(1)$.

Proof.

We will prove this using induction over $n$. This is actually a quite natural idea. We take some $n$-segment partition and add a single segment to build an $(n+1)$-partition. We just have to ensure that the new segment has the same length $\Delta$ as the rest. Also, this makes clear why we have to consider partitions of subcurves. To have place to add another segment, the current partition must not cover the whole curve.

The induction base $n=1$ is quite trivial, just choose

$$t_0(\tau)=0,\quad t_1(\tau)=\tau.$$

This is just a single line segment connecting $c(0)$ and $c(\tau)$. The rest of the proof will deal with the induction step $n\to n+1$.

We want to build a new $(n+1)$-partition from our already existing $n$-partition $t_i(\tau),i=0,...,n$ that also continuously blends from a division of the empty curve to a division of the whole curve $c$. Let's parametrize this continuous blend by $\hat\tau$ to avoid confusion with the already existing parametrization of the $t_i(\tau)$. For the moment fix $\hat\tau$. Now, we can describe any possible partition-candidate by only two numbers: $x$ and $\tau$.

• $x$ is the new division point added to the end of the old $n$-partition.
• $\tau$ describes which $n$-partition $t_i(\tau)$ to choose for the rest.

Of course, most of these candidates are useless. For example we must ensure that $x\geq t_n(\tau)$ so that $x$ is indeed the last point. Further, the distance from $c(x)$ to $c(t_n(\tau))$ (= the length of the new segment) must equal the common chord length $\Delta(\tau)$ of the rest to ensure equichordality. And this is the easy part. Finally we must ensure that $x$ and $\tau$ are choosen continuously w.r.t. the new parameter $\hat\tau$. We will see how to deal with all of this simultaneously.

What we should see from this thought process is, that the search space for the new partition is 2-dimensional. Any cadidate is represented uniquely by a pair $(x,\tau)$. Let's define the cadidate-space

$$D:=\{(x,\tau)\in[0,1]^2\mid t_n(\tau)<x<1\}.$$

We see that the condition that $x$ is the last division point is already incorporated. $D$ might look like the gray colored area in the picture below.

$\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad\quad$

Now define the following function on $D$ to have a measure for how equichordal a candidate is:

$$f(x,\tau):=\Delta(\tau) - \|c(x)-c(t_n(\tau))\|.$$

This function compares the length of the new segment to $\Delta(\tau)$. If it is zero, i.e. $f(x,\tau)=0$, then we indeed found an equichordal $(n+1)$-partition. So we are interested in the zeros of $f$. But not only this. Because we need to have a continuum of partitions parametrized by $\hat\tau$, we should actually look for a whole path of zeros inside $D$ that hopefully extends from $(0,0)$ (a partition of the empty curve) to $(1,\tau)$ (a partition of the whole curve), see the dashed black line in the image. So the last thing to do is to show that there is such a path $p:[0,1]\to D$ that is completely locate inside the zeros of $f$ and satisfies

$$ p(0)=(0,0),\quad p(1)=(1,\tau),\quad\text{for some $\tau\in[0,1]$}.$$

And here comes the big trick that will show the existence. Imagine yourself sitting on the left edge of $D$ and try to walk to the curvy edge of $D$, but without passing through a zero of $f$. First, note that

• on the left edge all pairs have $\tau=0$, hence describe partitions of the empty curve. Therefore $\Delta(0)=0$ and hence $f(x,0)\leq 0$.
• on the curvy edge all pairs describe the case $x=t_n(\tau)$. This means the last segment has zero length, hence $f(x,\tau)\geq 0$.

So during your journey from the left edge to the curvy one, you have to go from negative values of $f$ to positive values of $f$, and because $f$ is continuous (can be seen easily), the intermediate value theorem say that we have to pass $f=0$ at some point. Imagine the zeros as walls. Then what does it mean that we cannot reach from the one edge to the other. Probably that there is a wall (made from zeros) extending without gaps from the lowest point of $D$ to some highest point of $D$. This "wall" is our path $p$.

That this path actually exists and is continuous is not obvious. Proving this would probably need another such post. So check out the following links:

• "Intermediate Value Theorem" for curves
• Is this two-dimensional version of the Intermediate Value Theorem correct?
• Generalization of "easy" 1-D proof of Brouwer fixed point theorem

To be precise, this theorem holds probably only for sufficiently nice $f$. But At this point I must trust in the fact that, e.g. assuming $c$ has finite length will do the trick.

This finishes this proof by induction. $\square$

So, now what to take away from this? As there is no way to explicitely write down the division points you might be looking for, this proof sheds some light on how one can gradually approach a equichordal partition.

The result is comparable to Yves' answer. You start with a partition of a very small initial part of the curve (some tiny $\tau$). It might be easy to ensure equichordality here. You then gradually move the last division point further along the curve, bit by bit. After each move you recover equicordality by slightly shifting the other points. That this not need heavy (and unpredictable) adjustments of these other points is ensured by the continuity of the resulting partition blend.

It might happen that you cannot move $t_n$ further along the curve by still keeping the partition equichordal. This was the initial problem in Yves' approach. However, the proof shows that you can still make progress by instead moving $t_n$ backwards. You just have to make sure that you will not reverse the movement of all the other points.