Подскажите алгоритм расширения многоугольника, пожалуйста.

← →
Andrey007 (2003-09-15 13:32) [0]

Дано: список вершин многоугольника. Многоугольник может быть как выпуклым, так и невыпуклым.
Требуется: получить список вершин многольника, отстоящего от исходного на заданное расстояние. То есть, расстояние - это входной параметр этой процедуры.

Я делал так.
Первый шаг. Создаётся два списка точек - содержащие списки вершин многоугольников, у которых все стороны параллельны сторонам исходного - только у одного многоугольника все стороны оказываются внутри исходного, а у другого - вне.
Второй шаг. Из этих двух многоугольников выбирается тот, у которого больше высота - то есть, выбирается внешний. При этом получается так, что у невыпуклого исходного многоугольника внешний получается с персекающимися друг с другом сторонами.
Третий шаг. Поиск пересекающихся друг с другом сторон получившегося многоугольника и удаление пересечений.

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

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

← →
Думкин © (2003-09-15 13:46) [1]

Эта проблема около года назад обсуждалась на Алголисте. Одна из первых веток. Посмотри там - может найдешь еще.
Там обсуждалась и корректность данной задачи.

← →
Verg © (2003-09-15 13:47) [2]

Это что ж, эквидистанту к многоугольнику надо построить?
Или простое масштабирование?

Что называется "расстоянием меджу многоугольниками"?

← →
Думкин © (2003-09-15 13:59) [3]

> Andrey007 (15.09.03 13:32)
Я там и примерный алгоритм приводил.

← →
Andrey007 (2003-09-15 14:28) [4]

>Думкин ©
А алголист - это где? www.algolist.ru не существует

>Verg © (15.09.03 13:47)
Это что ж, эквидистанту к многоугольнику надо построить?
Или простое масштабирование?
Что называется "расстоянием меджу многоугольниками"?

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

http://algolist.manual.ru

Подскажите алгоритм расширения многоугольника, пожалуйста. Найти похожие ветки