/ Редактирование карты / Глава 20. Трансформация координат

Типы преобразования координат

Трансформацией координат в системе ObjectLand называется замена прежних значений координат всех или части объектов карты на новые значения, вычисленные по некоторому закону преобразования. При выполнении операции трансформации пользователь не имеет дела с отдельными объектами, а вместо этого должен задать закон преобразования координат и указать, к какому множеству объектов должно быть применено это преобразование.

Имеется два способа выполнения трансформации.

• Преобразование может быть выполнено как одноразовая операция, приводящая к изменению координат соответствующих объектов, хранящихся в базе данных. В дальнейшем эти объекты будут храниться в измененном виде.

• Пользователь может предпочесть задать преобразование как свойство темы или свойство слоя темы (см. гл. 15 «Свойства темы и ее компонентов»). В этом случае объекты, хранящиеся в базе данных, не претерпевают изменений, однако всякий раз при отображении соответствующей темы выполняется «на лету» данное преобразование и объекты отображаются с измененными значениями координат.

Оба способа выполнения трансформации основываются на одних и тех же способах задания законов преобразования координат. Дальнейшее изложение ориентировано в основном на одноразовое выполнение преобразования, а немногие отличия, касающиеся трансформации «на лету», будут отмечаться особо.

Для определения закона преобразования пользователь должен выполнить два действия:

• Выбрать тип преобразования из нескольких возможных типов, предлагаемых системой.

• Задать множество опорных точек преобразования, указав исходные координаты этих точек и их новые (желаемые) координаты.

В зависимости от выбранного типа преобразования, система обеспечивает либо точное, либо приближенное совпадение рассчитанных координат опорных точек с их указанными новыми координатами. При этом для объектов карты координаты пересчитываются по тому же закону, т.е. изменяются согласованно с изменением координат опорных точек.

Выбор типа преобразования зависит, прежде всего, от задачи, для решения которой используется операция трансформации. Можно указать, по крайней мере, две существенно разные практические ситуации, в которых с успехом может быть применена эта операция.

• Переход к другой системе координат. По тем или иным соображениям может оказаться необходимым перевести координаты всех объектов карты из первоначально выбранной декартовой системы координат (см. гл. 9 «Карты») в другую, также декартову систему, отличающуюся значением единицы длины, положением начала координат или даже направлением осей. Несколько более сложной является ситуация, когда нужно объединить в рамках одной карты объекты, изначально введенные в разных системах координат. В этом случае для части объектов необходимо выполнить переход к той системе координат, в которой заданы остальные объекты.

• Уточнение координат по ориентирам. В результате проведения более точных измерений для некоторых характерных точек карты (ориентиров) могут быть получены уточненные значения координат, отличающиеся от тех значений, которые были ранее установлены для этих точек. Если в этой ситуации просто отредактировать объекты-ориентиры, то будет нарушено взаимное положение ориентиров и близких к ним по расположению объектов. Задача заключается в том, чтобы пересчитать координаты всех объектов согласованным образом. Говоря математическим языком, требуется построить непрерывную и по возможности гладкую функцию преобразования координат по заданным опорным точкам.

Две описанные ситуации предъявляют существенно разные требования к выполняемому преобразованию. В первом случае требуется лишь пересчитать координаты из одной декартовой системы в другую. Эта задача решается без проблем, если известны обе системы координат. Вторая задача не имеет столь однозначного и идеального решения. Возникающие трудности проще всего пояснить на таком примере. Допустим, три опорные точки располагались на одной прямой, но после уточнения координат оказалось, что одна из них несколько смещена в сторону от прямой. В этом случае любой предложенный закон преобразования либо должен переводить некоторые прямые линии в кривые (или ломаные), либо не сможет обеспечить точное преобразование всех трех точек. Чтобы облегчить поиск разумного компромисса между точностью преобразования опорных точек и минимизацией искажений остальных объектов, система ObjectLand предлагает несколько типов преобразований на выбор.

Пользователь, не имеющий желания вдаваться в детали, может пока пропустить текст до начала следующего пункта и руководствоваться на практике простым правилом: для перехода к другой системе координат следует использовать преобразование подобия, а для уточнения координат по ориентирам – аффинно-локальное.

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

• Преобразование подобия решает задачу перехода от одной декартовой системы координат к другой. Чтобы задать преобразование, достаточно выбрать в качестве опорных точек любые две точки плоскости и указать старые и новые координаты этих точек. Удобно принять в качестве опорных точек начало координат и какую-либо точку, лежащую на оси X или Y.

• Аффинное преобразование, которое называют также линейным преобразованием. Это преобразование, которое всегда переводит прямые линии в прямые, при этом параллельные прямые остаются параллельными. Углы между пересекающимися прямыми могут изменяться или оставаться прежними. Рассмотренное выше преобразование подобия является частным случаем аффинного. Можно сказать также, что произвольное аффинное преобразование переводит заданный квадрат в любой заданный параллелограмм, в то время как преобразование подобия переводит квадрат в любой другой заданный квадрат.

• Чтобы задать аффинное преобразование, достаточно выбрать в качестве опорных точек три любые точки, не лежащие на одной прямой, и указать старые и новые координаты этих точек. Удобно принять в качестве опорных точек начало координат и две точки, лежащие соответственно на осях X и Y.

• Аффинное преобразование с вычислением коэффициентов методом наименьших квадратов предназначено для случая, когда число заданных опорных точек больше трех. Это означает, что решается задача уточнения по ориентирам. Если число ориентиров превышает 3 и некоторые из значений их координат (старых или новых) получены с некоторой погрешностью, то нельзя рассчитывать на построение аффинного преобразования, точно переводящего все ориентиры в новое положение. Можно обеспечить точное преобразование любых трех точек, но чем хуже остальные опорные точки? Чтобы не прибегать к произвольному выбору трех точек для построения преобразования, можно использовать известный в математике метод наименьших квадратов. При построении преобразования по этому методу может оказаться, что ни для одной из опорных точек расчетное положение не совпадет с измеренными новыми координатами, однако средняя ошибка (точнее, средний квадрат расстояния между измеренным и рассчитанным положением каждой опорной точки) будет минимальной среди всевозможных аффинных преобразований. Таким образом, данный тип преобразования не может обеспечить точность преобразования опорных точек, но зато сохраняет все прямые линии прямыми.

• Полиномиальное преобразование. Это один из типов нелинейных преобразований, т.е. таких, которые гарантируют точное преобразование для любого количества опорных точек, расплачиваясь за это искривлением прямых линий.

• Как известно из математического анализа, если заданы значения некоторой функции вещественного или комплексного переменного в N различных точках, то можно единственным образом построить полином степени N-1, принимающий в этих точках заданные значения (интерполяционный полином Лагранжа). Именно таким образом строится закон преобразования координат для полиномиального типа преобразования. Точки плоскости рассматриваются как комплексные числа. Для любого количества опорных точек гарантируется точное (в пределах погрешности вычислений) преобразование их координат в заданные новые значения. В теории функций комплексного переменного данный тип преобразования называется конформным голоморфным преобразованием. Интересной особенностью этого преобразования является то, что, несмотря на искривление линий, все углы пересечения линий сохраняют неизменное значение.

• К сожалению, полиномиальное преобразование как средство решения задачи уточнения координат имеет ряд недостатков. Основной из них – чрезмерное искривление линий, резко усиливающееся по мере удаления от опорных точек.

• Локальное преобразование. В отличие от предыдущего типа преобразования, данное преобразование основано не на строгих математических предпосылках, а скорее на соображениях здравого смысла. Идея заключается в следующем. Для каждой из опорных точек можно тем или иным способом построить такую нелинейную функцию, которая преобразует старые координаты этой точки в ее новые координаты, а для остальных точек изменяет координаты тем менее, чем дальше точка отстоит от опорной. На большом расстоянии от опорной точки изменение координат должно стремиться к нулю. Построив подобные функции для каждой опорной точки, можно определить общее преобразование как взвешенную сумму этих функций, при этом коэффициенты суммирования нетрудно рассчитать таким образом, чтобы компенсировать небольшой сдвиг каждой опорной точки под влиянием перемещения остальных опорных точек.

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

• Комбинированные аффинно-нелинейные преобразования. Опыт различных областей прикладной математики показывает, что учет нелинейных эффектов дает хорошие результаты в том случае, когда величина нелинейных искажений достаточно мала. В задаче трансформации координат это означает, что для успешного применения полиномиального или локального преобразования желательно, чтобы разность между новыми и старыми координатами опорных точек была как можно меньше. Можно ожидать заметного улучшения качества трансформации, если сначала выполнить аффинное преобразование по методу наименьших квадратов, а затем применить один из нелинейных методов. При этом на первом (аффинном) этапе в большинстве случаев удается значительно сократить расстояния, на которые должны быть перемещены опорные точки, и в результате этого второй (нелинейный) этап преобразования вносит значительно меньшие нелинейные искажения, чем при непосредственном применении без предварительного выполнения линейной части преобразования.

• Как показывает практика, наилучшие результаты в задаче уточнения координат по ориентирам дает использование комбинированного аффинно-локального преобразования.

В табл. 20-1 приведены основные свойства всех типов преобразований координат.

Табл. 20-1. Свойства типов преобразований