|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
Опции темы | Поиск в этой теме |
14.10.2015, 18:29 | #1 |
Регистрация: 18.03.2015
Сообщений: 5
|
Алгоритм для многоугольника
Столкнулся с проблемой при составлении алгоритма для рисования многоугольника по случайным точкам.
Пользователь задаёт N случайных точек struct TPoint { int x, y; };, по ним нужно составить многоугольник без самопересечений. Может кто-нибудь помочь с алгоритмом? Я попробовал отсортировать точки по возрастанию Х, но столкнулся с проблемой, как среди точек найти следующую с максимальным Y. Может, есть какой-нибудь ещё не сильно сложный алгоритм? Последний раз редактировалось dklinge; 14.10.2015 в 18:41. |
14.10.2015, 19:21 | #2 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
А вот графическое представление одного из алгоритмов построения
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
14.10.2015, 19:24 | #3 |
Регистрация: 18.03.2015
Сообщений: 5
|
Да, как должно выйти, я понимаю. Есть какой-нибудь алгоритм для этого или готовый код для сортировки точек / отрисовки линий?
По рисунку: точки сравниваются и берётся ближайшая по Х с наибольшим Y? |
14.10.2015, 19:29 | #4 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
А это и есть алгоритм. Сначала от левой крайней до правой крайней точки огибающую по низу ломанную строим. Потом соединяем отрезками точки слева направо отсортированные по возрастанию координаты по оси абсцисс
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
14.10.2015, 20:13 | #5 |
Регистрация: 18.03.2015
Сообщений: 5
|
Не выходит построить ломанную по нижним точкам.
Выходит так, что линия идёт просто по всем точкам. Вот код: Код:
Понял, в чём ошибка, но не могу понять, как выбирать для отрисовки линии конечными только точки снизу. Последний раз редактировалось Stilet; 16.10.2015 в 06:51. |
14.10.2015, 20:34 | #6 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Выбирай любой алгоритм построения выпуклой оболочки набора точек в
https://ru.wikipedia.org/wiki/%D0%A1...BC%D0%BE%D0%B2 там их куча
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
14.10.2015, 20:40 | #7 |
Регистрация: 18.03.2015
Сообщений: 5
|
Всё же написал программу, не могли бы Вы её проверить на правильность?
Сначала я сортирую все точки по возрастанию Х. Затем нахожу точку с максимальным Y, эта точка и будет первой, с которой начинается цикл. После этого я нахожу точку с максимальным Y, игнорируя первый элемент (for (int i = 1; i < N; i++)), эта точка будет последней. В итоге у меня есть начало и конец линии, остальные точки между первой и последней соединяются по возрастанию Х, а первую и последнюю я в самом конце соединяю. Нашлась ошибка. Последний раз редактировалось dklinge; 14.10.2015 в 20:46. |
14.10.2015, 20:44 | #8 |
Старожил
Регистрация: 17.11.2010
Сообщений: 18,922
|
Не понял - дважды по возрастанию Y. Проверь на бумаге с карандашом. Вангую - алгоритм будет с самопересечением.
Если бы архитекторы строили здания так, как программисты пишут программы, то первый залетевший дятел разрушил бы цивилизацию
|
14.10.2015, 20:50 | #9 |
Регистрация: 18.03.2015
Сообщений: 5
|
Так и есть, иногда выходит пересечение.
Моя задумка была в том, чтобы ломанная начиналась с самой низшей точки, а заканчивалась бы второй по наибольшему Y точкой. Почему-то иногда появляется сбой во второй и третьей точках с конца. Они будто меняются местами в очереди. Последний раз редактировалось dklinge; 14.10.2015 в 20:56. |
16.10.2015, 00:01 | #10 |
Новичок
Джуниор
Регистрация: 11.10.2011
Сообщений: 3,882
|
У меня вот такое чудо есть :
Код:
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Написать программу вычисления площади многоугольника используя формулу для вычисления площади треугольника в качестве подпрограммы | сердце | Паскаль, Turbo Pascal, PascalABC.NET | 0 | 24.12.2012 18:21 |
площадь многоугольника | Shenan | C# (си шарп) | 1 | 25.05.2012 22:15 |
Алгоритм подгонки площади многоугольника | Achervov | Помощь студентам | 0 | 19.03.2012 09:28 |
Построчный алгоритм заполнения многоугольника с затравкой (Билдер С++) | SKA_zo4nik | Помощь студентам | 8 | 28.03.2011 20:15 |
Рисование многоугольника в C# | vandrouny | C# (си шарп) | 3 | 11.10.2010 23:30 |