Блог

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

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

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

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

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

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

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

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

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