Рис. 7. Поиск события, расположенного вточке максимально плотного скопле-
ния событий (
Σ
— сумма расстояний до
N
ближайших соседей)
несколько тысяч соседей. Для увеличения быстродействия значение
N
может быть искусственно занижено при некоторых характерных
распределениях шума второго вида в пространстве.
Для ускорения такого перебора применяют блочную (корзинную)
сортировку [14]. Число операций для нее близко к
K
·
const, осо-
бенно при большом числе корзин, внутри которых, в свою очередь,
ведется сортировка методом
вставки
[14]. Этот метод работает с по-
следовательно поступающими данными корзин и позволяет объеди-
нить корзины в непрерывный массив. Это позволяет сделать корзины
маленькими, увеличив их число (при использовании памяти того же
объема), и приблизить число необходимых операций к
K
·
const.
Ближайшие соседи шумовых событий, расположенных в областях
с малым числом точек, сами также расположены далеко от события,
расположенного в центре наиболее плотного их скопления. Данный
факт используется для оптимизации поиска события, расположенно-
го в центре наиболее плотного их скопления (события с минималь-
ной суммой расстояний до ближайших соседей). Если для некоторого
события сумма расстояний до ближайших соседей имеет значение,
значительно превосходящее значение, наименьшее из найденных на
данный момент, то в этом случае следует исключить из дальнейше-
го рассмотрения само событие и определенное число его ближайших
соседей (точные критерии нельзя привести в настоящей статье из-за
их крайней громоздкости). На рис. 8 показана работа алгоритма выше-
изложенной оптимизации. Как видно из рис. 7, 8, после рассмотрения
первых двух событий минимальная сумма расстояний
Σ
тн
принимает-
ся равной
Σ
2
(Σ
2
<
Σ
1
)
. На следующем шаге выясняется, что
Σ
3
на-
много больше
Σ
2
, поэтому
Σ
тн
не изменяется, а некоторые ближайшие
78 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 1
