Алгоритм для расширения/выкачивания (возмещение, буферизуя) полигоны

Вот альтернативное решение, посмотрите, понравится ли оно вам больше.

1. Проведите триангуляцию , это не должно быть медленным - подойдет любая триангуляция. .

2. Надуйте каждый треугольник - это должно быть тривиально. если вы сохраняете треугольник в порядке против часовой стрелки, просто переместите линии в правую сторону и сделайте пересечение.

3. Объедините их, используя модифицированный алгоритм отсечения Вейлера-Атертона

Sounds to me like what you want is:

• Starting at a vertex, face anti-clockwise along an adjacent edge.
• Replace the edge with a new, parallel edge placed at distance d to the "left" of the old one.
• Repeat for all edges.
• Find the intersections of the new edges to get the new vertices.
• Detect if you've become a crossed polygon and decide what to do about it. Probably add a new vertex at the crossing-point and get rid of some old ones. I'm not sure whether there's a better way to detect this than just to compare every pair of non-adjacent edges to see if their intersection lies between both pairs of vertices.

The resulting polygon lies at the required distance from the old polygon "far enough" from the vertices. Near a vertex, the set of points at distance d from the old polygon is, as you say, not a polygon, so the requirement as stated cannot be fulfilled.

I don't know if this algorithm has a name, example code on the web, or a fiendish optimisation, but I think it describes what you want.

Многоугольник, который вы ищете, в вычислительной геометрии называется многоугольником смещения вовнутрь / наружу и тесно связан с прямым каркасом .

Это несколько полигонов смещения для сложного многоугольника:

А это прямой скелет для другого многоугольника:

Как указано в других комментариях, в зависимости от того, насколько далеко вы планируете «раздувать / deflate »ваш многоугольник, вы можете получить различные возможности подключения для вывода.

С точки зрения вычислений: как только у вас есть прямой скелет, можно будет относительно легко построить смещенные многоугольники. Библиотека с открытым исходным кодом и (бесплатная для некоммерческих) CGAL имеет пакет, реализующий эти структуры. См. этот пример кода для вычисления полигонов смещения с использованием CGAL. ​​

Руководство по пакету должно дать вам хорошую отправную точку для создания этих структур, даже если вы не собираетесь использовать CGAL, и содержит ссылки на документы с математическими определениями и свойствами:

Руководство CGAL: 2D прямой каркас и смещение многоугольника

Each line should split the plane to "inside" and "outline"; you can find this out using the usual inner-product method.

Move all lines outward by some distance.

Consider all pair of neighbor lines (lines, not line segment), find the intersection. These are the new vertex.

Cleanup the new vertex by removing any intersecting parts. -- we have a few case here

(a) Case 1:

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

if you expend it by one, you got this:

0----a----3
|    |    |
|    |    |
|    b    |
|         |
|         |
1---------2

7 and 4 overlap.. if you see this, you remove this point and all points in between.

(b) case 2

 0--7  4--3
 |  |  |  |
 |  6--5  |
 |        |
 1--------2

if you expend it by two, you got this:

0----47----3
|    ||    |
|    ||    |
|    ||    |
|    56    |
|          |
|          |
|          |
1----------2

to resolve this, for each segment of line, you have to check if it overlap with latter segments.

(c) case 3

       4--3
 0--X9 |  |
 |  78 |  |
 |  6--5  |
 |        |
 1--------2

expend by 1. this is a more general case for case 1.

(d) case 4

same as case3, but expend by two.

Actually, if you can handle case 4. All other cases are just special case of it with some line or vertex overlapping.

To do case 4, you keep a stack of vertex.. you push when you find lines overlapping with latter line, pop it when you get the latter line. -- just like what you do in convex-hull.