MAXimal

добавлено: 14 Sep 2010 2:07
редактировано: 6 Jan 2011 1:11

Преобразование геометрической инверсии

Преобразование геометрической инверсии (inversive geometry) — это особый тип преобразования точек на плоскости. Практическая польза этого преобразования в том, что зачастую оно позволяет свести решение геометрической задачи с окружностями к решению соответствующей задачи с прямыми, которая обычно имеет гораздо более простое решение.

По всей видимости, основоположником этого направления математики был Людвиг Иммануэль Магнус (Ludwig Immanuel Magnus), который в 1831 г. опубликовал статью об инверсных преобразованиях.

Определение

Зафиксируем окружность с центром в точке O радиуса r. Тогда инверсией точки P относительно этой окружности называется такая точка P^\prime, которая лежит на луче OP, а на расстояние наложено условие:

 OP \cdot OP^\prime = r^2.

Если считать, что центр O окружности совпадает с началом координат, то можно сказать, что точка P^\prime имеет тот же полярный угол, что и P, а расстояние вычисляется по указанной выше формуле.

В терминах комплексных чисел преобразование инверсии выражается достаточно просто, если считать, что центр O окружности совпадает с началом координат:

 z^\prime = r^2 \cdot \frac{ z }{ |z|^2 }.

С помощью сопряжённого элемента \overline{z} можно получить более простую форму:

 z^\prime = \frac{ r^2 }{ \overline{z} }.

Применение инверсии (в точке-середине доски) к изображению шахматной доски даёт интересную картинку (справа):

Свойства

Очевидно, что любая точка, лежащая на окружности, относительно которой производится преобразование инверсии, при отображении переходит в себя же. Любая точка, лежащая внутри окружности, переходит во внешнюю область, и наоборот. Считается, что центр окружности переходит в точку "бесконечность" \infty, а точка "бесконечность" — наоборот, в центр окружности:

 (O)^\prime = \infty,
 (\infty)^\prime = O.

Очевидно, что повторное применение преобразования инверсии обращает первое её применение — все точки возвращаются обратно:

 \left( P^\prime \right) ^\prime \equiv P.

Обобщённые окружности

Обобщённая окружность — это либо окружность, либо прямая (считается, что это тоже окружность, но имеющая бесконечный радиус).

Ключевое свойство преобразования инверсии — что при его применении обобщённая окружность всегда переходит в обобщённую окружность (подразумевается, что преобразование инверсии поточечно применяется ко всем точкам фигуры).

Сейчас мы увидим, что именно происходит с прямыми и окружностями при преобразовании инверсии.

Инверсия прямой, проходящей через точку O

Утверждается, что любая прямая, проходящая через O, после преобразования инверсии не меняется.

В самом деле, любая точка этой прямой, кроме O и \infty, переходит по определению тоже в точку этой прямой (причём в итоге получившиеся точки заполнят всю прямую целиком, поскольку преобразование инверсии обратимо). Остаются точки O и \infty, но при инверсии они переходят друг в друга, поэтому доказательство завершено.

Инверсия прямой, не проходящей через точку O

Утверждается, что любая такая прямая перейдёт в окружность, проходящую через O.

Рассмотрим любую точку P этой прямой, и рассмотрим также точку Q — ближайшую к O точку прямой. Понятно, что отрезок OQ перпендикулярен прямой, а потому образуемый им угол \angle PQO — прямой.

Воспользуемся теперь леммой о равных углах, которую мы докажем чуть позже, эта лемма даёт нам равенство:

 \angle PQO = \angle Q^\prime P^\prime O.

Следовательно, угол \angle Q^\prime P^\prime O тоже прямой. Поскольку мы брали точку P любой, то получается, что точка P^\prime лежит на окружности, построенной на O Q^\prime как на диаметре. Легко понять, что в итоге все точки прямой покроют всю эту окружность целиком, следовательно, утверждение доказано.

Инверсия окружности, проходящей через точку O

Любая такая окружность перейдёт в прямую, не проходящую через точку O.

В самом деле, это сразу следует из предыдущего пункта, если мы вспомним об обратимости преобразования инверсии.

Инверсия окружности, не проходящей через точку O

Любая такая окружность перейдёт в окружность, по-прежнему не проходящую через точку O.

В самом деле, рассмотрим любую такую окружность Z с центром в точке O_2. Соединим центры O и O_2 окружностей прямой; эта прямая пересечёт окружность Z в двух точках S и T (очевидно, ST — диаметр Z).

Теперь рассмотрим любую точку P, лежающую на окружности Z. Угол \angle SPT прямой для любой такой точки, но по следствию из леммы о равных углах также прямым должен быть и угол \angle S^\prime P^\prime T^\prime, откуда и следует, что точка P^\prime лежит на окружности, построенной на отрезке S^\prime T^\prime как на диаметре. Опять же, легко понять, что все образы P^\prime в итоге покроют эту окружность.

Понятно, что эта новая окружность не может проходить через O: иначе бы точка \infty должна была бы принадлежать старой окружности.

Лемма о равных углах

Это вспомогательное свойство, которое было использовано выше при анализе результатов преобразования инверсии.

Формулировка

Рассмотрим любые две точки P и Q, и применим к ним преобразование инверсии, получим точки P^\prime и Q^\prime. Тогда следующие углы равны:

 \angle PQO = \angle Q^\prime P^\prime O,
 \angle QPO = \angle P^\prime Q^\prime O.

Доказательство

Докажем, что треугольники \triangle PQO и \triangle Q^\prime P^\prime O подобны (порядок вершин важен!).

В самом деле, по определению преобразования инверсии имеем:

 OP \cdot OP^\prime = r^2,
 OQ \cdot OQ^\prime = r^2,

откуда получаем равенство:

 OP \cdot OP^\prime = OQ \cdot OQ^\prime,
 \frac{ OP }{ OQ } = \frac{ OQ^\prime }{ OP^\prime[...]

Таким образом, треугольники \triangle PQO и \triangle Q^\prime P^\prime O имеют общий угол, а две прилежащие к нему стороны пропорциональны, следовательно, эти треугольники подобны, а потому соответствующие углы совпадают.

Следствие из леммы

Если даны любые три точки P, Q, R, причём точка R лежит на отрезке OQ, то выполняется:

 \angle QPR = \angle Q^\prime P^\prime R^\prime,

причём эти углы ориентированы в разные стороны (т.е. если рассматривать эти два угла как ориентированные, то они разного знака).

Для доказательства заметим, что \angle QPR — это разность двух углов \angle QPO и \angle RPO, к каждому из которых можно применить лемму о равных углах:

 \angle QPR = \angle QPO - \angle RPO = \angle P^\[...]

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

Конформность

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

Для доказательства этого рассмотрим две произвольные кривые, пересекающиеся в точке P и имеющие в ней касательные. Пусть по первой кривой будет идти точка Q, по второй — точка R (мы их устремим в пределе к P).

Очевидно, что после применения инверсии кривые будут по-прежнему пересекаться (если, конечно, они не проходили через точку O, но такой случай мы не рассматриваем), и точкой их пересечения будет P^\prime.

Учитывая, что точка R лежит на прямой, соединяющей O и Q, получаем, что можем применить следствие из леммы о равных углах, из которой мы получаем:

 \angle QPR = - \angle Q^\prime P^\prime R^\prime,[...]

где под знаком "минус" мы понимаем то, что углы ориентированы в разных направлениях.

Устремляя точки Q и R к точке P, мы в пределе получаем, что это равенство — выражение угла между пересекающимися кривыми, что и требовалось доказать.

Свойство отражения

Если M — обобщённая окружность, то при преобразовании инверсии она сохраняется тогда и только тогда, когда M ортогональна окружности C, относительно которой производится инверсия (M и C считаются различными).

Доказательство этого свойства интересно тем, что оно демонстрирует применение геометрической инверсии для ухода от окружностей и упрощения задачи.

Первым шагом доказательства будет указание того факта, что M и C имеют как минимум две точки пересечения. В самом деле, преобразование инверсии относительно C отображает внутренность окружности в её внешность, и наоборот. Раз M после преобразования не изменилась, то значит, она содержит точки как из внутренности, так и из внешности окружности C. Отсюда и следует, что точек пересечения две (одна она быть не может — это означает касание двух окружностей, но этого случая, очевидно, быть по условию не может; совпадать окружности также не могут по определению).

Обозначим одну точку пересечения через A, другую — через B. Рассмотрим произвольную окружность с центром в точке A, и выполним преобразование инверсии относительно неё. Заметим, что тогда и окружность C, и обобщённая окружность M необходимо переходят в пересекающиеся прямые. Учитывая конформность преобразования инверсии, получаем, что M и M^\prime совпадали тогда и только тогда, когда угол между двумя этими пересекающимися прямыми прямой (в самом деле, первое преобразование инверсии, — относительно C, — изменяет направление угла между окружностями на противоположное, поэтому если окружность совпадает со своей инверсией, то углы между пересекающимися прямыми с обеих сторон должны совпадать, и равны \frac{ 180 }{ 2 } = 90 градусов).

Практическое применение

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

Построение фигур после инверсии

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

Если мы хотим найти окружность, получившуюся в результате инверсии прямой, то, согласно приведённым выше выкладкам, надо найти ближайшую к центру инверсии точку Q прямой, применить к ней инверсию (получив некую точку Q^\prime), и тогда искомая окружность будет иметь диаметр O Q^\prime.

Пусть теперь мы хотим найти окружность, получившуюся в результате инверсии другой окружности. Вообще говоря, центр новой окружности — не совпадает с образом центра старой окружности. Для определения центра новой окружности можно воспользоваться таким приёмом: провести через центр инверсии и центр старой окружности прямую, посмотреть её точки пересечения со старой окружностью, — пусть это будут точки S и T. Отрезок ST образует диаметр старой окружности, и легко понять, что после инверсии этот отрезок по-прежнему будет образовывать диаметр. Следовательно, центр новой окружности можно найти как среднее арифметическое точек S^\prime и T^\prime.

Параметры окружности после инверсии

Требуется по заданной окружности (по известным координатам её центра (x_0,y_0) и радиусу r_0) определить, в какую именно окружность она перейдёт после преобразования инверсии относительно окружности с центром в (x_c,y_c) и радиусом r.

Т.е. мы решаем задачу, описанную в предыдущем пункте, но хотим получить решение в аналитическом виде.

Ответ выглядит в виде формул:

 x^\prime = x_c + s (x_0 - x_c),
 y^\prime = y_c + s (y_0 - y_c),
 r^\prime = |s| \cdot r_0,

где

 s = \frac{ r^2 }{ (x_0 - x_c)^2 + (y_0 - y_c)^2 -[...]

Мнемонически эти формулы можно запомнить так: центр окружности переходит "почти" как по преобразованию инверсии, только в знаменателе помимо |z|^2 = (x_0 - x_c)^2 + (y_0 - y_c)^2 появилось ещё вычитаемое r_0^2.

Выводятся эти формулы ровно по описанному в предыдущем пункте алгоритму: находятся выражения для двух диаметральных точек S и T, затем к ним применяется инверсия, и затем берётся среднее арифметическое от их координат. Аналогично можно посчитать и радиус как половину длины отрезка ST.

Применение в доказательствах: задача о разбиении точек окружностью

Даны 2n различных точек на плоскости, а также произвольная точка O, отличная от всех остальных. Доказать, что найдётся окружность, проходящая через точку O, такая, что внутри и вне неё будет лежать одинаковое число точек набора, т.е. по n штук.

Для доказательства произведём преобразование инверсии относительно выбранной точки O (с любым радиусом, например, r=1). Тогда искомой окружности будет соответствовать прямая, не проходящая через точку O. Причём по одну сторону прямой лежит полуплоскость, соответствующая внутренности окружности, а по другую — соответствующая внешности. Понятно, что всегда найдётся такая прямая, которая разбивает множество из 2n точек на две половины по n точек, и при этом не проходит через точку O (например, такую прямую можно получить, повернув всю картину на любой такой угол, чтобы ни у каких из рассматриваемых 2n+1 точек не совпали координаты x, а затем просто взяв вертикальную прямую между n-ой и n+1-ой точками). Эта прямая соответствует искомой окружности, проходящей через точку O, а значит, утверждение доказано.

Применение при решении задач вычислительной геометрии

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

Т.е. если задача имеет достаточно сложный вид различных операций с окружностями, то имеет смысл применить ко входным данным преобразование инверсии, попытаться решить полученную модифицированную задачу без окружностей (или с меньшим их числом), и затем повторным применением инверсии получить решение исходной задачи.

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

Цепочки Штейнера

Даны две окружности C и D, одна находится строго внутри другой. Затем рисуется третья окружность E, касающаяся этих двух окружностей, после чего запускается итеративный процесс: каждый раз рисуется новая окружность так, чтобы она касалась предыдущей нарисованной, и первых двух. Рано или поздно очередная нарисованная окружность пересечётся с какой-то из уже поставленных, или по крайней мере коснётся её.

Случай пересечения:

Случай касания:

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

В случае касания получающая цепочка окружностей называется цепочкой Штейнера.

С этой цепочкой связано так называемое утверждение Штейнера (Steiner's porism): если существует хотя бы одна цепочка Штейнера (т.е. существует соответствующее положение стартовой касающейся окружности, приводящее к цепочке Штейнера), то при любом другом выборе стартовой касающейся окружности также будет получаться цепочка Штейнера, причём число окружностей в ней будет таким же.

Из этого утверждения следует, что и при решении задачи максимизации числа окружностей ответ не зависит от позиции первой поставленной окружности.

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

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

Применение в технике: прямило Липкина-Поселье

Долгое время задача преобразования кругового (вращательного) движения в прямолинейное оставалась весьма сложной в машиностроении, удавалось находить в лучшем случае приближённые решения. И лишь в 1864 г. офицер инженерного корпуса французской армии Шарль Никола Поселье (Charles-Nicolas Peaucellier) и в 1868 г. студент Чебышёва Липман Липкин (Lipman Lipkin) изобрели это устройство, основанное на идее геометрической инверсии. Устройство получило название "прямило Липкина-Поселье" (Peaucellier–Lipkin linkage).

Чтобы понять работу устройства, отметим на нём несколько точек:

Точка B совершает вращательное движение по окружности (красного цвета), в результате чего точка D необходимо движется по прямой (синего цвета). Наша задача — доказать, что точка D — суть инверсия точки B относительно центра O с некоторым радиусом r.

Формализуем условие задачи: что точка O жёстко закреплена, отрезки OA и OC совпадают, и также совпадает четвёрка отрезков AB, BC, CD, DA. Точка B движется вдоль окружности, проходящей через точку O.

Для доказательства заметим вначале, что точки O, B и D лежат на одной прямой (это следует из равенства треугольников). Обозначим через P точку пересечения отрезков AC и BD. Введём обозначения:

 OB=x,~~~BP=y,~~~AP=h.

Нам нужно показать, что величина OB \cdot OD = {\rm const}:

 OB \cdot OD = x(x+2y) = x^2 + 2xy.

По теореме Пифагора получаем:

 OA^2 = (x+y)^2 + h^2,
 AD^2 = y^2 + h^2.

Возьмём разность этих двух величин:

 OA^2 - AD^2 = x^2 + 2xy = OB \cdot OD.

Таким образом, мы доказали, что OB \cdot OD = {\rm const}, что и означает, что D — инверсия точки B.