# Spiral path generation to cover a 2D area

In my project, a robotic arm with an end effector of radius R needs to cover a 2D area in an optimal route (least time, smooth path). I am trying to achieve that by generating spiral covering routes.

I am currently a bit lost. I have a 2D area shaped arbitrarily. How can I implement the route generation algorithm to traverse it spirally (see photo)? I am kinda starting this project and I need a robotic arm to traverse this area spirally. Any suggestions would be helpful.

The spacing of the spiral turns has to be uniform and adjustable.

The generated path would be similar to that generated in CNC routing software. (Figure 2)

I tried implementing a very basic Matlab implementation but the result is coarse (See Figure 3).

• Welcome to Robotics, karl online. It's not clear what you're trying right now to generate the spiral path, but the (I'm assuming) Matlab image looks generally correct. Could you please edit your question to explain more about how you generated the image and what you think is wrong about the result you saw? Dec 6, 2021 at 13:37
• You will need to specify more about "uniform spacing," "shaped arbitrarily," and, perhaps, "traverse." The obvious interpretation -- little if any variation in spacing, no crossing, no pen-up -- has no solution for, say, an hourglass, where there is a pinched waist between larger regions. Dec 6, 2021 at 16:47
• @Chuck Hello. Thank you for your comment. The Matlab figure is generated by starting at the area's edge and traversing it all, then entering the next layer (second perimeter), and so on. The problem is: If the spacing of the nodes ($\Delta X$) is large, the path generated is coarse and with lots of right angles (which is not very optimal in my case because this path is to be drawn by a robotic arm). The main idea is: I wanna cover the 2D area spirally from outside to inside using a robotic arm with an end effector of radius R, in an optimal way. Kinda like CNC route generation for cavities. Dec 6, 2021 at 22:43
• @r-bryan Yeah you are absolutely right. I added a figure to the question to clarify it better. Thank you for your input. Dec 6, 2021 at 22:45
• But the shape you're trying to spiral into is coarse with lots of right angles. The spiral is keeping perfect margins. Also your comparison with the CNC end mill is all right angles. Dec 7, 2021 at 0:42

Here's the approach I would take. Let's start with the skeleton, then add the meat and the hair.

Suppose the outer contour has an identifiable tangent everywhere. Suppose the robot arm will travel generally clockwise, as in your sketch with the red path. It will keep its "left hand" on the border. That means that the circle center always lies on a normal to the tangent, R away from the intersection of the tangent and the normal (i.e., from the border).

The arm (that is, the center of the end effector) will travel in a path approximately parallel to the tangent, incrementally adjusting its course left or right according to how the tangent changes direction. As the center traces out its path, the "right hand" traces out a path, too. The "right hand" is diametrically opposite to the "left hand", 2R from the border. Everything between the "left hand" and the "right hand" will have been covered, or milled, or routed, or whatever.

When the arm gets back to where it started, that's one circuit, or layer. The path traversed by the "right hand" becomes the new border, and the whole thing iterates once more. It terminates when the circle is trapped, such that it would intersect the border no matter what direction it moves.

What about corners, where the tangent is undefined? I hope the border is at least piecewise continuous. If the corner is not pathological, the arm's path for one piece will intersect with the path for the next piece, so the arm just starts following the second path where the paths intersect. If it's too pathological for that work, I'll wave my hands about differential geometry or Lebesgue measure or something, and send you off to math.stackexchange.com :-)

How does it represent the "right hand" path during traversal? If you have some analytic representation for the border, like Bezier splines or something, there might be an analytic transformation or something. It would be simpler and more general, though, (but probably use more memory) to "draw" into a big bitmap, the way a paint program's brush would. I hope someone has found a better way.

How does it identify a tangent in a bitmap? It will sample a neighborhood of pixels, and locally fit a line or some other, more general curve. Even the best fit will only be an approximation, but then the bitmap itself is an approximation. The size of the neighborhood and the acceptable degree of approximation will serve to smooth the computed motion. Those smoothing parameters also give the flexibility to fix the coarse zig-zaggy right-angle "problem".

How does it get from one layer to the next? Probably the same way it got to the starting point, whatever that was.

One loop inside another is not a continuous spiral path. That's true. In fact, forbidding overlap, it probably won't even be able to finish the center. The problem statement has to relax one or more of the constraints of

• uniform path spacing,

• cover everything, exactly once,

• don't go outside the border,

• one continuous spiral.

To make a single spiral path, we could do a gradual linear interpolation from one path to the next, with pathlength/circumference or something as the parameter—like the "grooves" on a phonograph record. There are details for how to get it started and ended, but then record players actually work.