| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Нужно найти оси геометрической симетрии объекта |
| Автор: Empirik 17.8.2012, 12:49 |
| Добрый день. Есть геометрический 2D объект заданный двумя массивами - точек и ребер. Нужно найти все возможные оси его симетрии. В общем случае это вытянутый полигон, но возможны и варианты. Подскажите кто-нибудь решал подобную задачу? И если решил то, как ? |
| Автор: Lipetsk 17.8.2012, 13:15 |
| идея такая берем пару точек, предполагаем, они симметричны относительно некой оси, такая ось одна, берем её и проверяем является ли она осью симметрии для остальных |
| Автор: Akina 17.8.2012, 13:27 |
| Слишком много вариантов (пар точек), особенно если вершин дофига. Рёбры-то есть! а коли так, то ось симметрии проходит через вершину и середину ребра, если кол-во вершин нечётно, и через две вершины либо две середины рёбер, если нечётно. К тому же "слева и справа" от точек пересечения оси симметрии и фигуры будет одинаковое количество вершин. Ещё вариант - построить массив углов в любом направлении обхода. Если фигура симметрична, то ищем в удвоенном массиве (alfa(i)=alfa(i+N)) палиндром с длиной, равной количеству углов фигуры N. |
| Автор: ksnk 17.8.2012, 14:21 |
| Можно вычислить "центр симметрии" фигуры - среднее арифметическое всех координат. Если оси симметрии есть - они проходят через центр симметрии. Дальше перебираем все центры и углы по одному. Строим прямую из центра в эту точку. Называем `ось`. От выбранной точки идем в одну сторону и другую, перебирая вершины. Каждая пара обязана проектироваться на ось в одной и той-же точке и находится на одном расстоянии от оси. Если такое условие выполняется для всех вершин - `ось` является осью симметрии. По сравнению с вариантом Akina - несколько более однозначно-линейный вариант ;) |
| Автор: Akina 17.8.2012, 16:05 | ||
Далее взять координату противоположной по счёту вершины либо центра стороны и проверить, лежит ли она на этой "оси". Если ось не является осью симметрии - для большинства кандидатов в оси эта третья точка окажется в стороне... и можно не считать проекции. А если лежит - то это ещё ничего не значит, и можно развлекаться далее по описанному алгоритму. |
