I have some polyline in the plane, it is necessary to construct two polygons on the left and right of it at given distances.

For example:

Suppose the polyline is set in red, it is necessary to rebuild the left and right polygons A and B relative to it. Thus, polygons A and B are joined in a given polyline. To construct polygons, with preservation of the curvature of the polyline, two distances are specified, for the left and right sides.

polygons on the left and right relative to the polyline

The difficulty lies in the fact that I need to know the direction of the polyline in order to move along this direction, at specified distances from it, to obtain the necessary points of the final polygons.

The limitations of the original data: 1) A polyline without self-intersections 2) A polyline cannot be bent, i.e. for example, one point of the X or Y axis is strictly

I am writing in c ++

Throw an idea)

  • one
    And how is your broken line? - Vladimir Martyanov
  • 2
    The simplest option: take a segment from the beginning to the end of the polyline and build a perpendicular to it - this will be the direction vector of the shift. Then each point of the polyline can be shifted to this vector * distance and connect the ends. - Lyth
  • one
    What do you plan to do with the self-intersecting result? - Igor
  • one
    @Naf The letter "P" also has no self-intersections. I'm not talking about the original broken line, but about the resulting after the indent. - Igor
  • one
    @Naf You need to decide: You need a parallel transfer of the entire broken line (a dangerous thing - there can be intersections with the original line, uneven indents from the original one, and where should you actually transfer?), Or a uniform indent is no less difficult task, because the indent line is not congruent to the original. - Igor

1 answer 1

Suppose there are points C = [(x1, y1), (x2, y2), ..., (xn, yn)] - this is a polyline.

The segment (x1, y1) - (xn, yn) connects the first and last points. We make from it the direction vector of the broken line v:

(vx, vy) = (xn - x1, yn - y1)

And turn 90 degrees:

| 0 -1 | d = (vx, vy) * | | = (-vy, vx) | 1 0 |

This is a vector with any length which is perpendicular to the "direction" of the polyline. There will be a lot of nuances, but about them later. While we are normalizing (we will result in length 1):

 vL = sqrt(vx*vx + vy*vy) dN = d / vL = (-vy / vL, vx / vL)

Actually, now, having distances for which it is necessary to retreat "on the left" and "on the right" (p, q), we mix each point and get new broken lines:

  L= C + dN * p = [(x1 + dN.x * p, y1 + dN.y * p), ...] R= C - dN * q = [(x1 - dN.x * q, y1 - dN.y * q), ...]

To close them to the original polyline, add the original points in an inverted order, otherwise there will be strange diagonals when drawing:

  M1 = [L1, L2, ..., Ln, Cn, Cn-1, ... C1] M2 = [R1, R2, ..., Rn, Cn, Cn-1, ... C1]

Now the nuances.

  1. "Left" and "right" are very relative concepts, depending on the order of points in the original broken line. If they are given by projection on a plane, they may have to be turned over.

  2. There may be situations when the displaced polyline intersects with the original one, or it will be impossible to connect straight lines starting and ending points with the original polyline to get a non-intersecting polygon.

Example of the second situation: Polyline shift

Red when moving nalezla on the original; with green it is not possible to make a polygon without intersections.

  • I supplemented the question with restrictions on the source data. - Naf
  • @Naf "A polyline cannot be bent, that is, for example, on one value of the X or Y axis there is strictly one point" - this is the best that could be expected, then there will be no problems with polygons. - Lyth