Намиране на брой точки на решетката вътре в област

Даден набор от точки в 2-D равнина, Как да намерите броя на точките, лежащи върху или вътре в произволен триъгълник.
Един от методите е да проверите всички точки дали лежат вътре в дадения триъгълник.
Но аз прочетете, че Kd-дървото може да се използва за намиране на броя на точките, лежащи в даден регион, за O(log n) време, където 'n' е броят на точките. Но не разбрах как да го приложа.
Има ли друг по-прост метод за това?
Или kd-tree ще работи? Ако е така, може ли някой да обясни как?


computational-geometry kdtree
person sabari    schedule 04.02.2013    source източник
comment
PS: Това не е домашно!   -  person sabari    schedule 04.02.2013
comment
Хм, най-лошият случай трябва да е O(n) (защото най-лошият случай е, че всички точки лежат вътре в триъгълника)!   -  person Oliver Charlesworth    schedule 04.02.2013
comment
Не искам да изброявам всички точки вътре в триъгълника. Просто трябва да преброя. Така че с подходяща структура на данните предполагам, че броенето може да бъде постигнато за O(log n) време.   -  person sabari    schedule 04.02.2013

Отговори (1)


arrow_upward
1
arrow_downward

Може да се направи чрез рекурсивна проверка на позицията на подразделенията към триъгълник. За да видите кои точки от възел на дърво са в триъгълник, проверете всеки дял на възел (има 2 в k-d дърво) дали е цял в триъгълник, извън триъгълник ли е или е пресичащ се триъгълник. Ако дялът е в триъгълник, добавете брой точки в този дял към резултата, ако дялът е извън триъгълника, не правете нищо за този дял, ако дялът пресича триъгълник, направете същата проверка за подразделения на този дял.

За тази цел всеки възел на дърво трябва да съхранява брой точки в своето поддърво, което е лесно да се направи при създаване на дърво.

Времето на работа зависи от броя на пресичанията на ръбове на триъгълник с граници на дял. Не съм сигурен дали е O(log n) в най-лошия случай.

person Ante    schedule 04.02.2013