8
$\begingroup$

In high-school I learned how to find the circles that connect points in 2D space forming a curve made out of tangent circles like this:

5 points connected with 4 tangent circles same curve showing the centers of each circle

(The green line shows the "initial direction" of the curve)

You could imagine trying to close the curve with one last circle. However, this doesn't always close the curve "nicely":

5 points connected badly

And sometimes it does:

5 points connected nicely

My question is what conditions must these points follow such that they can be connected with a "nice" curve?

What I have found messing around is that, for an odd number of points, it seems to be always possible to find an "initial direction" that closes the curve nicely. But for an even number of points, this is only possible for some set of points: Sets that do close nicely for one "initial direction", close nicely too for all "initial directions". For example, points that can be all put in one circumference always close nicely.

I think I have some intuition for what is going on but I can't find a nice mathematical answer. I also can't find anything like this on the internet, so I'm sorry if this isn't very rigorous. Is there an official name for this kind of curves? Where could I find more information and theory on this?

$\endgroup$
2
  • $\begingroup$ Though it doesn't directly answer the main question, someone shared a very interesting paper on the matter: PLANAR AND POLY-ARC LOMBARDI DRAWINGS by Duncan, Christian A. et al. $\endgroup$
    – dino
    Commented May 1, 2022 at 23:56
  • 1
    $\begingroup$ From the second picture it seems to me that the answer is in the base angles of the isosceles triangles given by each side and the corresponding circle center. If you take them as signed, each adjacent pair of them always add up to the given angle of the original polygon. For n points that gives you n equations in n unknowns, though the solution might not be unique, since everything is only defined up to multiples of $2\pi$. $\endgroup$
    – mlk
    Commented May 2, 2022 at 7:03

2 Answers 2

4
$\begingroup$

The comment by mlk is right on the mark. The idea of this solution is basically what he wrote, but there a lot of messy details coming from the question of which direction the arcs are curving. Let the points be $P_1$, $P_2$, ... $P_n$ in that order, and assume that the curve is a simple closed curve. Let $\alpha_i$ be the angle $\angle(P_{i-1} P_i P_{i+1})$, measured inside the simple closed polygon. I will show that:

  • For $n=2m$ even, the curve closes if and only if $\alpha_1+\alpha_3+\cdots+\alpha_{2m-1} = \alpha_2 + \alpha_4 + \cdots + \alpha_{2m}$. In this case, we can start at any angle. (Since the sum of the angles of a $2m$-gon is $(2m-2) \pi$, the common value of the sum of $(m-1) \pi$.)

  • If $n$ is odd, there is exactly one angle we should start at.

Let $O_i$ be the center of the arc from $P_i$ to $P_{i+1}$. I found the following sign convention useful: If $O_i$ is inside the curve, I set $\theta_i = \angle(O_i P_i P_{i+1}) = \angle(O_i P_{i+1} P_i)$; these angles are equal because they are the base angles of an isosceles triangle. If $O_i$ is outside the curve, I put $\theta_i = \pi-\angle(O_i P_i P_{i+1}) = \pi-\angle(O_i P_{i+1} P_i)$.

The condition that the arcs $P_{i-1} P_i$ and $P_i P_{i+1}$ are tangent says that $O_{i-1}$, $O_i$ and $P_i$ are collinear with $O_{i-1}$ and $O_i$ on the same (respectively opposite) side of $P_i$ if $O_i$ and $O_{i+1}$ are on the same (respectively opposite) side of the curve.

I claim that the following relation holds: $$\alpha_i = \theta_{i-1} + \theta_i. \qquad (\ast)$$ We need to check all four cases for whether $P_{i-1}$ and $P_i$ are inside or outside of the curve: For example, if both are inside, then this holds because $$\angle(P_{i-1} P_i P_{i+1}) = \angle(P_{i-1} O_{i-1} P_i)+ \angle(P_{i} O_{i} P_{i+1}) = \angle(P_{i-1} O_{i-1} P_i)+ \angle(P_{i} O_{i+1} P_{i+1}).$$ In the other cases, we need to similarly check that all the $\pi$'s and $-$'s work out.

We can use $(\ast)$ to compute all of the $\theta_i$ in terms of $\theta_1$: We have $\theta_2 = \alpha_2-\theta_1$, $\theta_3 = \alpha_3-\alpha_2+\theta_1$, etcetera.

If $n$ is even, we see that the curve closes if and only if $\alpha_1+\alpha_3+\cdots+\alpha_{2m-1} = \alpha_2 + \alpha_4 + \cdots + \alpha_{2m}$. If $n$ is odd, we see that the key equation is $\theta_1 = \alpha_1 - \alpha_2+\alpha_3-\alpha_4 +\cdots +\alpha_n - \theta_1$. This will hold exactly for one value of $\theta_1$ modulo $\pi$. $\square$

I tried to work out the case of a self intersecting curve, but it got too messy. There is a method called "directed angles" which often cleans up situations like this -- see Section 1.7 of Geometry Unbound -- but I didn't find it helpful.

$\endgroup$
1
  • $\begingroup$ This directed angle idea was what I meant with signed angles in the comment, so yeah, I believe this could save a bit on case distinction. On the other hand, I missed the possibility of an arc consisting of more than half of the circle. It's quite possible that this works out mathematically with angles larger than $\pi/2$, but it might need another case distinction. $\endgroup$
    – mlk
    Commented May 3, 2022 at 8:41
2
$\begingroup$

(1) This paper's algorithm doesn't close smoothly at the joints, but it may serve as a link into the circular-arc literature:

Duncan, Christian A., David Eppstein, Michael T. Goodrich, Stephen G. Kobourov, and Maarten Löffler. "Planar and poly-arc Lombardi drawings." In International Symposium on Graph Drawing, pp. 308-319. Springer, Berlin, Heidelberg, 2011.

In particular, you might search for Lombardi drawings: "drawings of graphs in the plane so that every edge is represented by a circular arc and every vertex has perfect angular resolution: the edges are equally spaced around each vertex."

DE_Fig2


(Later.) (2) This paper is more of a direct hit on the OP's question, and its Introduction cites more than a dozen related works.

Song, Xinghua, Martin Aigner, Falai Chen, and Bert Jüttler. "Circular spline fitting using an evolution process." Journal of Computational and Applied Mathematics 231, no. 1 (2009): 423-433. DOI.

"We propose a new method to approximate a given set of ordered data points by a spatial circular spline curve."

Biarcs

(Above) Joining two primary arcs (dashed) by one biarc (dotted).

ClosedSpline

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .