Скачать: CL | DM;

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

← →
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)
Это что ж, эквидистанту к многоугольнику надо построить?
Или простое масштабирование?
Что называется "расстоянием меджу многоугольниками"?

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

---

← →
Думкин ©   (2003-09-15 14:52) [5]

http://algolist.manual.ru

---

Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.46 MB
Время: 0.014 c