Эффективный способ проверить, если N количество (x, y) координат в K количество прямоугольников

Question

Есть ли эффективный способ проверить, находится ли N количество точек (x, y) внутри K числа прямоугольников?Сейчас я использую метод грубой силы и прохожу все точки и прямоугольники, но это занимает около 2 минут и 30 секунд с 200 000 точек и 44 прямоугольников.

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

1. Прямоугольники могут перекрываться в зависимости от характера маршрута.2. Точка должна быть только в ONE прямоугольников3. Если точка находится на краю прямоугольника, я бы хотел, чтобы она считалась как внутри прямоугольника (но если ее легче не считать, я не буду считать)4. Прямоугольники зависят от того, какую область я хочу найти вне маршрута.Обычно они имеют высоту 2 мили (1 милю в каждом направлении от точки) и расстояние от точки 1 до точки 2 в ширину.

Answer 1

Теоретически в лучшем случае вам придется перебирать все 200 000 точек - и в худшем случае вам придется проверять все эти точки по всем 44 прямоугольникам (что вы и делаете сейчас) ).

Поскольку вы знаете, что вам придется проходить все 200 000 точек, лучшее, что вы можете сделать, это попытаться не проверять все 44 прямоугольника.

Чтобы сделать это, вам нужно будет выполнить некоторые вычисления для прямоугольников, вы найдете два ближайших прямоугольника и сформируете больший прямоугольник, который охватывает оба из них (кластер, если хотите). Затем вы найдете следующий ближайший прямоугольник к прямоугольнику, который вы только что сформировали, из другого кластерного прямоугольника. Вы продолжаете делать это, пока не заключите все прямоугольники (в итоге у вас будет 43 кластерных прямоугольника).

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

Answer 2

Вот несколько возможных идей:

• Нечеткое совпадение - если ваши точки не должны быть на 100% точно помечены как находящиеся в определенном прямоугольнике, вы можете написать алгоритм, который делает«наилучшее предположение», которое более эффективно, но жертвует точностью на 100%
• Нечеткий сначала, точный после - дает приблизительный ответ быстро, возможно, просто путем вычисления расстояния между данной точкой и верхним левым угломпрямоугольника или центр круга.Это даст приблизительный ответ, который может быть не точным на 100%, но затем позволит вам асинхронно продолжить вычисление, уточнить его и через некоторое время обновить отображение с точными данными 100%
• Сгруппировать точки- когда точка, которую она создала, должна «зарегистрировать» себя в прямоугольнике, в основном предварительно вычисляя, находится ли точка в данном прямоугольнике, если вы можете.
• Предварительный расчет + кэш - и затемкэшировать список прямоугольников, в которые помещается конкретная точка, в самой точке.Тогда это становится простым поиском вместо необходимости пересчитывать его каждый раз
• Асинхронная загрузка - можете ли вы начать отображать ответы по мере их вычисления?Если на выполнение всей партии уходит 2,5 минуты, можете ли вы показать результаты в 1000-точечных блоках по мере их расчета?Таким образом, пользователь быстро начинает получать некоторую обратную связь, пока расчет завершает работу.На 2,5 минуты это 150 секунд.Если бы вы могли получать результаты в виде 1000-точечных кусков (примерно 1/200 данных за раз), вы могли бы обновлять карту точек один раз в секунду, получая результаты по мере их поступления.