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

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

Причина в том, что у меня есть 2 миллиона из них, которые я отправляю в API, и я хочу знать, какие из них перекрываются, поэтому я могу уменьшить их, чтобы каждый ящик покрывал только уникальную область земли, поэтому нет двух ограничивающих прямоугольников покрыть тот же кусок геопространства.

Как бы вычислить его так, чтобы эти ограничивающие прямоугольники были покрыты их собственным уникальным пространством гео-земли?

Я пишу эту программу на C++ btw.

источник

2013-10-09 James Campbell

Как вы хотите обрабатывать перекрытия? –

Я знаю, что это не тот ответ, который вы ищете, но это может вас заинтересовать: http://en.wikipedia.org/wiki/Sweep_and_prune – Pol0nium

Я хочу, чтобы область ограничивающей рамки была покрыта другими более чем 50% (хотя этот процент может быть изменен), тогда он должен обрезать его. и, конечно, я нарисую изображение :) по краске для вас –

Я думаю, что эта задача сложнее, чем вы думаете.

Вам нужно будет разделить существующие ящики, пока не будет перекрываться, а затем удалите ящики, полностью содержащиеся в другом.

Вместо дает вам решение, что я рекомендую, чтобы проверить, если вы можете жить с:

1) снимите флажки, которые полностью содержатся в другом окне.
2) оставить (частично) перекрывающие коробки, как они есть.

Для 2 миллионов вам нужен пространственный указатель (QuadTree), чтобы получить список всех ящиков рядом с одной коробкой.

Если вам нужно избегать перекрытий, то вы должны продолжать думать, что должно быть результатом?
A) Объединение перекрывающихся прямоугольников, которые не являются прямоугольником, а многоугольник.
или B) В результате должны быть прямоугольники.

источник

2013-10-10 16:34:56 AlexWien

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

Это звучит прекрасно, вы можете часто сэкономить много денег, если вы пройдете простой, но достаточный путь. – AlexWien

Вы можете проверить, находится ли X% вершин окна внутри другого поля, чтобы найти перекрытие, но я полагаю, что это не оптимальное решение.

источник

2013-10-10 08:37:52 stan0

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

ответ

Смежные вопросы