Операция выполнена!
Закрыть
Хабы: Алгоритмы, Программирование, Проектирование и рефакторинг

Изначальной задачей являлось определение конкретной области 2-х мерного пространства, которой принадлежит произвольная заданная точка, при условии наличия некоторой коллекции таких областей. Каждая область определяется двумя точками: начальной – P0, и конечной – P1 (рисунок 1). Вопрос заключался в том, каким образом организовать хранение и навигацию по данной коллекции для минимизации издержек и повышения производительности. Дополнительным условием, немного упрощающим реализацию алгоритма, являлась однозначность соответствия точек и областей, иными словами – области не пересекаются.

Наивная реализация предполагает создание массива, по которому можно осуществить поиск через простой перебор областей до момента нахождения искомой. Более продвинутая реализация, позволяющая сэкономить вычислительные ресурсы, в свою очередь, может базироваться на концепции KD-деревьев, о чем и будет рассказано в данной статье.

Читать далее
Читайте также
НОВОСТИ

ПИШИТЕ

Техническая поддержка проекта ВсеТут

info@vsetut.pro