Розбиття Вороного

Наводиться код розбиття 3D-об'єкта на частини, що ґрунтується на методі побудови багатогранників Вороного за допомогою обходу граней.Розбиття Вороногокінцевої множини точок (атомів) S простору – це таке розбиття, при якому кожна область цього розбиття утворює безліч точок, ближчих до одного з атомів множини S, ніж до будь-якого іншого атома цієї множини. Результатом розбиття є багатогранники Вороного. Можна сказати, щобагатогранник Вороного- це область простору, що знаходиться ближче до одного з атомів, ніж до інших [1]. Розглядається завдання розбиття простору, обмеженого поверхнею 3D-об'єкта, наnчастин. Для отримання розбиття всередині об'єкта задаються, наприклад, випадковим чином,nточок (атомів). Далі використовуються ідеї методу отримання багатогранника Вороного у вигляді обходу граней. У разі простору, обмеженого поверхнею 3D-об'єкта, результатом розбиття є частини об'єкта. Це частини, обмежені шматком поверхні об'єкта і площинами розбиття, або багатогранник Вороного, утворений площинами розбиття. Приклад такого розбиття сфери по 12 випадково заданих атомів наведено на рис. 1.

Мал. 1. Сфера, поділена на 12 частин

Для завдання масиву атомів arrTms використано наступний код:

-- Радіус сфери r = 50.0 nTms = 12 -- Масив атомів, якими будуються багатогранники Вороного arrTms = #() kr = 0.8 * r -- Затравка датчика випадкових чисел seed 1.0 for k = 1 to nTms do ( x = random -kr kr y = random -kr kr z = random -kr kr append arrTms [x, y, z] )

Постійна затравка датчика випадкових чисел забезпечує при кожному запуску і постійному числі атомів один і той жерезультат. Всі атоми знаходяться всередині сфери з радіусом 0.8 *r, деr- це радіус розбивається на частини сфери. В якості об'єкта розбиття може бути використаний і інший 3D-об'єкт. У цьому випадку для генерації атомів розбиття можна використати конструктор системи частинок Particle Cloud (хмара частинок), подавши йому як емітер посиланняobна об'єкт, що розбивається, наприклад:

nTms = 12 ob = teapot radius:40 -- Object-base formation (formation:3) -- Use Total (quantityMethod:1) -- Необхідно для подальшого формування масиву атомів задати viewPercent:100 pCld = pCloud emitter:ob formation:3 quantityMethod:1 \ total_number:nTms viewPercent:100 pos:ob.Pos isHidden:true -- Заносимо координати частинок в масив атомів arrTms = for i = 1 to nTms collect (particlePos pCld i)

Розбиття Вороного методом обходу граней

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

Де x, y, і z – це координати точки, що шукається, а коефіцієнтиAi,Bi,CiіDiзадають три площини Вороного між центральним атомомi0, котрим будується багатогранник Вороного, і трьома поточними атомами з його оточення. Через координати атомів коефіцієнти виражаються так:

Перед початком розрахунку складається список найближчих сусідів атома, з яких визначатиметься геометричні сусіди. Кількість сусідів у списку має дещо перевищувати максимально можливу кількість граней багатогранників Вороного. Список сортується за зростанням від центрального атома. Алгоритм (наведено в [1]).

Знайти першу грань багатогранникаВороного атомаi0. Перебираючи всі атоми системи, знаходимо атомi1, найближчий доi0. Площина P1 Вороного цих атомів є площиною, що утворює (дає ненульову грань багатогранника Вороного атомаi0). Площина перпендикулярна до відрізку, що з'єднує атомиi0іi1, і проходить через його центр. Точкаpперетину площини P1 з відрізком, що з'єднуєi0іi1(рис. 2), належить грані багатогранника Вороного.

Мал. 2. Початок пошуку першої грані багатогранника атома i0

Перебираючи всіх сусідів, знаходимо атомi2, площина Вороного P2 якого перетинає площину P1 по лінії P1P2, найближчої до вже відомої точкиp(рис. 3).

Мал. 3. Знайдено першу грань багатогранника атома i0

Знаходимо атомиi3іie, площини Вороного P3 і Pe яких перетинають лінію P1P2 у точках V1 і Ve, найближчих до точкиq(рис. 4), деq- це основа перпендикуляра з точкиpдо лінії P1P2.

Мал. 4. Знайдено дві вершини V1 та Ve першої грані багатогранника атома i0

Точки V1 і Ve є вершинами багатогранника, що шукається. Перебираючи сусідів, що залишилися, знаходимо атомi4, площина Вороного P4 якого перетинає пряму P1P3 у точці V2, найближчій до вершини і V1 (рис. 5).

Мал. 5. Знайдено чергову вершину першої грані багатогранника атома i0

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

Першу межу багатогранника Вороного атомаi0знайдено. Крім того, відомі атоми, що дають суміжні з нею грані. Для знаходження наступних граней використовуємо, що кожен виявлений при обході атом дає свою ненульовугрань багатогранника атомаi0. Для кожної з них є інформація, що дозволяє розпочати побудову грані. Так, площина P4 містить вершини V2 та V3, що визначають ребро на лінії P1P4, що проходить у цій площині, а також ліній P4P3 та P4P5 (див. рис. 5). Почавши обхід з однієї з цих вершин, слідуючи процедурі кроку 4, ми прийдемо до іншої вершини, визначивши тим самим грань на площині P4. При обході цієї грані виявляться нові атоми, дають чергові грані шуканому багатограннику. Вичерпавши всі площини, ми отримаємо багатогранник Вороного.

Код розбиття 3D-об'єкта

Спираючись на наведений вище метод обходу граней, використовуємо наступну схему розбиття об'єкта (наводиться схема побудови одного шматка):

---