Равноудалённые точки от произвольного многоугольника

Ув. программисты посоветуйте алгоритм или хоть где можно почитать про это.
Мне нужно разместить энное кол-во точек вокруг многоугольника как это сделать? зная только координаты вершин многоугольника ? И обязательно ли могоугольник должен быть выпуклым?

0

Сообщение от snake32 Зная в каком порядке перечислены вершины полигона

Но это же чит...

0

Женя, если б я знал как можно сделать по другому, не прибегая к 3D, то так бы и сделал. Но пока даже выбирать нечего.... а ведь время то идёт.... а потом - лучше хоть какой-нибудь результат, чем вообще никакого, тем более что в тз вообще ничего не указано(точнее его вобоще нет). Я думаю, алгоритм можно назвать рабочим для большинства полигонов.
С удовольствием посмотрю на другие алгоритмы.

А что ты подразумеваешь под словом ЧИТ? Я что то ипользую незаконное?

0

Ну, мягко говоря, откуда тебе знать, там по часовой стрелке или против часовой. Хотя если это заказная работа - то по большому счёту пофиг. Но если для себя - то для порядку надо бы разобраться, как это делать "по-человечески", т.е. имея лишь набор точек и не обладая какими-либо априорными знаниями о том, в каком порядке они записаны. Я не знаю, как это делать, ибо с математикой туго, но могу поспрашивать

Добавлено через 11 минут
Математики рассказали, как определить, находится некая точка X снаружи многоугольника, или внутри. Допустим, многоугольник задаётся точками M1, M2, ... MN

Берём от точки X рисуем два вектора X-M1 и X-M2. Вычилсяем веторное произведение (ону будет либо положительным, либо отрицательным в зависимости от взаимного расположения веторов). Дальше берём пару векторов X-M2, X-M3 и т.д. до X-MN, X-M1. Все эти векторные произведения складываем. Если точка находится за пределами многоугольника, то сумма полуится равна нулю. Если внутри многоугольника, то сумма окажется равной площади многоугольника (как сумма площадей соотвествующих треугольников).

Исходя из этого можно определить, с какой стороны рисовать каёмку

Добавлено через 23 минуты
Правда такой метод годится только в случае, когда нет пересечений. Ещё возникает вопрос, как выбрать точку (критично для последней картинки из 20-го поста)

1

Сообщение от snake32 Зная в каком порядке перечислены вершины полигона(по часовой или против)

Кстати, а если попарно векторно перемножить все стороны (1-ю на 2-ю, 2-ю на 3-ю, ... N-ю на 1-ю) то не полуится ли, что знак результата зависит от направления обхода?

1

Сообщение от Evg Вычилсяем веторное произведение (ону будет либо положительным, либо отрицательным в зависимости от взаимного расположения веторов)

Опять же это в пространстве, тк векторное произведение определено только для 3D-векторов.

Сообщение от Evg о сумма окажется равной площади многоугольника (как сумма площадей соотвествующих треугольников).

Если быть точнее, то полу-сумма = площади многоугольника, тк модуль длины векторного произведения определяет площадь параллелограмма, образованного векторами.

Сообщение от Evg Кстати, а если попарно векторно перемножить все стороны (1-ю на 2-ю, 2-ю на 3-ю, ... N-ю на 1-ю) то не полуится ли, что знак результата зависит от направления обхода?

Скорее всего должен получится нуль-вектор, но я не проверял.

Сообщение от Evg Берём от точки X рисуем два вектора X-M1 и X-M2. Вычилсяем веторное произведение (ону будет либо положительным, либо отрицательным в зависимости от взаимного расположения веторов). Дальше берём пару векторов X-M2, X-M3 и т.д. до X-MN, X-M1.

Сделал немного по-другому: за точку М взял первую вершину и попарно выполнил векторое произведение с остальными вершинами.... и о чудо! Действительно, знак z координаты суммы произведений показывает направление обхода!!!
СПАСИБО Евгений тебе и твоим математикам!

PS: После небольшого редактирования программе уже наплевать на обход. Жаль что я ещё вчера отправил мою прогу. Работадатель так и не увидит её.

Добавлено через 8 минут

0

А что будет, если натравить на 3-ю картинку из 20-го поста (самопересекающуюся часть удалить). В том плане, что если на многоулоьнике растояние между зубцами меньше, чем расстояние, на котором должна быть нарисована рамка

Насколько я понимаю, с пересечениями ты не сделал? Потому как математики сказали, что это вообще отдельная геморройная задача, дальше у меня просто уши отсохли. Единственное, что я понял - если взять 5-конечную звезду (нарисованную как в детстве, пятью пересекающимися линиями), то с аналитической (математической) точки зрения центральный 5-угольник является внешней стороной, а 5 треугольников - внутренние. И, насколько я понял, если в векторных графических редакторах по типу corel draw выбрать прорисовку закрашенного многоугольника по точкам, то если нарисовать 5-угольник в виде звезды, внутренность и вправду окажется незакрашенной.

0

Сообщение от Evg растояние между зубцами меньше, чем расстояние, на котором должна быть нарисована рамка

Это и

Сообщение от Evg Насколько я понимаю, с пересечениями ты не сделал?

это не сделал.

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

0

https://www.cyberforum.ru/job/ тебе в помощь

1