# Algorithm to generate parallel path inside polygon

A path is defined as a list of 2D points (x,y) (and may be open or closed).

Given a path p, what is an algorithm which generates a path p' which is "inside" p and at constant offset to p i.e. each line segment of p' is parallel to the corresponding line segment of p.

• Sharing your research helps everyone. Tell us what you've tried and why it didn’t meet your needs. This demonstrates that you’ve taken the time to try to help yourself, it saves us from reiterating obvious answers, and most of all it helps you get a more specific and relevant answer. Also see How to Ask
– gnat
May 1, 2015 at 16:16
• Wow! 2 downvotes. Intimidating forum. I'm really sorry. My crime was not to think hard enough before asking the question. I now understand that StackExchange is only to be used as a last resort. If possible, StackExchange expects people to solve their own problems and, where possible, not to ask questions at all. That makes a lot of sense. Got it. May 1, 2015 at 18:39
• meta.stackoverflow.com/a/261593/839601
– gnat
May 1, 2015 at 19:21
• May 2, 2015 at 6:21
• My guess on why you received downvotes has to do with the quality of the question. Perhaps if you had taken to find related work such as: seant23.files.wordpress.com/2010/11/anoffsetalgorithm.pdf (found searching on the term "parallel paths with offset algorithm") and told us why it didn't work for you, your question would have received upvotes instead. FWIW, I think this is a valid question for this site, so I didn't downvote, but I couldn't upvote this one either... I hope this doesn't discourage you from participating in stackexchange sites. Thick skins are an asset here :-) May 23, 2015 at 16:45

Well, this turns out to be non-trivial extension of Veldaeven's solution.

For each sequence of 3 points, calculate the 2 vectors between them, as suggested by Veldaeven.

Find the angle between the two vectors by adding the angles from the x axis - (nb do not use dot product which always returns an angle less than pi and hence is too symmetrical for our problem).

Halve this angle. This is the perpendicular bisector along which the resulting vector will lie.

Now to calculate which quadrant to draw the point in (the "which side" problem). Find the difference between the 2 vectors. If the gradient of this (i.e. the "double derivative") is positive then the path is going back on itself through a maximum: add pi/2. If the gradient is negative, the path is going through a minimum: subtract pi / 2

``````innerWallClockwise :: Float -> V2 Float -> [Point V2 Float] -> [V2 Float]

innerWallClockwise w acc (p : p' : p'' : ps) =

let v = p' .-. p
v' = p'' .-. p'
d2v = v' .-. v
phi = atan2 (v ^. _y) (v ^. _x)
rho = atan2 (v' ^. _y) (v' ^. _x)
theta = phi + rho
d2vtheta = atan2 (d2v ^. _y) (d2v ^. _x)

theta' = theta / 2 + if d2vtheta > 0 then pi / 2 else (-1) * pi / 2
v''' = w *^ angle theta'
v'''' = acc .+^ v'''
in
if ps == [] then [v''''] else v'''' : (innerWallClockwise w (acc .+^ v') (p' : p'' : (head ps) : (tail ps)))
``````

Let's give it a simple rectangular path

``````let path=[P (V2 0 0), P(V2 0 5), P(V2 5 5), P (V2 5 (-5)), P (V2 0 (-5))]
``````

Try out our function:

``````innerWallClockwise 1 (V2 0 5) path

=> [V2 0.70710677 4.2928934,V2 4.2928934 4.2928934,V2 4.2928934 (-4.2928934)]
``````

Yes, the points are all inside the input path at a distance of sqrt(2) from the vertex.

NB all methods using e.g. the cross product of the two vectors are too symmetrical.

Hopefully this will help someone in the future.

I don't know of a formal algorithm. I implemented this once long ago. The algorithm depends on not only the enumeration of line segments, but also on the "side" of the line segments that the parallel path is meant to follow. Assume you know the "side".

My set of line segments was (as you describe) a list of 2d points (x,y).

1. For each point `p`, I looked at the two vectors formed by using its previous and subsequent points in the enumeration.
2. I found the angle between these two vectors using a dot product
3. I split that angle in half, making a third vector that bisected the first two. (This is where knowing "what side of the path" comes in)
4. By setting the magnitude of this third vector to the "constant offset", you come up with a point `p'` on the "parallel path" that corresponds to point `p`
5. For the endpoints of a path that is not closed, I simply used the constant offset to set the magnitude of a vector perpendicular to the vector formed by the endpoint and its neighboring point.
• Thanks for this Veldaeven. I would vote it up but unfortunately my reputation is in tatters for having dared not to know the answer before I asked the question. So I'll do it here: +1 vote May 1, 2015 at 18:40
• Its OK Robert... I have learned that a thick skin helps. The article that "gnat" cites in the above comment is pretty legit- I can't fault any point of reason therein. Sometimes people (myself included) just don't have anyone to bounce ideas off of. I asked your question once also (heaven forbid- not on this forum!) and I also had nobody to answer it. I thought "programmers.se" was more open to such questions (StackOverflow is so NOT open to them!), but perhaps gnat has the right of it. If you find a forum where people who are otherwise alone in the world need someone to chat with, let me know May 3, 2015 at 1:02
• On the "what side of the path" issue, the angle produced by the dot product is always less than pi isn't it? So that the "third vector" bisector could end up either side of the path. Is there something better than the dot product, to handle this symmetry problem? May 10, 2015 at 11:16
• You are correct- its been a long time since I did that. I was wrong about the dot product. If you use ATAN2(V2-V1). The sign of ATAN2 determines the side. V2 is the vector from point P to the next point, V1 is the vector from P to the previous point. May 11, 2015 at 13:42

I believe you're looking for an offset-polygon.

This stackoverflow post details approaches to the problem.