Повна версія

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

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


<<   ЗМІСТ   >>

РОЗПІЗНАВАННЯ І ВІДНОВЛЕННЯ ОБ'ЄМНИХ ЗОБРАЖЕНЬ

Назвемо тривимірним зображенням Л або тілом кінцеве безліч точок в тривимірному евклідовому просторі. Занумеруем попарно різними номерами точки зображення А, тобто задамо функцію нумерації Мд. Нехай V mnuv і Vk spq - обсяги тетраедрів з вершинами в четвірках точок з номерами ТП, П, і, У І до } S } Ру q І нехай pmnuv, k P sq = Vmnuv / Vks P q- По- дотримуючись інструкцій, що порядок в четвірках не важливий, самі четвірки різні і для випадку, коли Vk spq = 0> Pmnuv, kP sq не визначене. Безліч індексованих чисел Pmnuv, k P s q для всіх таких пар четвірок позначимо через Т д. Кодом тіла назвемо пару <МД, Тд>. Тіла Л і В назвемо еквівалентними, якщо існують такі функції нумерації МД і Ms, що в кодових множинах Тд і Та елементи, відповідні однаковим індексам збігаються.

Тіла, всі крапки яких розташовані в одній площині, називаємо двовимірними і для них розглянутий код не визначений.

Тіла називаємо аффінно еквівалентними ( а-еквівалентними ), якщо вони переводяться одна в одну аффіннимі перетвореннями.

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

Наведемо без доведення наступне твердження.

Теорема 2. Два об'ємних зображень еквівалентні точно тоді , коли вони афінно еквівалентні.

Тепер звернемося до питання відновлення тривимірного тіла по його двовимірним проекція.

Розглянемо тіло Т і пряму, яка називається напрямком проекції. Напрямки проекції назвемо різними, якщо вони не паралельні. Проведемо через кожну точку тіла Т прямі, паралельні напрямку проекції а й звані променями. Вважаємо а таким, що на кожному промені знаходиться тільки одна точка тіла. Назвемо площину, що перетинає промені, площиною проекції , зображення, утворене точками перетину променів з площиною проекції - проекцією тіла (на дану площину по даному напрямку). Розглядаємо проекції тіла Т за різними напрямками і на різні площини. Взаємно однозначна відповідність між точками двох зображень назвемо їх розміткою. Відповідні один одному точки будемо позначати однією літерою (з різними індексами). Ясно, що описаним вище встановлюється взаємно однозначна відповідність між точками тіла Т і точками проекцій Si (r = 1,2, ...). Якщо а - точка тіла Т, то точку проекції 5 *, що лежить з нею на одному промені, позначимо через а, і будемо називати проекцією точки а. Це встановлює і взаємно однозначна відповідність між точками проекцій Si і Sji відповідні один одному точки є проекціями однієї і тієї ж точки тіла Т. Розмічені зображення А і В назвемо А'-еквівалентними, якщо можна перевести їх одне в інше аффіннимі перетвореннями так, що сполучаться відповідні один одному точки (позначення: А ж У). В іншому випадку А і В назвемо А'-різними (позначення: А Ф В). Частина зображення А , що складається з його точок а, 6, ..., v будемо позначати як А (а, Ь, ..., v). Три точки проекції, що не лежать на одній прямій, назвемо гранню, яка визначається цими точками площину - площиною грані. Три точки проекції, що не лежать на одній прямій, назвемо трикутником. Обмовимо позначення для спеціального випадку. Зображення А, що складається з точок а *, 6 *, с *, .. .Ui і прямий Li, будемо позначати через A (ai, bi, Ci, .. .Ui, Li). Аналогічно, зображення В, що складається з точок aj, bj, Cj , .. .Uj і прямий Lj, будемо позначати через B (aj, bj y Cj, .. .Uj, Lj). Назвемо зображення Лі У А'-еквівалентними, якщо їх можна перевести одне в інше аффіннимі перетвореннями так, що точки а *, 6 *, с *, .. сполучаться з точками відповідно aj, bj, Cj, ... Uj і пряма Li суміститься з прямою Lj.

Маючи тіло Т, заданий напрямок проекції а й змінюючи площині проекції, можна отримати деяке безліч {5} проекцій. Все проекції з {5} будуть попарно А'-еквівалентни- ми. З іншого боку, тіло Т - не єдине, проектуванням якого можна отримати безліч {5} проекцій. Таким буде, наприклад, тіло Т ', отримане заміною кожної точки тіла Т , що знаходиться на промені а х проектування, на якусь іншу точку х' на тому ж промені. У приватному і виродженим випадку всі крапки тіла Т 'можуть перебувати в одній площині. З цього випливає, що маючи одну або кілька проекцій з безлічі {5}, не можна відновити тіло Т. Проекції з {5} можна інтерпретувати як зображення тіла в одному ракурсі. Отже, для того, щоб відновити тіло, потрібно мати більш ніж одну проекцію, причому в різних ракурсах (тобто при різних напрямках проекції).

Теорема 3. Якщо S і S 2 суть А'-різні проекції тслаТ, то існує процедура, яка за проекціями S і S 2 побудує тіло Т ' таке, що тіла Т і Т' - а '-еквівалентни.

Опишемо процедуру, існування якої затверджується в теоремі 3, без доведення її коректності.

Нехай Si і? 2 - А'-різні проекції тіла Т , aibC на S і 026 202 на - трикутники. Будемо говорити, що точка D - 1 на Si лежить в площині трикутника aibiCi , якщо

В цьому випадку і cfe лежить в площині трикутника 026202- В іншому випадку говоримо, що di лежить поза площиною трикутника aibiCi (е / 2 лежить поза площиною трикутника 026202).

Нехай Si і S 2 - А'-різні проекції тіла Т. Розглянемо на 51 та 5 2 четвірку трійок точок ((ai6 1 ci) (a262C2) (c 1 eid 1 ) (c 2 e2rf 2 )) таку, що aibiCi і 026202 - трикутники, точки d і ej лежать поза площиною трикутника ai6iCi (і, відповідно, точки cfe і ег лежать поза площиною трикутника 026202) та з трійок

cCdi і c 2 d 2 e 2 хоча б одна трикутник. Таку четвірку назвемо правильною. Її точки на S і S 2 є проекціями точок а, 6, с, d y е тіла Т, причому abc і cde - межі, і площині цих граней різні. Позначимо через L лінію перетину цих площин, через L і L 2 - проекцію цієї лінії на S і S - 2. Очевидно, що Li і L 2 проходять через точки відповідно ci і з 2 . Для визначення положення прямих L і L 2 , тим самим, досить визначити ще по одній точці, що лежать на них. Наведемо алгоритм визначення по правильній четвірці ((ai & ici) (a 2 6 2 c 2 ) (cieidi) (c 22 e 2 )) ліній L і L 2 .

1. Покладемо, що тільки одна з трійок з ^ з ^ і c 2 rf 2 e 2 - трикутник, і нехай, для визначеності, це трійка c 2 d 2 e 2 . Отже, ci, d і ei лежать на одній прямій і, отже, напрямок проекції ос паралельно площині грані cde. В цьому випадку точки ci, d і ei лежать на прямій L, що і визначає її положення.

Пряма L в тілі Т лежить в площині трикутника абс, отже, 2 ( a 2 > ^ 2 »c 2 , L 2 ). Сумісний аффіннимі перетвореннями зображення S точки а у Ь і ci з точками відповідно а 2 , 6 2 і з 2 на 5 2 . Пряма Ь при цьому сполучиться з L 2 , що і визначає положення L 2 на? 2 .

2. Покладемо тепер, що трійки ciei ^ i і c 2 d 2 e 2 - трикутники.

Якщо будь-яка з точок aj і 6i лежить в площині трикутника ced y то пряма L проходить через цю точку і точку ci * Положення L 2 теж визначено тим, що вона проходить через відповідні точки на S 2 .

Нехай тепер точки а і & i лежать поза площиною трикутника cedi.

Якщо в тілі Т відрізок de паралельний площині грані abc і відрізок ab паралельний площині грані cde , то обидва відрізка повинні бути паралельні прямій L і, отже, паралельні між собою. В цьому випадку відрізки ai6i і de на 5 1 і а 2 6 2 і rf 2 c 2 на 5 - 2 паралельні між собою. Їх напрямки і визначають прямі L і Z, 2 .

Покладемо тепер, що або відрізок de не паралельний межі abc , або відрізок ab не паралельний межі cde. Нехай, для визначеності, відрізок de не паралельний межі abc. Обозна-

Мал. 1.4 :

чим через х точку перетину відрізка de мул його продовження з прямою L, і відповідно через х і Х 2 - відповідні точки на 5 * 1 і 5г- Точки а, 6, с і х лежать в тілі Т в одній площині, отже, « Si (ai, 6i, ci, xi) ~ * $ 2 (02,62, С2, Х2). Точ- ки с, d, е і х лежать в тілі Т в одній площині, і, отже, * Si ( c bdi> e i »si)« * ^ 2 (с2, ^ 2, ^ 2, ^ 2). Сумісний аффіннимі перетвореннями зображення S 2 його точки аг, 62 і С2 з точками відповідно а , & i і ci на Si. При цьому точка х ^ суміститься з точкою X t а точки е / 2 і займуть положення, які позначимо через d 2 і е ' 2 (рис. 1.4). Точка х лежить на відрізку ed або його продовженні. Точка Х2 - на відрізку е2 ^ 2 або його продовженні. Після суміщення х з Х2 точка х повинна, тим самим, бути перетином відрізків ed і e 2 d 2 або їх продовжень. Це і визначає положення прямої L на Si, а значить і L 2 на

5 2 .

Нехай 5 * 1 і - a'-різні проекції тіла Т. Наведемо процедуру побудови по S i і S 2 деякого тіла Т ', А'-еквівалент- ного тіла Т. Нехай aibiC на S i і <1262 ^ 2 на S 2 - трикутники і точка е лежить поза площиною трикутника a ^ biCi. Виберемо деяку пряму а ' (не паралельно площині зображення S 1) в якості напрямку проекції. Проведемо через точки а 1, & i, з і е промені, паралельні а ', і на кожному промені візьмемо по точці відповідно а', 6 ', з', е 'так, щоб вони не лежали в одній площині. Нехай тепер d - довільна точка на S. Побудуємо відповідну їй точку d! тіла Т '.

  • 1. Нехай d лежить в площині трикутника ai & ici. Сумісний аффіннимі перетвореннями точки ai, b і з с відповідно точками а ', 6' й d . Точка, в яку перейде d при цьому перетворенні, і є d !.
  • 2. Нехай d лежить поза площиною трикутника аЬС.

Нехай хоча б одна з трійок cdie і С2 ^ 2 е 2 - трикутник. Тоді (( a? IC) {a 2 b 2 C 2 ) (cied) {c 2 e 2 d 2 )) - правильна четвірка. Побудуємо по S і S 2 прямі Ь і L 2 на них як було описано вище. Аффіннимі перетвореннями зображення 5i сумісний точки ai, 61 і С з точками відповідно а ', 6' й з '. Пряму, в яку перетворюється Li, позначимо через V. Нехай, для визначеності, С2 ^ 2 е 2 - трикутник. 5г афінних перетворень зображення (з прямою L 2 ) сумісний Z / 2 з V і точку е 2 з точкою е '. Точка, в яку перейде при цьому d 2 > є d '.

Нехай тепер і cde 1 і сг ^ ег - НЕ трикутники. Можливі дві ситуації.

2а). Точки с, d і е в тілі Т лежать на одній прямій. На S і

це проявляється тим, що в кожній з четвірок ai, ci, е, d і ci, ei, rfi точки лежать в одній площині. У свою чергу, точки aj, ci, ei і d лежать в одній площині, якщо при aiciei і а 2 з 2 е 2 - трикутниках 5i (ai, ci, ei, di) »5г (А2, С2, е2, з ^ ) - Якщо ж, наприклад, aiciei - чи не трикутник (тобто напрямок проекції а * паралельно площині грані асі, то всі чотири точки ai, ci, ei, d повинні лежати на одній прямій. Аналогічно визначається приналежність одній площині і точок ьІ сі ei і d.

Аффінним перетворенням зображення 5i поєднуємо точки ci і ei з точками з 'і е'. Точка, в яку переходить d, є d '.

  • 26). Точки с, d і е в тілі Т утворюють грань, і напрямки Qi і з * 2 обидва паралельні цієї межі. Якщо точка d лежить на одній прямій з точками а і е або 6 і е, то побудова d! зводиться до пункту 2а. Якщо ade і bde межі, то, наприклад, четвірка
  • ((ai & iCi) (a 2 & 2 C2) (aiei6! зводиться до початку пункту 2.

Опис процедури завершено.

вправи

  • 1.1. Чи існує лінійний по складності правильний код для безлічі геометричних перетворень Г 2 ?
  • 1.2. Нехай Ма - функція нумерації зображення А, Л = п,

Чи буде код <МД, 7а> правильним для безлічі перетворень Г 2 ?

  • 1.3. Чи буде правильним для безлічі перетворень Гз код, отриманий з коду, описаного у вправі 1.2, розподілом кожного елемента на ri | 2 ?
  • 1.4. Нехай К а, К в - описані раніше коди зображень А і В. Оцінити зверху складність алгоритму, що з'ясовує еквівалентність цих зображень.
  • 1.5. Чи є афінно еквівалентними а) два ромба; б) два паралелограма; в) дві трапеції?
  • 1.6. Дано два трикутника А АВС і ААВС. Доведіть, що існує єдине Афінний перетворення, яке переводить точку А в А } В - в Bi, З - в С.
  • 1.7. Доведіть, що будь-який Афінний перетворення площині можна представити у вигляді композиції двох розтягувань і перетворення подібності.

1.8. Доведіть, що якщо Афінний перетворення ip переводить деяку окружність в себе, то

  • 1.9. На площині дано 3 вектора а, 6, с, причому аа + pb + 7с =
  • 0. Доведіть, що ці вектори аффінним перетворенням можна перевести в вектори однакової довжини тоді і тільки тоді, коли з відрізків з довжинами | а |, | /? |, | 7 | можна скласти трикутник.
  • 1.10. Нехай - взаємно однозначне відображення площині в себе. Припустимо, що воно має наступну властивість: якщо три точки лежать на одній прямій, то їх образи теж лежать на одній прямій. Доведіть, що тоді tp - Афінний перетворення.
  • 1.11. Придумайте правильний код для безлічі перетворень Г 4 , який має складність по порядку меншу, ніж складність коду К.
  • 1.12. Дан опуклий ЛГ-уголишк, де N <100, і безліч

А = {Лх ..... Дню} деяких точок цього багатокутника. Відомо, що всі N вершин TV-кутника належать множині А, і що ніякі 3 крапки не лежать па одній прямій, а ніякі 4 точки не лежать в двох паралельних прямих. Дозволяється задавати питання типу: чому дорівнює площа AAiBjCk ? Доведіть, що 300 питань досить, щоб з'ясувати, які точки є вершинами багатокутника, і щоб знайти площу багатокутника.

 
<<   ЗМІСТ   >>