Нахождение количества точек решетки внутри области

Учитывая набор точек на двумерной плоскости, как найти количество точек, лежащих на любом произвольном треугольнике или внутри него.
Один из способов — проверить все точки, лежат ли они внутри данного треугольника.
Но я читайте, что 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