У меня проблемы с выяснением того, что делает фрагмент кода ниже.Он взят из книги Генрика Ванна Дженсена «1001 * Реалистический синтез изображений с использованием фотонного картирования» .Я думаю, что он пытается сделать (или что я думаю, что он должен пытаться сделать, учитывая его место в коде), это вычислить медианный индекс в массиве между некоторым начальным и конечным индексом.
// inputs are an array, start and end indices that define a subset of the array
int median = 1;
while((4*median) <= (end-start+1))
median += median;
if ((3*median) <= (end - start + 1)) {
median += median;
median += start - 1;
} else
median = end - median + 1
Дляв более широком контексте, код взят из раздела, который строит структуру данных дерева kd, учитывая список трехмерных точек.На каждом рекурсивном этапе построения дерева kd медианная точка (относительно некоторого измерения) выбирается как корень нового дерева kd.
Я думаю, что этот код должен вычислять медианный индексмежду некоторым начальным и конечным индексом, но если я прав, я не могу понять, почему этот медианный индекс вычисляется таким странным образом.
Любая помощь или понимание будут оценены, спасибо!
Редактировать : Благодаря Вону Катону теперь я вижу, что таким способом необходимо вычислить медианный индекс.Первоначально я был озадачен тем, почему нельзя просто сделать (конец - начало) / 2 + начало.Цель этого кода - взять список точек и преобразовать его в полное сбалансированное kd-дерево, которое может быть сохранено в виде данных в виде кучи (все двоичное дерево в массиве).Вычисление медианного индекса наивным способом не обязательно даст вам дерево, которое вы можете сгладить в массив.
Теперь я не понимаю, как кто-то придумал это.Кто-нибудь может объяснить или направить меня в сторону дерривации?