В компютърната геометрия известен проблем за определяне на точка от границата на полигона. В самолета, тъй като полигон и точка. Необходими за решаване на въпроса дали точката на многоъгълника.

В многоъгълник може да бъде изпъкнала. и не-изпъкнала. Обикновено се приема, че полигонът е проста, това е, без самостоятелно кръстовища, но проблемът се счита за не-прости многоъгълници. В последния случай, различни начини за определяне на членовете на полигона могат да доведат до различни резултати. Разграничаване алгоритъм, без предварителна обработка и алгоритми с предварително третиране, по време на което създава някои структури от данни, които позволяват по-бързо в бъдеще, за да се отговори на многобройните искания за доставки до едно и също многоъгълника.

метод за проследяване лъч [редактиране | редактиране уики текст]

Отчитане на броя на контролно-пропускателни пунктове [редактиране | редактиране уики текст]

Методи работят по различен начин в продължение на самостоятелно пресичащи полигони в чужбина. Вляво: дори-странно правило. Дясно: различна от нула ликвидация правило.

Един от стандартните методи за определяне на точката принадлежи на произволен прост многоъгълник е както следва. Обръщаме лъч от дадена точка в произволна посока (например в положителната посока на хоризонталната ос), и се брои колко пъти лъч пресича краищата на многоъгълника. Това е достатъчно, за да ходим в една линия по ръбовете на полигона и ще определи дали лъчът пресича всеки ръб. Ако броят на кръстовища е странно, това е обявено, че точката е в рамките полигон е дори - отвън. Това се основава на простото наблюдение, че когато се движат по линията на пресичане с всяка граница точка последователно се появява вътре, от външната страна на многоъгълника. Алгоритъмът е известен под имена като брой преминаване (брой) алгоритъм или дори-странно правило.

Трудността на алгоритъм възниква в изродени случая, когато лъч преминава през връх на многоъгълника. Една от техниките за преодоляване на това е да се предположи, че такива върховете на многоъгълника се крият безкрайно по-горе (или долу) пряко греда, а оттам и на кръстовището всъщност не е така. [1] По този начин, пресичане на лъча с острието се отчита, когато един от краищата на ребрата се намира точно под лъча, а другият край - горе или почива върху гредата.

Алгоритъмът работи по време O (N) за N-гон.

скорост Счетоводни [редактиране | редактиране уики текст]

Кривата прави два оборота около точката.

Помислете за броя на оборотите, което прави, ориентирани граница на многоъгълник около дадена точка P. В алгебрични топология, този брой се нарича индекс точка по отношение на кривата. [2] Това може да бъде изчислено както следва. Както и преди, освобождаването на лъч Р в произволна посока и да обмислят ребрата, която преминава. Всяка пресичане определя броя на 1 или -1, в зависимост от това как лъч пресича ръб - в посока на часовниковата стрелка (вдясно) или обратно на часовниковата стрелка (дясно на ляво). Тези два случая могат да бъдат разграничени от знака на скаларен продукт между направляващата ребро и вектора перпендикулярна на посоката на вектора на лъча. [3] Сумата на получените стойности е базовата точка спрямо кривата. Сумата ще бъде положително или отрицателно, в зависимост от ориентацията на границата. Ако това не е нула, тогава можем да приемем, че точката е вътре полигон, или - отвън.

Такъв алгоритъм е известен като правилото е нула ликвидация. [3]

За прости многоъгълници, този метод работи също толкова добре като метод, основан на отчитане на броя на кръстовища. Разликата между тях е показано, когато се обмисля самостоятелно пресичащи полигони с граница.

методът на сумиране на ъгли [редактиране | редактиране уики текст]

Възможно е да се определи, че точка Р е вътре полигон върхове в V0 на. V1. Vn = V0. изчисляване на сумата от:

# X03D5; I = ARccOS # X2061; (Р V и # X2212; 1 # X22C5; P В и | Р V и # X2212; 1 | # X22C5; | P В и | ) S и п г (г д т (Р V и # X2212; 1 Р V и)). = \ ARccOS \ ляво (\ cdot PV_> | \ cdot | PV_ | >> \ вдясно) знак \ ляв (detPV _ \\ PV_ \ край> \ дясно)>.

Ние можем да докажем, че тази сума не е, че друг, тъй като броят намотка на точка P по отношение на границата на полигона до постоянен коефициент 2 # X03C0; , Следователно можем да приемем, че точката е извън границата на полигона, ако сумата е равна на нула (или достатъчно близо до него, ако се използва приблизителната аритметика). Въпреки това, този метод е много практично, тъй като изисква скъпи операции за изчисляване на всеки ръб (обратни тригонометрични функции, квадратни корени), и "най-лошите в света алгоритъм" е дори име за тази задача. [1]

К. Вайлер бе предложена практичен вариант на този метод, като се избягват скъпоструващи операции и приблизителни изчисления. [4] Доказано е, че сумата от ъглите може да бъде изчислена като се използва само точка операцията класифициране на многоъгълник в квадранта около точка P. Weiler алгоритъм и някои подобрения към него, са описани в [5].

Алгоритми С предварителна обработка [редактиране | редактиране уики текст]

Изпъкналите и звездни полигони [редактиране | редактиране уики текст]

Аксесоари точки на изпъкнала или звездна N -gon могат да се определят с помощта на двоичен търсене време O (влезте N), инвестицията на O (N) памет и O (N) време за предварителна обработка. [6]

Произволен полигон [редактиране | редактиране уики текст]

Проблемът на точка принадлежи на произволен прост многоъгълник може да се мисли като специален случай на проблема за локализиране на мястото, в планарна подразделение. За N-ъгълник, този проблем може да бъде решен по време O (влизане 2 N), използвайки вода (N) памет и O (N влизане N) време за предварителна обработка. [7]

Бележки [редактиране | редактиране уики текст]

Позоваването [редактиране | редактиране уики текст]

• Drug Е. М. Sheymos Раздел 2.2: Задачи точки локализация. // компютърна геометрия: Въведение. - Москва: Мир, 1989.

Позоваването [редактиране | редактиране уики текст]