У меня есть большой список ограничивающих рамок, как я могу рассчитать дубликаты?
У меня есть список ограничивающих рамок, мне было интересно, как я могу рассчитать, какие из них были избыточными / дубликатами.
Причина в том, что у меня есть 2 миллиона из них, которые я отправляю в API, и я хочу знать, какие из них перекрывают другие, чтобы я мог уменьшить их, чтобы каждый прямоугольник покрывал только уникальную область земли, поэтому никакие два ограничивающих прямоугольника не покрывают один и тот же фрагмент геопространства.
Как бы я рассчитал это так, чтобы эти ограничивающие рамки покрывали свое уникальное пространство геозоны?
Я пишу эту программу на C ++, кстати.
Решение
Я думаю, что эта задача сложнее, чем вы думаете.
Вам придется разделить существующие ящики, пока не будет перекрытия, а затем удалить ящики, полностью содержащиеся в другом.
Вместо того, чтобы дать вам решение, я рекомендую проверить, можете ли вы жить с:
1) удалите коробки, которые полностью содержатся в другой коробке.
2) оставить (частично) перекрывающиеся поля, как они есть.
Для 2 миллионов вам нужен пространственный индекс (QuadTree), чтобы получить список всех ящиков рядом с одним ящиком.
Если вам нужно избегать каких-либо совпадений, то вы должны продолжать думать, каким должен быть результат?
А) Объединение перекрывающихся прямоугольников, которое больше не является прямоугольником, а многоугольником.
или Б) Результатом должны быть прямоугольники.
Другие решения
Вы можете проверить, находятся ли X% вершин блока внутри другого блока, чтобы определить, перекрывается ли он, но я полагаю, что это не оптимальное решение.