Краткая версия: учитывая два дерева kd, которые содержат похожие, но не идентичные наборы 2D-точек и могут не иметь одного и того же корня, можете ли вы использовать тот факт, что они оба являются деревьями, чтобы сопоставить точки в одном с ближайшими точками в другом с меньшим количеством шагов поиска, чем если бы вы искали узлы один за другим?
У нас есть общедоступный API, который отправляет геометрию (координаты широты и долготы в формате WKT, могут быть как точки, так и полигоны) клиентским приложениям, они вносят изменения и отправляют нам измененный WKT. В последнее время у нас возникла проблема, когда клиентское приложение проецирует и не проецирует все точки перед сохранением, что приводит к незначительному смещению всех точек из-за пределов математической точности с плавающей запятой, даже для точек, которые пользователь не собирался перемещать. . Предполагается, что клиент сохраняет копию исходных значений без изменений и обновляет только те точки, которые пользователь фактически переместил.
Очевидно, это должно быть исправлено в клиентском приложении. Но я хотел бы определить, когда это произойдет в будущем, чтобы мы могли «поймать» клиентов, которые это делают. Это может быть только эвристика, но если мы увидим, что 90% точек сдвинуты лишь на небольшую величину, мы можем зарегистрировать предупреждение. Если точки перемещаются более чем на крошечную величину, мы можем предположить, что пользователь намеревался переместить точку.
Усложняющим фактором является то, что клиент может сериализовать возвращаемые нам точки или вершины полигонов в порядке, отличном от того, в котором мы их отправляли, но при этом он может по-прежнему представлять ту же форму и быть действительным. Кроме того, пользователь может разбивать полигоны, а точки или вершины могут быть удалены или добавлены к данным. Если бы это были просто многоугольники, мы могли бы вращать списки вершин до тех пор, пока они не «совпадут», но, учитывая, что многоугольники можно редактировать, и что у нас также есть столько же данных, которые являются просто точками, а не полигонами, я думаю, что это упрощающее предположение просто рассматривать все данные как наборы точек с целью проверки.
Один алгоритм, который я придумал для этого, состоит в том, чтобы поместить один из наборов точек в дерево k-d для быстрого поиска, а затем найти ближайшего соседа каждой точки во втором наборе. Но я мог бы поместить их обоих в деревья k-d, и мне было интересно, есть ли быстрый алгоритм для сравнения двух деревьев k-d?
