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

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

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

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

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

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

Подскажите, пожалуйста, более правильный и лучший алгоритм для этого?
  • Вопрос задан
  • 159 просмотров
Пригласить эксперта
Ответы на вопрос 3
Stalker_RED
@Stalker_RED
Для задачи кластеризации существуют готовые решения.
В виде библиотек в том числе.

Вероятно вам даже подойдут алгоритмы группировки.
Ответ написан
xmoonlight
@xmoonlight
https://sitecoder.blogspot.com
Берём все Y-ки всех точек и находим минимальное и максимальное расстояние.
Берём среднее, и выравниваем сетку строк по высоте так, чтобы точки были как можно ближе к центру строк.
Тоже самое, делаем со столбцами.
Ответ написан
@mayton2019
Ent. Software engineer. Oracle. SQL. BigData.
Я бы предложил 2 шага.
1) построить гистограмму для всех X,Y координат раздельно. Выбрать локальные минимумы. Это будут линии таблицы. Но не точно.

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы