170
правок
Изменения
Новая страница: «{{ptready}} == Определение и построение == '''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структ...»
{{ptready}}
== Определение и построение ==
'''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике.
''Примечание: в книжке описывается двумерный вариант, и на лекциях, кажется, только он был, поэтому далее считается, что <tex>k = 2</tex>. Обобщение на большую размерность достаточно просто додумать при необходимости.''
Строится это дерево следующим образом: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее (раз считаем, что <tex>k = 2</tex>, то на следующем уровне вновь будем разбивать вертикальными прямыми).
''Замечание: проблемы могут возникнуть, если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим {{---}} не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbers, то есть сравнивая ещё и по другой (другим) координате. Не думаю, что об этом нужно много писать.''
Строить дерево будем рекурсивно с помощью функции <tex>BuildKdTree(P, Depth)</tex>, принимающей множество точек и глубину. В зависимости от остатка при делении на размерность (в нашем случае от чётности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод:
<code>
BuildKdTree(P, Depth)
//Input. A set of points P and the current depth Depth.
//Output. The root of a kd-tree storing P.
if P contains only one point
return a leaf storing this point
else if depth is even
Split P into two subsets <tex>P_1</tex> and <tex>P_2</tex> with a vertical line <tex>l</tex> through the median x-coordinate of the points in P
else
Split P into two subsets <tex>P_1</tex> and <tex>P_2</tex> with a horizontal line <tex>l</tex> through the median y-coordinate of the points in P.
<tex>V_{left}</tex> <- BuildKdTree(<tex>P_1</tex>, Depth + 1)
<tex>V_{right}</tex> <- BuildKdTree(<tex>P_2</tex>, Depth + 1)
Create a node v storing <tex>l</tex>, make <tex>V_{left}</tex> the left child of v, and make <tex>V_{right}</tex> the right child of v.
return v
</code>
== Ссылки ==
* ''van Kreveld, de Berg, Overmars, Cheong {{---}} Computational Geometry. Algorithms and Applications.'' Страница 99.
* [http://en.wikipedia.org/wiki/K-d_tree Английская Википедия]
* [http://ru.wikipedia.org/wiki/K-%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE Русская Википедия]
[[Категория: Вычислительная геометрия]]
== Определение и построение ==
'''K-d дерево''' (short for k-dimensional tree) {{---}} статическая структура данных для хранения точек в <tex>k</tex>-мерном пространстве. Позволяет отвечать на запрос, какие точки лежат в данном прямоугольнике.
''Примечание: в книжке описывается двумерный вариант, и на лекциях, кажется, только он был, поэтому далее считается, что <tex>k = 2</tex>. Обобщение на большую размерность достаточно просто додумать при необходимости.''
Строится это дерево следующим образом: разобьём все точки вертикальной прямой так, чтобы слева (нестрого) и справа (строго) от неё было примерно поровну точек (для этого посчитаем медиану первых координат). Получим подмножества для левого и правого ребёнка. Далее построим для этих подмножеств деревья, но разбивать будем уже не вертикальной, а горизонтальной прямой (для этого посчитаем медиану вторых координат). И так далее (раз считаем, что <tex>k = 2</tex>, то на следующем уровне вновь будем разбивать вертикальными прямыми).
''Замечание: проблемы могут возникнуть, если много точек имеют одинаковую координату, тогда разбить примерно поровну не получится (почти все точки будут лежать на медиане и попадут в левую часть). Лучший способ борьбы с этим {{---}} не вспоминать о данной проблеме совсем. Но вообще с этим борются, используя composite numbers, то есть сравнивая ещё и по другой (другим) координате. Не думаю, что об этом нужно много писать.''
Строить дерево будем рекурсивно с помощью функции <tex>BuildKdTree(P, Depth)</tex>, принимающей множество точек и глубину. В зависимости от остатка при делении на размерность (в нашем случае от чётности) сплитим множество на два подмножества и делаем рекурсивные вызовы. Для лучшего понимания приведём псевдокод:
<code>
BuildKdTree(P, Depth)
//Input. A set of points P and the current depth Depth.
//Output. The root of a kd-tree storing P.
if P contains only one point
return a leaf storing this point
else if depth is even
Split P into two subsets <tex>P_1</tex> and <tex>P_2</tex> with a vertical line <tex>l</tex> through the median x-coordinate of the points in P
else
Split P into two subsets <tex>P_1</tex> and <tex>P_2</tex> with a horizontal line <tex>l</tex> through the median y-coordinate of the points in P.
<tex>V_{left}</tex> <- BuildKdTree(<tex>P_1</tex>, Depth + 1)
<tex>V_{right}</tex> <- BuildKdTree(<tex>P_2</tex>, Depth + 1)
Create a node v storing <tex>l</tex>, make <tex>V_{left}</tex> the left child of v, and make <tex>V_{right}</tex> the right child of v.
return v
</code>
== Ссылки ==
* ''van Kreveld, de Berg, Overmars, Cheong {{---}} Computational Geometry. Algorithms and Applications.'' Страница 99.
* [http://en.wikipedia.org/wiki/K-d_tree Английская Википедия]
* [http://ru.wikipedia.org/wiki/K-%D0%BC%D0%B5%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE Русская Википедия]
[[Категория: Вычислительная геометрия]]
