There is a vector polygon in the program (in the form of drawing commands).

The task is to expand this polygon in all directions by a specified distance. That is, to get its contour or frame, taking into account possible internal collisions. Interested, in fact, the algorithm of this action. It is desirable, not particularly resource-intensive. Or just a literature where you can read about it.

The most interesting thing is:

  • processing of self-intersections in closed areas (like an internal hole in the letter "I" - filled completely).
  • rounding in the corners. How to do without rounding is more or less clear (draw parallel lines at a given distance). Or do you connect the ends of the segments with the help of a bezier? ..

alt text

Black is the source area, and blue is the final (for different contour thickness). In extreme cases, you can build on the finished raster of the original polygon.

  • and why it is impossible to convert it into an image, after which any algorithm to scale the image and convert it back? - Andrio Skur

1 answer 1

Vector case

alt text

If we assume that you have already switched to the vector format, then:

  1. consistently examine the edges of the polygon in one direction (for example, counterclockwise). This is important because will affect the orientation of polygon edge vector guides.
  2. For each edge, calculate the normal (this is a normalized vector perpendicular to the edge vector of the edge). In your case, you should also make sure that the normal is directed "from" the polygon, and not "inside" it.
  3. multiply each normal by the "expansion" coefficient k.
  4. add the normal to the initial (u) and to the final (v) edge vertices (consider the vertices as vectors originating from the origin). We get the "extended" vertices u 'and v'. These vertices define the beginning and end of the "extended" edge.
  5. In addition, as a result, two (in the general case non-collinear) "extended" vertices u 'and u "' will be received for each vertex of the polygon (they will be calculated for adjacent edges with a common vertex u). They can be used to make a "rounding" (the most obvious way: to build intermediate vertices by turning u 'to u' 'in small angular steps).
  6. It is also necessary to identify situations of self-intersection and process them. I'm afraid to lie, but in my opinion, here we must look at the signs of mixed products of normal edges and vector (0,0,1). When the direction of polygon traversal is chosen, the sign of this work should change only for "concave" pairs of edges (forming the "non-convexity" of the polygon). It seems so..

You can read something on analytical geometry and vector arithmetic.

UPD: As an option, you can still look at this book: Steven M. LaValle. Planning Algorithms . It covers a wide range of issues, including and work with polygons.

Raster case

I think in almost any case it makes sense to do the conversion to a vector representation. To determine the boundaries, you can try to use the polygon intersection algorithm with a line parallel to any coordinate axis + read the color of pixels. Another option is to somehow try modifying the polygon fill algorithm. It's less obvious here, you have to think or look for a ready vectorizer :)

  • Thank you, I thought about that, but you wrote it all quite specifically =) I will try. There will be clarifications - I will note later. - Alexey Sonkin