| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Нахождение подобных вершин |
| Автор: radistor 16.7.2012, 20:18 | ||
| Сломал всю голову, но никак не придумаю алгоритм к следующей задачке. Есть две фигуры заданные координатами вершин http://s1.ipicture.ru/Gallery/Viewfull/11888105.html Визуально, сразу можно сказать какой вершине первой фигуры соответсвует вершина второй фигуры. А как алгоритмически это осуществить? Дополнительные данные по фигурам - Фигура относительно другой может быть повернута не более 90 градусов - Отрезки соединяющие вершины не обязательно равны. В процентном соотношение различие 0-15% Для примера дам координаты двух вышеизображенных фигур.
|
| Автор: Skevalt 17.7.2012, 06:38 |
| Можно таким методом: 1. Находим центр масс каждой фигуры 2. Осуществляем параллельный перенос одной из фигур так, что бы их центры масс совпали 3. Аппроксимируем множество вершин каждой из фигур прямой с помощью метода наименьших квадратов (упрощение метода главных компонент) 4. Находим угол между двумя получившимися прямыми и поворачиваем одну из фигур относительно центра масс на получившийся угол Вот примерное соответствие и получается. |
| Автор: Earnest 17.7.2012, 06:46 |
| Если фигуры почти подобны, то можно их сначала одинаково ориентировать (например, вдоль самой длинной стороны), выровнять масштабы (т.е. пересчитать длину всех ребер относительно периметра), а затем просто наложить, совместив центры масс. И куда они денутся... Если возможна неопределенность с отражением, ну тогда 2 варианта посмотреть и взять лучший. А в более общем случае нужно перебирать решения, строить их оценку и выбирать лучшую. Что касается перебора, то в твоей задаче можно тупо делать полный перебор, трудоемкость линейная от числа вершин. Т.е. ориентируем фигуры одинаково (например, по часовой стрелке), и начинаем перебор: сопоставляем вершины, начиная с первой (т.е. 0-0, 1-1 и т.д.), строим оценку, смещаемся на одну вершину (0-1, 1-2...), опять строим оценку, пока не пройдем цикл, выбираем лучшую оценку. Другой подход - строим двудольный граф, соединяя вершины фигур ребрами с весами. Затем выбираем паросочетание с наименьшим общим весом (или наибольшим, это как веса задавать). Оценка решения или веса ребер - отдельный вопрос. Оценка должна отражать "похожесть" соединяемых вершин. Например, трудоемкость превращения одной в другую (перемещение, изменение длины смежных ребер, их поворот до совпадения угла) |
| Автор: radistor 17.7.2012, 09:51 |
| Skevalt, 3. Аппроксимируем множество вершин каждой из фигур прямой с помощью метода наименьших квадратов (упрощение метода главных компонент) Можно подробнее про апроксимацию? Т.е какие вершины брать для апроксимации? Earnest, фигуры почти подобны. Различия не очень значительны, но они есть. можно их сначала одинаково ориентировать (например, вдоль самой длинной стороны) - а если даны два абсолютно одинаковых квадрата, просто один повернут относительно другого (допустим на 10 градусов)? Т.е пока что я понял из ответов 1. Совмещаем фигуры путем параллельного переноса и поворота. Как поворачивать, до конца не понял 2. Находить веса вершин или прямых их соединяющих и искать соответсвие. Тут довольно неординарная задача |
| Автор: Skevalt 17.7.2012, 13:46 |
| Взять все множество вершин и провести через них прямую по http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%BD%D0%B0%D0%B8%D0%BC%D0%B5%D0%BD%D1%8C%D1%88%D0%B8%D1%85_%D0%BA%D0%B2%D0%B0%D0%B4%D1%80%D0%B0%D1%82%D0%BE%D0%B2. Разность углов наклона прямых использовать для определения угла поворота фигуры. Earnest, правильно говорит, перебор здесь будет хорошо работать. |
| Автор: Earnest 18.7.2012, 12:19 | ||
1) можно определить главные оси инерции по моментам - это общий случай 2) по простому, как я предлагала: находим самую длинную сторону, поворачиваем так, чтобы она была горизонтальна |
| Автор: _Y_ 18.7.2012, 21:20 |
| И опять делаю рекламу http://forum.vingrad.ru/index.php?showtopic=314777&view=findpost&p=2246148. Прямо-таки в двух темах подряд. Если фигуры подобны - их нетрудно распознать. Там в книге есть такой раздел №4.3 кажется. ЗЫ: Надо, что-ли, с авторов процент брать какой за рекламу  |
