Кластеры точек для каждого типа формы можно хранить в простой структуре данных PointCl lister, содержащей поле num для числа точек в кластере и массив p[i] (см. приложение В). Для каждого класса форм разработан метод makeExtentPoints(Ро1 ntCluster& dust), он вызывается только один раз на этапе предварительной обработки для каждого объекта на сцене (см. упражнения).
14.9. Использование экстентов После того как мы построили кластер точек для базового объекта, нетрудно найти прямоугольный и сферический экстенты. Каждое поле прямоугольного экстента содержит самую большую или самую маленькую координату, обнаруженную в массиве точек кластерар[г]: left - minp[i]jc, top - maxp[i].y и т. д., так что все поля можно найти по точкам кластера внутри одного цикла. Для этой цели предназначена подпрограмма
void makeBoxExtent(PointCluster& clust.Cuboid& cub)принимающая кластер точек и генерирующая структуру данных класса Cuboid, которая затем записывается в объект (см. упражнения).
Создание сферического экстента лишь немного сложнее. За центр экстента принимается центроид кластера точек, поскольку это удобная центральная точка (центр тяжести кластера, см. раздел «Аффинные комбинации точек» главы 4). Для того чтобы найти центроид, нужно покомпонентно сложить все точки и разделить полученную сумму на число точек. Затем определяется радиус охватывающей сферы - как наибольшее расстояние от центра экстента до любой из точек кластера. На основе такого подхода нетрудно написать подпрограмму void makeSphereExtent (PointClusterS clust. SpherelnfoS sph) (см. упражнения).
Наконец, легко сформировать прямоугольный и сферический экстенты в мировых координатах: просто преобразуем каждую точку из кластера точек базового объекта, в результате чего получим кластер точек в мировых координатах, а затем для получения желаемых экстентов используем те же подпрограммы.
Практические упражнения 14.9.1. Оценка уровня ложных тревог На рис. 14.38, б показан силуэт конического цилиндра, заключенный в круг. Вычислите «степень пустоты» для различных удлинений и поворотов этого цилиндра внутри круга. Степень пустоты определяется по следующей формуле: