Здравствуйте, sjukov, Вы писали:
S>Товарищи! Посоветуйте пожалуйста варианты разрешения — есть задача:
S>- На некоторой плоскости размещено N-е количество полигонов
S>- Имеется некоторая ограничивающая прямоугольная область на этой плоскости
S>Необходимо оптимальным способом определить какие из полигонов попадают в ограничивающую
S>область.
S>Желательно такой алгоритм чтобы для проверки на попадание в "окно" ограничивающей области
S>не использоался перебор всех граней каждого полигона.. а нечто наподобии. к примеру, bounding-rect'а
S>полигона. Важным критерием является скорость.
Ключевые слова:
kd-tree
или
spatial data structures
multidimensional search methods
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Товарищи! Посоветуйте пожалуйста варианты разрешения — есть задача:
— На некоторой плоскости размещено N-е количество полигонов
— Имеется некоторая ограничивающая прямоугольная область на этой плоскости
Необходимо оптимальным способом определить какие из полигонов попадают в ограничивающую
область.
Желательно такой алгоритм чтобы для проверки на попадание в "окно" ограничивающей области
не использоался перебор всех граней каждого полигона.. а нечто наподобии. к примеру, bounding-rect'а
полигона. Важным критерием является скорость.
Вообщем задача, в прицнипе, схожа с задачей D3DClipperа который просто отсекает невидимые объекты при отрисовки сцены..
в этом случае ограничивающая область это экран!
Спасибо!
... << RSDN@Home 1.1.4 stable SR1 rev. 568>>
Здравствуйте, What, Вы писали:
W>Здравствуйте, sjukov, Вы писали:
S>>Желательно такой алгоритм чтобы для проверки на попадание в "окно" ограничивающей области
S>>не использоался перебор всех граней каждого полигона.. а нечто наподобии. к примеру, bounding-rect'а
S>>полигона. Важным критерием является скорость.
W>Ключевые слова:
W>kd-tree
Супер!! Оно!!! Спасибо большое. Оказывается задача является довльно таки распрастранненой.
W>или
W>spatial data structures
W>multidimensional search methods... << RSDN@Home 1.1.4 stable SR1 rev. 568>>