Малыхин СергейmaytonМалыхин Сергей, для данный способ не работает для вещественных координат
точек до тех пор пока мы не определимся с шагом сетки.

Вопрос определения этого шага пока остался за кадром.

При чем тут шаг?
точки сортируются по одной из координат после этого перебираются по очереди

http://blog.ivank.net/fortunes-algorithm-and-implementation.html описание и реализация
Просто демка так была показана как будто мы работаем с методом сеток
или чем-то численным. Надо было другое видео приаттачить где
хм... больше аналитики штоль.

ДохтаРmaytonДля целочисленной плоскости в диапазоне short можно весь универсум
проиндексировать. Каждому пикселу сопоставить ссылку на ближайший
объект точки.

Это нормальная цена решения?

Думаю что нет, потому что алгоритмика решения в такой постановке
не масштабируется на 3D.
Он одинаково хреново масштабируется или не-масштабируется для 2D и 3D.
Но прежде чем решать задачу старым дедовским научным методом
я обычно предлагаю тривиальные, хардкорные и табличные решения.

В дополнение к "сопоставить ссылку" - раскрасить многоугольники Вороного-Делоне
(от 1 до 256) каждый в свой цвет. В какой цвет попали - та и точка.

ДохтаР, это лучше чем хэш. Док. Это блджад O(1) без промахов.

ДохтаРПосчитай сколько в среднем вершин попадет фигуру одного цвета,
я думаю, что около 6-и, твоя раскраска стремится к О(n/6).

Вообще не понял суть твоего пассажа! Что куда стремиться?

Я предложил целочисленно - точное решение. Как раскрасил - так и будет.

И причём тут базист с хешами? Я про хеши вообще ничего не сказал.

ДохтаР, да никак не планирую. Я предложил тупой маргинальный табличный алгоритм.
С кучей ограничений на memory и разрядность цвета. Да и нет никакого цвета.
Просто метафора.

Но он (алгоритм) имеет место в нашей дискуссии как отправная точка для СРАВНЕНИЯ
алгоритмов. А если у тебя дискретное поле 10 на 10 и точек штук 20 - так это и будет самая
лучшая имплеметнация. Я гарантирую это (с)

Еще зависит от гистограммы. К примеру взять Quad-Tree.
При некоторых раскладах оно работает хуже простого
разбиения пространства на одинаковые сегменты. Тоесть
мы можем найти наихудший случай при котором дерево
теряет смысл и вырождается в "матрицу с уровнями".

МетодСложность построенияСложность поискакомментарииПолный перебор0o(n)Тривиально и долгоДиаграмма Вороного (триангуляция Делоне?)o(n) - o(n*ln(n))o(Sqrt(n))Построить можно только для двумерного случая, применим только для численных значенийОбход Змейкой by mayton0o(n)Быстрее но линейное время остаётся в формулеK-D деревостремится к o(n^2)o(h*ln(h)), где h~ln(n)алгоритм в википедии Дихотомический метод ДохтарА и Димы-Т??В обсужденииДиаграмма Вороного (триангуляция Делоне?) + раскраска Мейтонаo(n) - o(n*ln(n))o(1)Жрёт память. Целочисленные координаты. Зависит от разрядности координат. Зависит разрядности цвета 8/16/24/32.

Ребята. Док. Дима. Руслан. Саша.

Я думал о тестовых данных. И вот к чему пришёл. У нас есть минимум 5 измерений по классам алгоритмов.
Но у нас нет представления о том как наши 5 алгоритмов соотносятся с различными наборами входных
данных. Поэтому беру на себя обязательство нагенерировать наборы.

1) 1% равномерное заполнение (очень мало точек)
2) 3% равномерное заполнение (мало точек)
3) 50% шум (много точек)
4) Один кластер точек с ярко выраженным центром (по Гауссу). Трёхсигмовая зона - не выходит за пределы картинки.
5) Два кластера точек. Центры - разнесены на расстояние.
6) Три кластера точек (с неодинаковым количеством точек в кластерах). Распределение - аналогично п (4) и (5).
7) Точки с ярко-выраженной географической составляющей (линия берега).
8) Точки с ярко-выраженной исскусственной географией (линии домов, кварталов, дорог).

Для пунктов (4) (5) (6) количество точек я определю чуть позже. Главное требование - чтобы
в центре не было наложения точки на точку.

Пункты (7) и (8) я постараюсь взять из реальных фотоснимков местности.

Наборы будут сохранены в виде

1) Ч.Б картинок с размером 256x256 где точки - черный цвет.
2) В виде CSV-файлов с координатами.
Для простоты - целочисленными.

Итого - 8 файлов с картинками + 8 csv файлов.

Да. Если есть пожелания по добавлению новых наборов - пишите. Учту.