Оптимальный способ рассортировать точки в 2D по таблице?

Question

[Kalombyr]

Добрый день!
Есть множество координат точек в 2D пространстве, которые отдалённо напоминают таблицу/сетку.
Пример:


Нужно, грубо говоря, распределить точки по "таблице":


Количество строк и столбцов заранее не известна.

Сейчас делаю так: сортирую по координате X, пробегаюсь по массиву получившемуся - как только расстояние между соседними слишком велико (больше предполагаемой погрешности), считаю, что начинается новые столбец.
Потом в каждом "столбце" сортирую по Y.

Но в моём случае проблема в том, что заранее не известно сколько хотя бы примерно должно быть между столбцами, строками, их количество. Поэтому, иногда, получается, что точка оказывается в другом столбце.

Подскажите, пожалуйста, более правильный и лучший алгоритм для этого?

Comments

[twobomb]

А в одной ячейке может быть 2 и более точки?

[Kalombyr]

twobomb, гарантированно нет.

[twobomb]

Kalombyr, но могут быть ячейки без точек как я понял, и высота\ширина строк\столбцов условных может быть разной?

[Andrey Tsvetkov]

если ячейки могут быть пустыми и их размер никак не ограничен, то у данной задачи нет единственного правильного решения

[twobomb]

Ну первая мысль, алгоритм начинает свою работу сверху вниз слева направо, тоесть с левой верхней точки.
Изначально у нас есть список всех точек, убираем из списка левую верхнюю точку. Далее условно от это точки проводим так скажем угол обзора (на картинке оранжевые линии), находим все точки из списка которые попадают в этот угол обзора и берем ближайшую, исключаем эту точку из списка и опять от нее повторяем такой же алгоритм. Если точек в углу обзора не найдено или они слишком далеко опять ищем крайнюю левую верхнюю и списка и продолжаем строить такие цепочки( цепочки обозначены черными линиями), по итогу думаю не составит труда уже определить сколько строк (это количество цепочек), а кол-во столбов (это максимальное количество точек во всех цепочках). Ну тут стоит поиграться с углом и возможно еще с расстоянием, чтобы исключить варианты как на второй картинке. Для это стоит найти для каждой точки расстояние к ее ближайшей точке и взять среднее из всего этого и если расстояние при построении цепочки сильно отличается от этого среднего расстояния, то не учитывать такие точки...
Ну это так первая мысль, если посидеть я думаю можно что нибудь получше придумать.

[Wataru]

Kalombyr, У вас на картинке у ячеек разная высота в разных строках. Это проблемы рисунка, или вы допускаете такое решение?

Потом, в текущей постановке, если могут быть пустые ячейки, то можно просто взять очень-очень мелкую сетку. Тогда каждая точка точно будет в отдельной клетке. Нужно или ограничить их с низу, или выбрать критерии. Может вам нужна сетка с максимальной площадью ячейки, если они все одинаковые должны быть.

[Kalombyr]

twobomb, wataru, Да, высота/ширина столбцов может быть разной, как и необязательность присутствия в ней точки.
Andrey Tsvetkov, допускаю. Мне бы тогда направление, куда двигаться и какие алгоритмы смотреть.

[Kalombyr]

twobomb, спасибо, думаю в этом направлении.

[Wataru]

Kalombyr, Дак чем вас тогда не устраивает провести вертикальные и горизональные линии совсем рядом с каждой точкой? Чуть ниже и чуть выше?

[ComodoHacker]

Для хорошего алгоритма нужно представлять какими могут быть данные и какими не могут.

Откуда они берутся?

[Kalombyr]

wataru, тогда в строке и в столбце будет всего по одной точке, а такого уж точно быть не может. Поясню подробнее, зачем мне:

ComodoHacker, вообще эти "точки" я нахожу на изображении.
Изначально они располагаются строго по сетке с одинаковым расстоянием между строками и столбцами, но из-за искажений камеры, перспективы, фокуса, неточности определения имеем большие погрешности либо вовсе отсутствие какой-либо точки.

Всё делается, что бы потом сопоставить точкам идеальные точки и получить хорошую матрицу трансформации, с помощью OpenCV и findHomography().

Answer 1

[Stalker_RED]

Для задачи кластеризации существуют готовые решения.
В виде библиотек в том числе.

Вероятно вам даже подойдут алгоритмы группировки.

Answer 2

[xmoonlight]

Берём все Y-ки всех точек и находим минимальное и максимальное расстояние.
Берём среднее, и выравниваем сетку строк по высоте так, чтобы точки были как можно ближе к центру строк.
Тоже самое, делаем со столбцами.

Answer 3

[mayton2019]

Я бы предложил 2 шага.
1) построить гистограмму для всех X,Y координат раздельно. Выбрать локальные минимумы. Это будут линии таблицы. Но не точно.

2) дефекты клеток в которые попали по 2 точки можно поправить случайным образом двигая линии. Но чтоб случайность была эффективнее я бы предложил генетически алгоритм.