Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.80/5: Рейтинг темы: голосов - 5, средняя оценка - 4.80
radistor
0 / 0 / 0
Регистрация: 16.07.2012
Сообщений: 6
1

Нахождение подобных вершин

16.07.2012, 21:32. Просмотров 830. Ответов 10
Метки нет (Все метки)

Сломал всю голову, но никак не придумаю алгоритм к следующей задачке.

Есть две фигуры заданные координатами вершин
http://s1.ipicture.ru/uploads/20120716/IUniVPJH.png
Визуально, сразу можно сказать какой вершине первой фигуры соответсвует вершина второй фигуры.
А как алгоритмически это осуществить?

Дополнительные данные по фигурам
- Фигура относительно другой может быть повернута не более 90 градусов
- Отрезки соединяющие вершины не обязательно равны. В процентном соотношение различие 0-15%

Для примера дам координаты двух вышеизображенных фигур.
Код
Fig. 1
1522,868
591,1182
1234,178
819,912
534,1021
591,392

Fig. 2
2955,1239
1977,663
2278,798
3318,628
1919,819
2615,195
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.07.2012, 21:32
Ответы с готовыми решениями:

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

Нахождение вершин в орграфе
Я хочу считать граф из файла и передать его в уже написанную функцию.Но не до конца понял как...

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

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

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

10
Thread
programmer
1871 / 343 / 27
Регистрация: 01.06.2011
Сообщений: 3,047
Записей в блоге: 1
17.07.2012, 01:19 2
По индексу в массиве не катит?
0
murderer
3326 / 1472 / 135
Регистрация: 06.10.2010
Сообщений: 3,233
17.07.2012, 06:17 3
1) Найти углы между гранями и из них составить массив для обоих фигур.
2) Делать циклический сдвиг первого массива, пока тот не совпадёт со вторым.
0
radistor
0 / 0 / 0
Регистрация: 16.07.2012
Сообщений: 6
17.07.2012, 10:30  [ТС] 4
Цитата Сообщение от murderer Посмотреть сообщение
1) Найти углы между гранями и из них составить массив для обоих фигур.
2) Делать циклический сдвиг первого массива, пока тот не совпадёт со вторым.
А если углы одинаковы? Т.е допустим первая фигура - квадрат, а вторая - тоже квадрат только немного повернутый (допустим на 10 градусов) относительно другой
0
murderer
3326 / 1472 / 135
Регистрация: 06.10.2010
Сообщений: 3,233
17.07.2012, 12:21 5
Можно к углам добавить ещё длину грани. А в случае с квадратом все вершины равноправны.
0
radistor
0 / 0 / 0
Регистрация: 16.07.2012
Сообщений: 6
17.07.2012, 14:32  [ТС] 6
Цитата Сообщение от murderer Посмотреть сообщение
Можно к углам добавить ещё длину грани. А в случае с квадратом все вершины равноправны.
Да, все вершины равноправны, но как найти соответсвие первой вершине первой фигуры соответсвует 4 вершина второй фигуры
0
Thread
programmer
1871 / 343 / 27
Регистрация: 01.06.2011
Сообщений: 3,047
Записей в блоге: 1
17.07.2012, 15:53 7
порядок следования вершин как-то определяеться для фигур?
В смысле к примеру самая правая это 1,дальше 2...n.Или нет закономерности никакой?
0
radistor
0 / 0 / 0
Регистрация: 16.07.2012
Сообщений: 6
17.07.2012, 17:55  [ТС] 8
http://s2.ipicture.ru/uploads/20120716/qJDeI4H2.png
вот картинка
Надо составить соответсвие:
Вершина первой фигуры - вершина второй фигуры
1-3
2-2
3-1
4-6
5-5
6-4

Порядок следования должен быть по порядку, но начинаться может с любой вершины и идти по часовой или против часовой стрелки
0
Alex330
118 / 118 / 4
Регистрация: 12.06.2012
Сообщений: 130
17.07.2012, 22:28 9
А можно их хотя бы нумеровать в одном направлении (только по или против часовой) на вашем рисунке они в разные стороны занумерованы? Предложение такое: 1) создать два массива которые будут содержать последовательные значения углов при вершинах. 2) "сдвигать" один массив относительно другого пока не будет получена минимальная величина от суммы элементов третьего массива, равного модулю разности первых двух на каждом шаге.
0
Greek9000
4 / 4 / 2
Регистрация: 05.07.2009
Сообщений: 13
18.07.2012, 21:48 10
Предлагаю такой вариант (подразумевается, что количество вершин у фигур одинаковое и равно N):
1. Нормализовать длины сторон (длину каждого ребра разделить на периметр фигуры, в которую входит это ребро)
2. Для каждой вершины посчитать угол между её ребрами
3. Построить для каждой фигуры список из элементов вида " № - Длина - Угол - Длина " (по одному элементу на вершину) Список содержит порядковый номер вершины и длины прилегающих рёбер.
4. Начать циклически сдвигать элементы одного списка относительно другого, и при каждом сдвиге считать сумму абсолютных значений поэлементных разностей (Ʃ(ΔДлина + ΔУгол + ΔДлина))
5. Минимальная сумма будет соответствовать максимальному совпадению вершин.
Как-то так...
0
murderer
3326 / 1472 / 135
Регистрация: 06.10.2010
Сообщений: 3,233
19.07.2012, 07:17 11
Нормализовать длины не обязательно.
0
19.07.2012, 07:17
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.07.2012, 07:17

Нахождение координат вершин квадрата,описанного вокруг окружности
Здравствуйте! Подскажите,пожалуйста. Задача такая: есть окружность,известны координаты ее центра...

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

Нахождение площади параллелограмма, треугольника и объема параллелепипеда, тетраэдра по координатам вершин
Нахождение площади параллелограмма, треугольника и объема параллелепипеда, тетраэдра по координатам...


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

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

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