Побудова паралельних прямих. Допустимі відрізки для побудови за допомогою циркуля та лінійки

В основі способів побудови паралельних прямих за допомогою різних інструментів є ознаки паралельності прямих.

Побудова паралельних прямих за допомогою циркуля та лінійки

Розглянемо принцип побудови паралельної прямої, що проходить через задану точку, за допомогою циркуля та лінійки.

Нехай дана пряма та деяка точка А, яка не належить даній прямій.

Необхідно побудувати пряму, що проходить через задану точку $А$ паралельно даній прямій.

На практиці часто потрібно побудувати дві або більше паралельних прямих без даної прямої точки. У такому випадку необхідно накреслити пряму довільно і відзначити будь-яку точку, яка не лежатиме на даній прямій.

Розглянемо етапи побудови паралельної прямої:

Насправді також застосовують метод побудови паралельних прямих з допомогою креслярського косинця і лінійки.

Побудова паралельних прямих за допомогою косинця та лінійки

Для побудови прямої, яка проходитиме через точку М паралельно даній прямій а, необхідно:

1. Кутник прикласти до прямої $а$ діагоналлю (дивіться малюнок), а до його більшого катету прикласти лінійку.
2. Пересунути косинець по лінійці доти, поки ця точка $М$ не опиниться на діагоналі косинця.
3. Провести через точку $М$ шукану пряму $b$.

Ми отримали пряму, що проходить через задану точку $М$, паралельну даній прямій $а$:

$a \parallel b$, тобто $M \in b$.

Паралельність прямих $а$ і $b$ видно з рівності відповідних кутів, які позначені малюнку буквами $\alpha$ і $\beta$.

Побудова паралельної прямої, що віддалена на задану відстань від даної прямої

У разі необхідності побудови прямої, паралельної заданої прямої та віддаленої від неї на заданій відстані можна скористатися лінійкою та косинцем.

Нехай дана пряма $MN$ та відстань $а$.

1. Зазначимо на заданій прямій $MN$ довільну точку та назвемо її $В$.
2. Через точку $В$ проведемо пряму, перпендикулярну до прямої $MN$, і назвемо її $АВ$.
3. На прямій $АВ$ від точки $В$ відкладемо відрізок $ВС=а$.
4. За допомогою косинця та лінійки проведемо пряму $CD$ через точку $С$, яка і буде паралельною заданою прямою $АВ$.

Якщо відкласти на прямий $АВ$ від точки $В$ відрізок $ВС=а$ в іншу сторону, то отримаємо ще одну паралельну пряму до заданої, що віддалена від неї на задану відстань $а$.

Інші способи побудови паралельних прямих

Ще одним способом побудови паралельних прямих є побудова за допомогою рейсшини. Найчастіше цей спосіб використовують у креслярській практиці.

При виконанні столярних робіт для розмітки та побудови паралельних прямих використовується спеціальний креслярський інструмент – малка – дві дерев'яні планки, які скріплюються шарніром.

Відома з античних часів.

У завдання на побудову можливі такі операції:

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

Простий приклад

Завдання.За допомогою циркуля та лінійки розбити цей відрізок ABна дві рівні частини. Одне з рішень показано малюнку:

• Циркулем проводимо коло з центром у точці Aрадіусом AB.
• Проводимо коло з центром у точці Bрадіусом AB.
• Знаходимо точки перетину Pі Qдвох побудованих кіл.
• Лінійкою проводимо відрізок, що з'єднує точки Pі Q.
• Знаходимо точку перетину ABі PQ. Це - шукана середина відрізка AB.

Правильні багатокутники

Античним геометрам були відомі способи побудови правильних для n=2^k\,\!, 3\cdot 2^k, 5\cdot 2^kі 3\cdot5\cdot2^k.

Нерозв'язні завдання

Наступні три завдання на побудову було поставлено ще в античності:

• - Розбити довільний кут на три рівні частини.
• - побудувати відрізок, що є ребром куба вдвічі більшого обсягу, ніж куб із ребром.
• - Побудувати квадрат, рівний за площею даному колу.

Побудови одним циркулем та однією лінійкою

За теоремою Мора-Маскероні (Mohr–Mascheroni theorem) за допомогою одного циркуля можна побудувати будь-яку фігуру, яку можна побудувати циркулем та лінійкою. У цьому пряма вважається побудованою, якщо у ній задані дві точки.

Легко помітити, що за допомогою однієї лінійки можна проводити тільки проектно-інваріантні побудови (див., наприклад, теорії поверхонь ).

Зокрема, неможливо навіть розбити відрізок на рівні частини. Але за наявності на площині заздалегідь проведеного кола з зазначеним центром за допомогою лінійки можна провести ті ж побудови, що і циркулем і лінійкою ( теорема Понселе-Штейнера (Poncelet-Steiner theorem), .

Див. також

• - програма, що дозволяє робити побудови за допомогою циркуля та лінійки.

Література

• А. Адлер. Теорія геометричних побудов,Переклад з німецької Г. М. Фіхтенгольця. Видання третє. Л., Учпедгіз, 1940 – 232 с.
• І. І. Александров, Збірник геометричних завдань на побудову,Видання вісімнадцяте, М., Учпедгіз, 1950 – 176 с.
• Б. І. Аргунов, М Б Балк. Геометричні побудови на площині,Допомога для студентів педагогічних інститутів. Видання друге. М., Учпедгіз, 1957 – 268 с.
• А. М. Воронець. Геометрія циркуля,Популярна бібліотека з математики за загальною редакцією Л.А.Люстерника, М.- Л., ОНТІ, 1934 - 40 с.
• Ю. І. Манін, Про розв'язність задач на побудову за допомогою циркуля та лінійки,Енциклопедія елементарної математики книга четверта (геометрія), М., Фізматгіз, 1963. - 568с.
• Ю. Петерсен. Методи та теорії вирішення геометричних задач на побудову,Москва, друкарня Е. Лісснера та Ю. Романа, 1892 - VIII + 114с.
• В. В. Прасолов Три класичні завдання на побудову. Подвоєння куба, трисекція кута, квадратура кола,М: Наука, 1992. 80 с. Серія Популярні лекції з математики, випуск 62
• Я. Штейнер, Геометричні побудови, що виконуються за допомогою прямої лінії та нерухомого кола,М., Учпедгіз, 1939 – 80 с.

Ця стаття написана за матеріалами одного з розділів книги Седжвіка, Уейна та Дондеро "Програмування мовою Python", що вже згадувалося раніше. Називається цей розділ "Системи ітераційних функцій", і в ньому описано побудову різних зображень, таких як трикутник Серпіньського, папороть Барнслі та деяких інших, за допомогою досить нескладного алгоритму, який ще й з легкістю реалізується.

Почну з опису даного алгоритму. Я використатиму математичну термінологію, в тому числі, і ту, яку автори книги, в ході своєї розповіді, не задіють. Суто математичний погляд на алгоритми полегшує мені їхнє розуміння, та й викладати їх за допомогою математичної мови мені досить зручно.

Тож для розуміння теоретичної частини статті читачеві знадобляться знання деяких розділів математики, які зазвичай читаються у технічних вузах. Зокрема, незайвим буде знайомство з теорією ймовірностей та елементами математичного аналізу.

За теоретичною частиною статті слідуватиме практична, що описує реалізацію алгоритму мовою C99. Оскільки результатами роботи програми будуть зображення, ми будемо використовувати в програмі графічну бібліотеку pgraph, припускаючи, що читач, хоча б загалом, з нею знайомий.

Отже, переходимо до теоретичної частини нашої оповіді.

Ітераційні функції та випадкові послідовності

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

Задамо 2 послідовності, x n n = 1 ∞ та y n n = 1 ∞ , за допомогою наступних рекурентних формул:

X n = f x n - 1 , y n - 1 , n ∈ ℕ , y n = g x n - 1 , y n - 1 , n ∈ ℕ .

Пояснимо, що x 0 та y 0 - це деякі заздалегідь задані числа, а f(x, y) та g(x, y) - це деякі функції двох змінних, звані ітераційними. Сам процес обчислення чергового члена тієї чи іншої послідовності через такі функції називатимемо ітераціями, а наведений вище набір рекурентних формул - ітераційною схемою.

Рекурсивний спосіб завдання послідовностей, швидше за все, добре знайомий читачеві, якщо він вивчав математику у вузі. Дещо незвичайним може здатися "перехресний" спосіб обчислення членів послідовностей, при якому для обчислення n-го члена кожної з двох послідовностей потрібний не тільки n− 1-й член тієї ж послідовності, а й n− 1-й член інший.

А тепер розглянемо схему побудови членів двох послідовностей, яка використовує не одну пару ітераційних функцій, а mпар. Кожна з цих функцій буде лінійною по обох змінних, а також міститиме адитивну константу. Більш конкретно, функції матимуть вигляд:

F k x , y = k + k + k + k g k x , y = d k x + e k y + h k , k = 0 , 1 , … , m - 1 .

Для кожного nпочинаючи з 1, буде випадковим чином вибиратися число від 0 до m− 1, та при обчисленні x nі y nу рекурентних формулах буде використовуватися пара ітераційних функцій, індекси яких дорівнюють даному випадковому числу. Зазначимо, що випадкові числа, " які " перед кожною ітерацією, нічого не винні бути равновероятными. Однак для різних кроків ймовірність появи конкретного фіксованого числа та сама.

Давайте тепер сформулюємо сказане суворою математичною мовою. Розглянемо послідовність дискретних незалежних у сукупності випадкових величин T n = 1 ∞ , розподілених по тому самому закону. А саме: кожна випадкова величина набуває значення 0, 1, …, m− 1 з відповідними ймовірностями p 0 , p 1 , …, p m-1 .

Тепер послідовності, x n n = 1 ∞ і y n n = 1 ∞ поставимо за допомогою наступної ітераційної схеми:

X n = f T n x n - 1 , y n - 1 , n ∈ ℕ , y n = g T n x n - 1 , y n - 1 , n ∈ ℕ .

Як і раніше, x 0 та y 0 – це деякі заздалегідь задані числа.

Таким чином, кожна з послідовностей є випадковою, тобто її члени – це випадкові величини. Однак, кожну з цих послідовностей можна "реалізувати", тобто обчислити всі її члени (зрозуміло, таких реалізацій буде дуже багато).

Поставимо головне питання даного розділу. А яке ж відношення зображення, яке ми збираємося будувати, мають до цієї пари випадкових послідовностей? Дуже просте. Побудуємо реалізацію цих двох послідовностей. Для кожного натурального nпару ( x n, y n) можна розглядати як координати точки, заданої в декартовій прямокутній системі координат на площині. Так ось, зображення, що відповідає деякій парі реалізованих послідовностей, є геометричним місцем всіх таких точок на площині.

Здавалося б, кожної реалізації пари послідовностей ми отримуватимемо своє зображення, відмінне від інших. Однак, як це не парадоксально, зображення щоразу будуть практично збігатися (тобто при побудові на комп'ютері будуть невиразні людським оком). А при відповідному доборі ітераційних функцій та законів розподілу випадкових величин, що беруть участь у формуванні членів послідовностей, можна створювати цікаві візерунки.

Додамо, що з побудові зображень на комп'ютері, зрозуміло, виконуватимемо лише кінцеве (але досить велике) число ітерацій.

Про генерацію псевдовипадкових чисел

При написанні програми ми зіткнемося з необхідністю генерувати псевдовипадкові числа, розподілені, взагалі кажучи, не рівномірно, а за наперед заданим законом. У той самий час, ми матимемо лише програмним генератором псевдовипадкових чисел, рівномірно розподілених на проміжку . Як із другого розподілу отримати перший?

Переведемо завдання до математичної площини. Нехай є безперервна випадкова величина U, Розподілена рівномірно на відрізку . Задамося метою побудувати дискретну випадкову величину Tяк функцію від U, таким чином, щоб Tприймала значення 0, 1, …, m− 1 з відповідними ймовірностями p 0 , p 1 , …, p m-1 .

Вирішити поставлене завдання дуже просто. Введемо на розгляд суми ймовірностей

Якщо верхня межа підсумовування iменше нижнього, то таку суму за визначенням вважатимемо рівною 0.

Твисловимо через Uнаступним чином:

T = 0 , якщо U ? s 0 , s 1 , 1 , якщо U ? s 1 , s 2 , 2 , якщо U ? s 2 , s 3 , … … … … … … , … … … … … … - 1 , якщо U ∈ s m - 1 , 1 .

Очевидно, випадкова величина Tрозподілено за необхідним нами законом. Зауважимо, що, по суті, Т- це номер проміжку, до якого потрапляє випадкова величина U(за умови, що проміжки ми нумеруємо числами від 0 до m− 1 у порядку зростання їх лівих кордонів).

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

А тепер можна переходити до написання програми.

Структура програми

Програма складається з файлу main.c та файлів, що утворюють графічну бібліотеку pgraph. Вміст файлу main.c починається з наступної директиви, що включає графічну бібліотеку:

Далі у файлі містяться описи глобальних константних змінних та константних масивів. За ними - визначення функцій get_random_value() та main(). Перша з них генерує псевдовипадкові числа, а друга виконує основну роботу з побудови зображень.

Глобальні константні змінні та константні масиви

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

Нижче наводяться описи даних констант та масивів.

• n – кількість ітерацій;
• w - ширина зображення у пікселях;
• h - висота зображення у пікселях;
• xc - абсциса початку нової системи координат у старій системі;
• yc - ордината початку нової системи координат у старій системі;
• l - довжина в пікселях відрізка, паралельного до однієї з осей координат, що має в новій системі координат одиничну довжину;
• m - кількість пар ітераційних функцій, тобто число m;
• s - одновимірний масив розміру m, що містить суми ймовірностей випадкових величин T n (k-й елемент масиву містить s k);
• f - двомірний масив, що складається з m f k(x, yk, 0), (k, 1), (k, 2) містять числа a k, b k, c kвідповідно, де 0 ≤ k ≤ m − 1);
• g - двомірний масив, що складається з m"рядок" і 3-х "стовпців", що містить константи, задіяні у функціях g k(x, y) (елементи масиву з індексами ( k, 0), (k, 1), (k, 2) містять числа d k, e k, h kвідповідно, де 0 ≤ k ≤ m − 1).

Усі змінні мають тип int, а базовим типом всіх масивів є double.

Пояснимо, що під "старою" системою координат мається на увазі та, яка визначена у бібліотеці pgraph. Побудови всіх зображень будуть вестись у новій системі, отриманій зі старої паралельним переносом (зрушення по осях абсцис та ординат рівні відповідно x cі y c) і "стисненням" в lразів. Таким чином, точка, що має в новій системі координати ( x, y), у старій буде мати координати ( x l + x c, y l + y c). Зайве, гадаю, пояснювати, що за зберігання чисел x c, y cі lвідповідальні константні змінні xc, yc та l відповідно.

Для зберігання чисел x 0 та y 0 змінні не виділяються, оскільки у всіх випадках побудови зображень як ці цифри беруться нулі.

Генерація псевдовипадкових чисел: функція get_random_value()

Функція get_random_value() при кожному зверненні до неї генерує ціле псевдовипадкове число в діапазоні від 0 до m− 1 відповідно до описаної раніше схеми. Ось код цієї функції:

Отримуємо за допомогою стандартної бібліотечної функції rand() псевдовипадкове число в діапазоні від 0 до значення макросу RAND_MAX , ділимо отриманий результат на це значення і привласнюємо приватне змінної r (стор. 3). Тепер у r зберігається число, що належить відрізку . Його приблизно можна вважати значенням випадкової величини, рівномірно розподіленої на цьому відрізку.

Пояснимо, що значення макросу RAND_MAX , у разі (т. е. у разі використання компілятора MinGW64 версії 4.9.2 для 64-бітних систем) дорівнює 32767.

Тепер, за допомогою лінійного пошуку, що діє цикл while , шукаємо індекс найбільшого елемента масиву s , що не перевищує значення r , збільшений на одиницю, і зберігаємо його в змінній c (див. стор 4-6). Зазначимо, що у разі, якщо значення r - нульове, цикл не виконується жодного разу, а змінна з зберігає одиничне значення (див. стор. 4).

Значення, яке повертається функцією, можна наближено розглядати як значення випадкової величини T, описаної у вищезгаданому розділі.

Генерація зображення: функція main()

А ось і код функції main():

Створюємо зображення із заданими розмірами (стор. 3). Виділяємо пам'ять під змінні xі y, у яких зберігатимуться поточні члени послідовностей, та ініціалізуємо їх нулями (стор. 4). Нагадаю, що як чисел x 0 та y 0 , що у обчисленні перших членів кожної з послідовностей, беруться нулі.

Обчислюємо у циклі for перші nчленів кожної послідовності (стор. 5-13). Отримуємо спочатку псевдовипадкове число і записуємо його в r (стор. 7). Далі обчислюємо поточні значення членів обох послідовностей, поміщаючи в тимчасові змінні x1 і y1 (стор. 8, 9). При обчисленні використовуємо константи, що фігурують в ітераційних функціях і зберігаються в масивах f і g. Вибір тієї чи іншої пари наборів коефіцієнтів (а значить, пари ітераційних функцій) залежить від значення r, що використовується як перші індекси елементів масивів, що беруть участь у обчисленнях.

Переписуємо обчислені поточні значення змінні x і y (стор. 10, 11). Координати точки, що містяться в цих змінних, переводимо в координати вихідної системи координат, округляємо до цілих і наносимо крапку з результуючими координатами зображення чорним кольором (стор. 12).

Після завершення циклу зберігаємо сформоване зображення у файлі "out.bmp" (стор. 14) і звільняємо пам'ять (стор. 15). У цьому робота функції завершується.

Побудова зображення трикутника Серпінського

Трикутник Серпіньського є безліч точок, одержуваного з усіх точок деякого вихідного рівностороннього трикутника наступним чином. Трикутник розбивається трьома середніми лініями на 4 трикутники, після чого "центральний" трикутник видаляється. Далі з кожним із трьох рівносторонніх трикутників, що залишилися, виконується та ж операція. Нарешті, те саме ми робимо з дев'ятьма рівносторонніми трикутниками.

Продовжуючи описані операції до нескінченності, видаляємо, зрештою, з вихідного трикутника нескінченне число рівносторонніх трикутників, сума площ яких дорівнює площі вихідного. Точки, що залишилися, утворюють лінію, звану трикутником Серпіньського, що відіграє важливу роль у теорії множин.

У книзі Седжвіка та інших авторів пропонується наступний спосіб побудови зображення трикутника Серпінського. Розглянемо 3 точки на площині, що є вершинами рівностороннього трикутника, наприклад, точки з координатами 0, 0, 0, 1, 1/2, 3/2 у прямокутній декартовій системі координат. Вибираємо навмання (з рівними ймовірностями) одну з трьох вершин трикутника і будуємо точку, що ділить відрізок, що з'єднує вершину з координатами 0, 0 і обрану навмання вершину навпіл. Це перша точка нашого зображення.

Наведений алгоритм можна укласти в описану раніше схему побудови зображень, що задіяла випадкові послідовності та ітераційні функції.

Нам потрібні 3 пари ітераційних функцій. Їхні індекси 0, 1, 2 повинні вибиратися з ймовірностями 1/3, 1/3, 1/3 відповідно. Самі ітераційні функції наведені нижче.

F 0 x , y = 1 / 2 x , g 0 x , y = 1 / 2 y , f 1 x , y = 1 / 2 x + 1 / 2 , g 1 x , y = 1 / 2 y , f 2 x, y = 1/2 x + 1/4, g 2 x, y = 1/2 y + 3/4.

Тепер давайте вставимо в нашу програму описи глобальних константних змінних та константних масивів, що відповідають даним ймовірностям та даним ітераційним функціям. Але для початку визначимо макрос TRIANGLE , помістивши файл main.с після інструкції #include наступну інструкцію

Після інструкції вставляємо у файл наступний код: