На прошлом уроке я рассказал о том, как повысить контрастность изображения и как выделить на изображении особе точки. Затем мы попробовали работать с найденными особыми точками. В частности, превратили эти точки в список координат и попытались объединить близкие точки в одну, так как у нас получилось очень много точек рядом. В статье был предложен следующий алгоритм: при составлении списка, перед добавлением в список очередной точки проверять, находится ли она близко от последней, если да, то добавлять в тот же список, если нет, то начинать новый список. Только проблема в том, что обход точек был через развертку, и могло получиться так, что близкие точки попадают в разные списки. Поэтому объединение точек получилось «криво». Сегодня мы исправим этот недочет.
Для начала, почему мы вообще начали все эти хитрости с алгоритмом? Дело в том, что если решать задачу «в лоб», то время работы алгоритма у нас будет пропорционально квадрату размера списка. Собственно, давайте сначала проверим, насколько критично будет время работы алгоритма «в лоб» при разных ситуациях. И так, нам нужно перебрать все точки и сравнить их расстояния со всеми точками: