# Algorithm for sweeping a 2d shape along a curve?

I am trying to create a graphics application where the user can use an arbitrary shape as a "brush", which will be swept along the drawing path. The shape may be transformed along the path (rotated, resized, etc).

I read this paper, and it seemed promising: Approximate General Sweep Boundary of a 2D Curved Object

My understanding of the method is this:

1. Simplify the shape to a polygon
2. Sample the shape at various times t along the curve
3. For each t, connect each point of the polygon at t the corresponding point of the polygon at t-1
4. Calculate the convex hull of the joined shapes
5. Move to t+1

Do I have it right? Is this the best way to approach this problem?

To clarify what I mean by a "Sweep Boundary": Examples would include a pen writing a line, Zorro marking the wall with his sword, a magic marker on a mirror. In each of these cases, there is a path that defines the movement (the "Heartline") and a shape that defines the width and angle of the writing instrument (the "Counterpoint"). The counterpoint is independent of the heartline and can change at any point t along the path.

The path would be "convex" only in the sense that an envelope is formed by the counterpoint as it "travels" along the heartline.

• Well, I am not 100% sure if I have the same thing in mind as you with the "sweep boundary", so you might define this first. And over which shapes do you calculate the convex hull, over the shapes t-1 and t, or 0,...,t ? The latter will not make much sense, I see no reason why a sweep boundary should be convex. – Doc Brown Dec 21 '14 at 20:29
• @DocBrown - Updated to include some more details. – Neil Mussett Dec 23 '14 at 14:02
• Are you creating a raster graphics application, or a vector graphics application? The first case should be much easier to be solved. For a vector gfx application, I think you have to make your way through the 45 pages of the paper you linked to. And though I did not read that paper, I am pretty sure you are not on the right track with step 4, the "outer hull" of the shape in stake has nothing in common with "the convex hull". – Doc Brown Dec 26 '14 at 8:55
• I am creating a vector graphics application (fonts). I guess I am back where I started. – Neil Mussett Dec 28 '14 at 3:29
• If you truly can sample at some number of n points and have it be "close enough", I think your general process is not that far off, but agree with @DocBrown about the convex hull. If your library for dealing with polygons allows you to "union" them, I think that would be what you want. (e.g. msdn.microsoft.com/en-us/library/ms607450%28v=vs.110%29.aspx) You will also definitely want to consider your delta-t value carefully or you may need to do more tricks if it is too big. – J Trana Dec 29 '14 at 6:53