0

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.

6
  • 3
    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 '15 at 16:16
  • 1
    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. – Robert Onslow May 1 '15 at 18:39
  • 2
  • 1
  • 1
    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 :-) – Jay Elston May 23 '15 at 16:45
2

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.

1

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.
4
  • 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 – Robert Onslow May 1 '15 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 – Veldaeven May 3 '15 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? – Robert Onslow May 10 '15 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. – Veldaeven May 11 '15 at 13:42
0

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

This stackoverflow post details approaches to the problem.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.