Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

ТЕОРЕМА КОЗЛОВА ПРО АФФИННОЙ ЕКВІВАЛЕНТНОСТІ ЗОБРАЖЕНЬ

Два зображення називаємо аффінно еквівалентними ( а-еквівалентними ), якщо вони перекладаються один в одного аффіннимі перетвореннями.

Лемма 1. Якщо два зображення а-еквівалентні, то вони еквівалентні.

Доведення. Потрібно показати, по суті, що при афінних перетвореннях чисельні значення елементів їх безлічі Т коду зображення не змінюються. Кожен елемент в Т визначається відношенням площ деяких трикутників. При перетвореннях зсуву, повороту і симетрії ці площі не змінюються, а значить не змінюється і їхнє ставлення. Нехай тепер відбувається стиснення (або розтягнення) зображення по осях х та у з коефіцієнтами до х і до у . Відомо [22], що в цьому випадку площа S ' фігури (або будь-який ес частини) буде після перетворення дорівнює Sk x k y (тут S- площа фігури до перетворення). Звідси випливає, що якщо p ' nuvip <7 - відповідний p m uv, ipq елемент безлічі безлічі Т після

Перетворення, ТО S muv k x ky / Sipqk x ky = S mtiV / Slpq = Pmuv, lpq

Лема доведена. ?

Нехай зображення В складається з точок, які є підмножиною точок зображення А з кодом < Ма, Та>. Позначимо через Мв безліч номерів тих і тільки тих точок з Л, які входять в зображення В. Відповідно через Тв позначимо безліч всіх тих елементів p fmuvipq з Та, для яких m, u, v, l, p, qМВ- Зображення В з кодом

< Мв, Тв > назвемо частиною зображення А. Будь-яке зображення В ' f a-еквівалентну зображенню В, назвемо подізображеніем зображення Л.

Будемо називати зображення з чотирьох точок четирехто- чечніком. Нехай в четирехточечніке Л з точок a, b, с, d точки а, 6 і з розташовані на одній прямій. Тоді S a b c = 0 і ті елементи з Та, для яких у відповідному відношенні S a bc входить в знаменник, не визначені, а ті, для яких 5 ' входить в чисельник (при що не дорівнює нулю знаменнику), дорівнюють нулю. Очевидно, можна стверджувати зворотне: якщо код

< Ма, Та> володіє вказаними властивостями, то в четирехточечніке Л точки а, Ь і з розташовані на одній прямій. У зображенні Л загального вигляду точки а, 6, с, що входять до зображення, розташовані на одній прямій в тому і тільки в тому випадку, якщо для будь-якої частини зображення Л, що є чстирехто- чечніком і включає точки а, 6, с, виконується зазначена властивість, що визначає схильність точок а, 6, з на одній прямій. У зображенні Л точки а, ..., а п (тх > 3) розташовані на одній прямій в тому і тільки в тому випадку, коли будь-які три точки з а ь ..., а п розташовані на одній прямій.

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

Лемма 2. Якщо за кодом плоского зображення обрані будь-які три його точки, що не лежать на одній прямій, і задано довільне (але не на одній прямій) положення цих точок

Мал. 1.3 :

на площині, то положення інших точок зображення визначається за кодом однозначно.

Доведення. Нехай наш код < Ма, Та> є кодом деякого плоского зображення А. Нехай га, р, q - три обрані точки, що не лежать на одній прямій, і а ', 6', d їх вихідне положення. Нехай s - четверта точка зображення, яка разом точками га, р, q утворює плоске зображення, тобто якщо д! - початкове положення точки s, то точки а ', 6', d і д! лежать в одній або двох паралельних прямих.

Припустимо, що задано нове положення а, 6, з точок га, р, q. Для визначення нового положення точки s скористаємося процедурою (стандартної) побудови за кодом четирехточечні- ка четвертої точки при відомих положеннях інших трьох. Вважаємо, що точки а, 6, з різні, лежать не на одній прямій, в іншому ж їх положення можна задавати довільним чином. Точку, положення якої визначається, позначимо через х.

Оскільки площа трикутника abc відома, то, використовуючи S a bx / S a b Cl S aC xf & abci ^ bcx / ^ abo знаходиться площа * Sa6x> & acxi Sbcx • Для трикутника abc довжини його сторін відомі, тому можна визначити довжини висот h a b , h ac , hb c , опущених з точки х на боку відповідно ab, ас і 6с. (Одна з цих висот може виявитися нульовою по довжині, дві бути нульовими, очевидно, не можуть). Таким чином, завдання зводиться до того, щоб по заданому трикутнику abc побудувати точку х та -

кую, що висоти з цієї точки на сторони ab f ас і ЬС трикутника є відповідно h a b, h ac і / i & c . Проводимо дві прямі, паралельні стороні ab по різні боки і віддалені від неї на величину h а ь, і дві прямі, паралельні стороні ас по різні її сторони і віддалені від неї на величину h ac . Виникає паралелограм, вершини якого позначені на рис. 4 как ?? 1, (? 2 > <Ез і Q 4 . За побудовою, точка х може розташовуватися тільки на вершинах цього паралелограма. Для остаточного визначення положення точки х потрібно провести дві прямі, паралельні залишилася осторонь трикутника abc (стороні ЬС на рис . 1.3) і віддалені від неї на величину hbc- Перетин цих прямих з вершинами паралелограма дасть можливі положення точки х.

Покажемо, що одне таке перетин гарантовано існує.

Розглянемо Афінний перетворення, яке переводить точки а ',?', D в точки а, 6 і с. Нехай це Афінний перетворення переводить точку d! в точку d. Згідно лемі 1 це Афінний перетворення не змінює коду і, отже, що точка d є гарантовано існуючим станом, точки х. Відзначимо, що так як Афінний перетворення переводить паралельні прямі в паралельні, то точки а, 6, з і d не лежать в одній або двох паралельних прямих.

Залишається питання, єдиним чи може вийти положення відновлюваної точки.

Припустимо, що для точки х можливі два різних положення х 1 і х ", одне з яких гарантована точка d.

  • 1. Припустимо, що точки х ' і х " збігаються з Q і Qz, які тому повинні бути рівновіддалені від сторони ЬС. Отже, відрізок ЬС повинен ділити відрізок Q1Q2 навпіл, тобто точка Ь повинна лежати на відрізку Q 1 Q 2 • В цьому випадку а, 6, с, х 'і х "розташовані на двох паралельних відрізках: відрізку ас і відрізку QQ 2 , і, отже, на двох паралельних відрізках лежать точки а, 6, с і d - прийшли до протиріччя.
  • 2. Аналогічним чином приходимо до протиріччя в припущенні, що х ' і х " збігаються з Qi і Q 4 .

Якщо х ' і х "збігаються з Q і Q3, то відрізок QQ $ повинен ділитися стороною ЬС навпіл. Однак серединою діагоналі Q 1 Q 3 повинен ділитися стороною 6с навпіл. Однак серединою діагоналі Q 1 Q 3 паралелограма є, по побудові, точка а .

Якщо х 'і х "збігаються з Q 2 і Q3, то відрізок Q2Q3 повинен бути або паралельний відрізку 6с, або ділитися цим відрізком або його продовженням навпіл. І те, і інше суперечливо з побудови. Аналогічне має місце і при збігу х' і х "з Q 4 .

3. Нехай, нарешті, х 'і х "збігаються з Q 2 і Q 4 . Тоді діагональ Q 2 Q 4 повинна бути паралельною стороні 6с, що суперечить тому, що точки а, 6, cud чи не лежать на двох паралельних прямих.

Тим самим ми довели, що положення точки х визначається однозначно і збігається з точкою d за умови, що точки то, р, q і s не лежать в двох паралельних прямих.

Розіб'ємо безліч точок зображення А, відмінних від точок то, р, <7, на два класи А і А 2 . У безліч А включимо точки s такі, що то, р, <7 і s не лежать в двох паралельних прямих, а клас А 2 складуть залишилися точки.

Як ми показали вище, положення кожної точки їх А визначається однозначно становищем точок то, р, q , причому так як зображення А плоске, то безліч А - непорожня.

Розглянемо довільну точку s з безлічі А 2 . Візьмемо довільну точку г з безлічі А> положення якої вже визначено. Точки m, р, q, s і г утворюють плоске зображення, значить з чотирьох m, р, q і г можна вибрати три, що вони разом з точкою s утворюють плоске зображення, тобто чи не лежать на двох паралельних прямих. Тоді за цими трьома точка положення точки s визначається однозначно.

Лема доведена. ?

Теорема 1. Два плоских зображення еквівалентні точно тоді, коли вони а-еквівалентні.

Доведення. В одну сторону теорема 1 випливає з леми

1.

Покажемо тепер, що якщо плоскі зображення А і В еквівалентні, то вони a-еквівалентні. Виберемо на А три точки

а, 6, с, не лежать на одній прямій. Нехай наступній з визначення еквівалентності біекція точкам а, 6, з зіставляються точки відповідно ahd зображення В. афінних перетворень зображення В сумісний його точки а ', Ь', з 'з точками відповідно а, b, с зображення Л. Оскільки положення інших точок зображення В, при заданих точках a? d визначається, відповідно до леми 2, однозначно, то, отже, вони співпадуть з точками зображення Л.

Теорема доведена. ?

 
<<   ЗМІСТ   >>