Форум программистов, компьютерный форум, киберфорум
C# для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.88/8: Рейтинг темы: голосов - 8, средняя оценка - 4.88
16 / 0 / 0
Регистрация: 26.02.2014
Сообщений: 97
1

Построить замкнутую линию по заранее указанным точкам

02.04.2014, 17:52. Просмотров 1607. Ответов 8
Метки нет (Все метки)

Дано n точек на плоскости. Указать (n-1)-звенную не самопересекающуюся
замкнутую ломаную, проходящую через все эти точки. (Соседним отрезкам
ломаной разрешается лежать на одной прямой.)
помогите пожалуйста никак не могу в её понять.заранее спасибо!
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
02.04.2014, 17:52
Ответы с готовыми решениями:

Нарисовать замкнутую ломаную линию по точкам, над каждым отрезком вывести длину
В общем этот код всегда на выходе выдает 1. Я не могу понять почему. Этот фрагмент кода выводит над...

По полученным точкам графика перегиба при разных t построить огибающую линию
Программа для графика уже есть, требуется ее доделать(доработать). Собственно задание: 1....

Добавление точек в замкнутую ломаную линию
Всем здравствуйте. Есть массив точек (изначально он может состоять только из 1 точки)....

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

8
Администратор
Эксперт .NET
8827 / 4110 / 741
Регистрация: 17.04.2012
Сообщений: 8,943
Записей в блоге: 14
02.04.2014, 18:01 2
Gaber78, уточните, вам нужно только указать ломаную или ещё и построить её?
0
1049 / 856 / 195
Регистрация: 31.03.2010
Сообщений: 2,516
02.04.2014, 18:20 3
Gaber78, вспомните детские рисовалки, когда вместо рисунка есть только точки с номерами и мы линией соединяем номера.
тут у нас есть только точки, мы сами их должны пронумеровать так, чтоб полученные линии не пересекались.
предлагаю простой рекурсивный алгоритм(далеко не эффективный):
1. получаем точку
2. для новой точки проверяем пересекается ли полученный отрезок со всеми предыдущими
2.1. не пересекается - добавляем ее в текущий массив точек
2.1.1 берем первую незанятую точку и вызываем функцию с полученной
2.1.1.1. получили ложь - вызываем функцию со следующей незанятой точкой
2.1.1.2 получили истину - возвращаем истину
2.1.2.незанятых точек нет возвращаем истину
2.2. пересекается - возвращаем ложь

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

Pascal
1
2
3
4
5
6
7
8
9
function Intersection(ax1,ay1,ax2,ay2,bx1,by1,bx2,by2:real):boolean;
var v1,v2,v3,v4:real;
begin
   v1:=(bx2-bx1)*(ay1-by1)-(by2-by1)*(ax1-bx1);
   v2:=(bx2-bx1)*(ay2-by1)-(by2-by1)*(ax2-bx1);
   v3:=(ax2-ax1)*(by1-ay1)-(ay2-ay1)*(bx1-ax1);
   v4:=(ax2-ax1)*(by2-ay1)-(ay2-ay1)*(bx2-ax1);
   Intersection:=(v1*v2<0) and (v3*v4<0);
end;
0
Администратор
Эксперт .NET
8827 / 4110 / 741
Регистрация: 17.04.2012
Сообщений: 8,943
Записей в блоге: 14
02.04.2014, 18:24 4
Learx, по этому алгоритму мы можем запороть возможную ломаную, если последовательность точек будет не такой, как нам надо, например
Название: Polygon.png
Просмотров: 157

Размер: 2.8 Кб
Мы могли бы построить пятиугольник, но из-за порядка его так не построишь
0
1049 / 856 / 195
Регистрация: 31.03.2010
Сообщений: 2,516
02.04.2014, 18:42 5
tezaurismosis, спасибо, есть ошибка: - 2.1.1.1 должна возвращать ложь если точек не осталось
по вашей картинке, что получим:
глубина I) берем 1 - отрезков нет, вызываем с 2
II) берем 2 - получаем один отрезок, вызываем с 3
III) берем 3 - отрезок не пересекается, вызываем с 4
IV) берем 4 - пересекается возвращаем ложь
III) вызываем 5
IV) берем 5 - не пересекаются, вызываем 4
V) 4 - пересекаются, возвращаем ложь
IV) точек нет - возвращаем ложь
III) точек нет, возвращаем ложь
II) берем 4
III) берем 3 - ложь
II) берем 5 - ложь( не буду расписывать). закончились - возвращаем ложь
I) берем 3 - в итоге получаем ложь(не буду расписывать)
I) берем 4 - в итоге получим истину(4-2-3-5)
получили 1-4-2-3-5
0
Администратор
Эксперт .NET
8827 / 4110 / 741
Регистрация: 17.04.2012
Сообщений: 8,943
Записей в блоге: 14
02.04.2014, 18:50 6
Learx, ещё в конце соединим с первой полученной, надо 1-4-2-3-5-1, ведь нам надо замкнутую ломаную.
0
1049 / 856 / 195
Регистрация: 31.03.2010
Сообщений: 2,516
02.04.2014, 18:52 7
tezaurismosis, о замкнутости не было речи
более того такой алгоритм не может создать замкнутую, ведь 1 помечена как использованная
0
Администратор
Эксперт .NET
8827 / 4110 / 741
Регистрация: 17.04.2012
Сообщений: 8,943
Записей в блоге: 14
02.04.2014, 19:04 8
Цитата Сообщение от Learx Посмотреть сообщение
о замкнутости не было речи
Почему это?
Цитата Сообщение от Gaber78 Посмотреть сообщение
Указать (n-1)-звенную не самопересекающуюся
замкнутую ломаную, проходящую через все эти точки
Это просто нужно вынести вне алгоритма - взять последнюю полученную точку и соединить с первой, без проверок
0
1049 / 856 / 195
Регистрация: 31.03.2010
Сообщений: 2,516
02.04.2014, 19:17 9
tezaurismosis, блин, ктулху помутил мой разум и я не замтил замкнутости.
"добавить" не подойдет - не обязательно последнее добавление не пересечет существующих отрезков.
тогда уж чтоб не придумывать новый алгоритм - сделать это добавление и проверку для него, если не выполнится проверка вызывать с новой начальной точкой ф-цию

Добавлено через 3 минуты
как вариант, просто получить все перестановки и для полученной "ламанной" делать проверку
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
02.04.2014, 19:17

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Нарисовать линию по 2 точкам
Добрый день. Известны координаты 2 точек на экране. Как лучше всего нарисовать линию?

Провести линию canvas по точкам
Подскажите как можно провести canvas линию между созданными блоками div. Пока что получается...

Как нарисовать линию по точкам?
почему алгоритм брезенхэма с ошибками в википедии и как всетаки нарисовать линию по точкам?

Постройте ломаную линию по заданным точкам
На плоскости заданы n точек своими координатами. Постройте ломаную линию, проходящую через эти...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
9
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.