Определение пар точек в двух контурах

@imerlin · Регистрация: 02.06.2014

Студворк — интернет-сервис помощи студентам

Здравствуйте!
Не знаю как правильно называется моя задача и не смог сформулировать ее для поиска в гугле, поэтому прошу помощи здесь. Если данный вопрос был разобран (здесь или на других ресурсах) прошу ткнуть носом.
Задача: даны два контура в разных системах координат. Преобразования СК афинные, то есть это комбинация масштабирования, сдвига и поворота, но при этом на любом этапе преобразования возможно внесение некоторых ошибок (машинное округление, неверный ввод данных, ошибки при пересчете и т.д.).
Контуры заданы последовательностью точек. Начальная точка и направление обхода в общем случае могут не совпадать.
Как найти пары соответствующих точек в разных контурах?
Пока предполагаю как то определить нулевую точку, после чего найти углы векторов от начала координат до точек, отсортировать их и таким путем получить массива попарно совпадающих точек. Может кто подсказать правильное решение этой задачи?

@woldemas · 09.10.2019, 18:16

Сообщение от imerlin

Как найти пары соответствующих точек в разных контурах?

Итеративная минимизация функции расстояния по параметрам трансформации.
ICP - iterative closest point.

@Fulcrum_013 · 09.10.2019, 18:27

imerlin, Контура выпуклые? Если невыпуклые строим выпуклые оболочки. Дальше действуем по теореме о минимальном охватывающем прямоугольнике. Для выпуклого контура он всегда лежит на самой длинной стороне. Соответственно выбираем за начальную точку одну из точек этой стороны. Какую именно - ну к примеру определять на основании угла/отношения длины с примыкающей стороной.
Единственное что стоит как то озаботится различением сторон с одинаковой длиной. Для правильного многоугольника к примеру работать вообще не будет. Так же как и для к примеру для параллелограмма всегда будет два равноценных варианта, какие критерии не выбери. Но для таких случаев как бы вообще ничего кроме предварительной нумерации точек не сработает.

@Excalibur921 · 10.10.2019, 18:50

Для каждого контура.
Центр масс точек контура даст центр.
Найти всем углы между отрезками
A(Центр масс) N(точка контура) и
A(Центр масс) B(Центр масс X+ 1).
Отсортировать по возрастанию угла.
Получим две ломанные, 2 массива углов.

Минимум одной неизвестной.
Найти такой угол сдвига угла одного массива чтобы сумма разностей между массивами была минимальна.
Локализация корня, перебор угла сдвига с шагом N радиан от 0 до 2 пи.
Уточнение корня например дихотомией.

Новые блоги и статьи Все статьи Все блоги /
http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .	Первый деплой lagorue 16.01.2026 Не спеша развернул своё 1ое приложение в kubernetes. А дальше мне интересно создать 1фронтэнд приложения и 2 бэкэнд приложения развернуть 2 деплоя в кубере получится 2 сервиса и что-бы они. . .	Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь постоянного тока с R, L, C, k(ключ), U, E, J. Программа составляет систему уравнений по 1 и 2 законам Кирхгофа, решает её и находит: токи, напряжения и их 1 и 2 производные при t = 0;. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .
Изучаю kubernetes lagorue 13.01.2026 А пригодятся-ли мне знания kubernetes в России?	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .	Classic Notepad for Windows 11 Jel 10.01.2026 Old Classic Notepad for Windows 11 Приложение для Windows 11, позволяющее пользователям вернуть классическую версию текстового редактора «Блокнот» из Windows 10. Программа предоставляет более. . .

@imerlin 5 / 5 / 0 Регистрация: 02.06.2014 Сообщений: 37

	Определение пар точек в двух контурах 09.10.2019, 15:16. Показов 889. Ответов 3 Метки нет (Все метки) Здравствуйте! Не знаю как правильно называется моя задача и не смог сформулировать ее для поиска в гугле, поэтому прошу помощи здесь. Если данный вопрос был разобран (здесь или на других ресурсах) прошу ткнуть носом. Задача: даны два контура в разных системах координат. Преобразования СК афинные, то есть это комбинация масштабирования, сдвига и поворота, но при этом на любом этапе преобразования возможно внесение некоторых ошибок (машинное округление, неверный ввод данных, ошибки при пересчете и т.д.). Контуры заданы последовательностью точек. Начальная точка и направление обхода в общем случае могут не совпадать. Как найти пары соответствующих точек в разных контурах? Пока предполагаю как то определить нулевую точку, после чего найти углы векторов от начала координат до точек, отсортировать их и таким путем получить массива попарно совпадающих точек. Может кто подсказать правильное решение этой задачи? 0

@Fulcrum_013 2083 / 1574 / 169 Регистрация: 14.12.2014 Сообщений: 13,614
	09.10.2019, 18:27
	imerlin, Контура выпуклые? Если невыпуклые строим выпуклые оболочки. Дальше действуем по теореме о минимальном охватывающем прямоугольнике. Для выпуклого контура он всегда лежит на самой длинной стороне. Соответственно выбираем за начальную точку одну из точек этой стороны. Какую именно - ну к примеру определять на основании угла/отношения длины с примыкающей стороной. Единственное что стоит как то озаботится различением сторон с одинаковой длиной. Для правильного многоугольника к примеру работать вообще не будет. Так же как и для к примеру для параллелограмма всегда будет два равноценных варианта, какие критерии не выбери. Но для таких случаев как бы вообще ничего кроме предварительной нумерации точек не сработает. 0

@Excalibur921 1472 / 827 / 140 Регистрация: 12.10.2013 Сообщений: 5,456
	10.10.2019, 18:50
	Для каждого контура. Центр масс точек контура даст центр. Найти всем углы между отрезками A(Центр масс) N(точка контура) и A(Центр масс) B(Центр масс X+ 1). Отсортировать по возрастанию угла. Получим две ломанные, 2 массива углов. Минимум одной неизвестной. Найти такой угол сдвига угла одного массива чтобы сумма разностей между массивами была минимальна. Локализация корня, перебор угла сдвига с шагом N радиан от 0 до 2 пи. Уточнение корня например дихотомией. 0