Вороной се раздели

Даден е кодът за разделяне на 3D обект на части, базиран на метода за конструиране на полиедри на Вороной чрез обикаляне на лица.Дялът на Воронойна краен набор от точки (атоми) S на пространството е такъв дял, в който всяка област от този дял образува набор от точки, които са по-близо до един от атомите на набора S, отколкото до всеки друг атом от този набор. Резултатът от разделянето е полиедрата на Вороной. Може да се каже, чеполиедърът на Воронойе област от пространството, която е по-близо до един от атомите, отколкото до останалите [1]. Разглежда се проблемът за разделянето на пространството, ограничено от повърхността на 3D обект, наnчасти. За да се получи дял вътре в обекта,nточки (атоми) се определят, например, произволно. След това се използват идеите на метода за получаване на полиедъра на Вороной чрез обикаляне на лицата. В случай на пространство, ограничено от повърхността на 3D обект, резултатът от разделянето е части от обекта. Това са или части, ограничени от част от повърхността на обекта и разделителни равнини, или полиедър на Вороной, образуван от разделителни равнини. Пример за такова разделяне на сфера на 12 произволно разпределени атома е показано на фиг. 1.

Фиг. 1. Сфера, разделена на 12 части

Следният код беше използван за задаване на масива от атоми arrTms:

-- Радиус на сферата r = 50.0 nTms = 12 - Масив от атоми, използвани за изграждане на полиедри на Вороной arrTms = #() kr = 0.8 * r - Генератор на произволни числа семе 1.0 за k = 1 до nTms do ( x = случайно -kr kr y = ran dom -kr kr z = произволно -kr kr добавете arrTms [x, y, z] )

Постоянното зареждане на генератора на произволни числа гарантира, че при всяко изпълнение и постоянен брой атоми са еднаквирезултат. Всички атоми са вътре в сфера с радиус 0,8 *r, къдетоrе радиусът на сферата, която се разбива на парчета. Друг 3D обект също може да се използва като разделен обект. В този случай, за да генерирате разделящи се атоми, можете да използвате конструктора на система от частици Particle Cloud (облак от частици), давайки му препраткатаobкъм разделящия се обект като емитер, например:

nTms = 12 ob = teapot radius:40 -- Формиране на база на обект (formation:3) -- Използвайте Total (quantityMethod:1) -- За последващо формиране на масив от атоми, задайте viewPercent:100 pCld = pCloud emitter:ob formation:3 quantityMethod:1 \ total_number:nTms viewP ercent:100 pos:ob.Po s isHidden:true - Поставете координатите на частиците в масив от атоми arrTms = за i = 1 до nTms събира (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 обект

    Въз основа на горния метод за заобикаляне на лица, ние използваме следната схема за разделяне на обект (дадена е схема за изграждане на едно парче):