Всем привет!! Задача такая: 



Есть какой то многоугольник с n-ым количеством вершин(на рисунке это четырехугольник и он красный) все координыты вершин известны. Многоугольник может быть любой формы.
Есть рамка для него(она зеленая) но её координаты не известны.
Нужно найти координаты вершин рамки.
Имено координаты!  Мне не нужно рисовать вокруг многоугольника рамку!


Нашел в инете что многокгольник можно промасштабировать путем умножения его координат на число... Но к сожалению такой мметод смещает многоугольник.
Тоесть выходи от что


Поскажите пожалуста каким образом можно многоуольник масштабировать не смещая его.

PS: Если есть у кого есть идеи как можно решить задачу без масштабирования готов внимательно выслушать  

Смести центр начала координат внутрь многоугольника (скажем, в его центр тяжести), смасштабируй (умножением координат на число) и верни начало координат обратно.

Я могу предложить такой алгоритм, но он подходит только для выпуклого многоугольника:

1. Находим центр многоугольника путем средне арифметического всех вершин (Center:TPoint).
2. Для каждой вершины (цикл)
 2.1. Находим вектор:  V.x := Center.x - P[i].x;
                                      V.y := Center.y - P[i].y;
 2.2. Далее вектор нужно нормализовать. V := Normal(V) // Ниже напишу как это сделать
 2.3. Координата вершины контура равна: Contur.P[i].x := P[i].x + V.x * k;
                                                                       Contur.P[i].y := P[i].y + V.y * k;    // Тут k это расстояние в пикселях, на котором нужно получить контур



А если Многоугольник невыпуклый, то могу предложить другой алгоритм, но он немного сложнее. Каждую вершину нужно умножать на матрицу

масштабирование - самый простой способ (с правильным выбором центра, естественно)
однако, он не даст рамку, которая находится на одинаковом расстоянии от многоугольника
например, если взять узкий длинный прямоугольник, возле длинных сторон рамка будет ближе к нему, чем возле коротких

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

чтобы сохранить одинаковость расстояния, соединять нужно дугами окружностей, чтобы сохранить "многоугольность", наверное, стоит просто продлевать их до пересечения (в случае невыпуклого многоугольника, возможно, придётся укорачивать...

Забыл уточнить многоугольник может быть невыпуклым 

Bitter, 

Я весь превратился в уши  
maxim1000, 

Эм.. а как их подвинуть?? Есть конечно предположение что это можно сделать с помощью перпендикулярного вектора, но на этом моя мысля заканчивается...   


На всякий случай дополню требования....



a b c d e -исходные
a1 b1 c1 d1 e1-искомые
Все отрезки aa1 bb1(на рисунке выделены зеленым) и тд должны быть одинаковой длины причем углы при них должны быть одинаковыми. Например у отрезка аа1 угол a1ab должен быть равен углу a1ac 
Рисунок делал в пэинте поэтому он не точен..

Это сообщение отредактировал(а) namervasek - 30.7.2009, 01:59

Блин, как правильно сказал maxim1000, умножение на матрицу не даст желаемого результата. Так как рамка не будет на одинаковом расстоянии. Но думаю что-то придумать можно. Только меня смутило вот что: 



Дело в том, что в случае невыпуклого многоугольника это невозможно. Вот смотри



Если соблюдать одинаковое расстояние от вершин, то рамка не будет повторять контур фигуры. А если повторять контур фигуры, то расстояние от вершин будет разным. Так что реши что нужно.

   че то я об этом не подумал....  
Нужно повторять контур фигуры  

А когда начинаются самопересечения для невыпуклого многоугольника, как например вот здесь:

что делать?

тогда начинаются проблемы 

и даже не только в самом алгоритме, но и в понимании, что именно должно получиться в результате
при "расширении" некоторых невыпуклых многоугольников могут получаться фигуры с дырками (пример - буква "С" с близкими концами)

тут всё зависит от того, для чего нужна рамка
в каких-то случаях можно просто забить на эти проблемы, и результат может оказаться приемлемым, в других случаях нужно будет найти внешнюю границу многоугольника
для этого можно избавиться от пересекающихся отрезков (просто разбить их на части в точках пересечения), а потом выкинуть те, которые невнешние

определение внешних отрезков иногда называют классификацией, например, можно пробовать определить положение точки, пуская луч и считая, сколько отрезков он пересечёт (при этом нужно также учитывать их направление)

вообще, по идее, на тему логических (булевских) операций должно быть немало документов а Интернете...

Да, для дуги тоже есть проблема:

Как можно искать внешнюю границу для такого случая?


На словах вроде понятно. А вот ссылки на конкретные алгоритмы были бы весьма полезны...

что-то не так много документации, как я ожидал...
можно попробовать поискать алгоритмы объединения/пересечения полигонов - там, по сути, тот же функционал используется, только разные отрезки остаются в результате...

Вот что у меня получилось: 


Тока код на делфи. Закоменчу и выложу. Надо еще добавить проверку на самопересечение

Вот исходники и exe

Тока проверку я не добавил, так как на работе времени мало

Присоединённый файл ( Кол-во скачиваний: 84 )
 Border.rar 172,16 Kb

Всем спс задачу решил