Alixx
@Alixx

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

Есть большая область (полигон, 1000+- точек) сложной формы (как выпуклой, так и "впуклой") и массив точек (10-30). Для каждой точки требуется проверить её вхождение в полигон.
Реализация на PHP и, возможно, JS.

Алгоритмы я нашла ни один и ни два, но то просто алгоритмы без сравнения скорости, а чтобы провести собственные тесты, придётся каждый реализовать, что не то, чтобы быстро.

Может кто знает какой алгоритм лучше всего подойдёт для этих целей? Или же может есть альтернативные варианты реализации следующей затеи?
Описание затеи

Проект: игра.
Есть клиент (веб-страничка) и сервер (PHP). На клиенте карта с возможностью мышью рисовать маршрут движения (думаю сделать расстояние между двумя точками фиксированное, к примеру, 10 у.е.). На клиенте определить вхождение точки в область можно банально использовав SVG с полигоном нужной формы, но если алгоритм будет хорош, можно всё и на canvas сделать. На клиенте будет несколько областей, а на сервер будет отправляться точки и в какой области каждая точка.
Так вот, клиенту, естественно, верить нельзя, поэтому необходимо провалидировать каждую точку, а чтобы не проверять в какой именно области находится точка, я решила проверять находится ли точка в указанной области и если нет, то весь массив отбрасывать, как невалидный.

Валидация потребует в любом случае много ресурсов сервера, однако хотелось бы их снизить до минимума, поэтому и решила узнать, может кто знает что лучше делать в данной ситуации.
  • Вопрос задан
  • 312 просмотров
Решения вопроса 1
twobomb
@twobomb
Игра очень серьезная? Я в том плане что
клиенту, естественно, верить нельзя

Подумайте кому-то это вообще нахрен нужно будет, лазить разбираться в вашем коде и подменять запросы, я думаю никому, ну допустим всё серьезно.
Я бы начал с того что именно взял первый попавшийся алгоритм и реализовал бы его, в реале пока вы дождесь какого либо толкового ответа вы могли бы уже реализовать все алгоритмы и протестить.
Всего скорее скорости работы первого попавшегося алгоритма должно хватить, если у вас не сумасшедшая нагрузка и не нужно выполнять тысячи таких проверок ежесекундно.
Крч проверьте на первом попавшемся алгоритме и если не хватит скорости тогда приходите будем думать как оптимизировать.
P.S. Сделал "тестовый стенд" на js на канве

На моей машине 100тысяч полигонов проверяются на 0.4мс
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
MySQL Spatial Data, ST_Contains / ST_Within
Ответ написан
MANAB
@MANAB
Разрабатываю на C#: Web, Desktop, Gamedev
Ну из того, что я понял по описанию, я бы использовал Quad-tree для того, чтобы сгруппировать и точки и полигоны по областям. Минимальный уровень Qaud я бы делал таким, чтобы его размер был много меньше размера полигона, чтобы в случае пересечения полигоном Qaud-a он бы разбивался на 2 или несколько треугольников. Ну и далее сам алгоритм проверки: находим Qaud для точки (константная по времени операция, т.к. по позиции можно формулой определить), смотрим, есть ли в этом Qaud часть заданного полигона, проверяем, полностью ли эта часть содержится в Quad или нет., если полностью - все ок, если не полностью - делим на треугольники, образованные точками пересечения полигона и Quad-а и проверяем попадание точки в треугольник, принадлежащий полигону.
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы