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

Question

[Alixx]

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

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

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

Описание затеи

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

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

Comments

[N]

Немного похоже на это:
Как выбрать зону яндекс.карт исходя из адреса юзера?
Только нужно абстрагироваться от "координат в отношении карт"...
P.S.: Там на PHP пример приводил...

[Сергей Соколов]

«большая область» – без самопересечений, без дырок?

[N]

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

область = полигон = многоугольник.

[Alixx]

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

Answer 1

[twobomb]

Игра очень серьезная? Я в том плане что

клиенту, естественно, верить нельзя

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

На моей машине 100тысяч полигонов проверяются на 0.4мс

Comments

[freeExec]

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

[Alixx]

twobomb

Крч проверьте на первом попавшемся алгоритме и если не хватит скорости тогда приходите будем думать как оптимизировать.

Алгоритмов действительно не мало) Как возможно с вами связаться?

[twobomb]

Alixx, Связаться :D? Мы уже связаны

[Alixx]

twobomb,

Сделал "тестовый стенд" на js на канве

Так это на клиенте, а проверка будет на сервере, на php. Если б на клиенте нужно было - вопроса бы такого и не возникло. Вопрос в том, как на сервере для каждого игрока проверять подряд каждую координату сравнивая с каждым полигоном?

[WbICHA]

Alixx, а какая разница где? Алгоритм на любом языке можно реализовать.

[twobomb]

Alixx, Да какая разница где это выполнять, хоть на вашем холодильнике, может на пхп это еще быстрее будет работать, вот пример перенес на php;

php code

<?php
$vertices = [];

class PVector{
	public $x;
	public $y;
	
    public function __construct( $x,  $y) {
        $this->x = $x;
        $this->y = $y;
    }
}

function generatePolygon($countPolyPoint = 1000){
	$vertices = [];
  $rad = 200;
  $cx = 200;
  $cy = 200;
  $pi2 = pi()*2;
  
  for($i = 0 ; $i < $countPolyPoint; $i++)
      array_push($vertices,new PVector(
          $cx + ($rad+ rand(0,100)) * cos($pi2* ($i/$countPolyPoint)) ,
          $cy + ($rad+ rand(0,100)) * sin($pi2* ($i/$countPolyPoint)) 
      ));	
      return $vertices;
}
  

function click($vertices,$x,$y){
	$start = microtime(true);
	echo polyPoint($vertices,$x,$y)?"Есть вхождение":"Нет входения";
	echo '  Время выполнения скрипта: '.(number_format((microtime(true) - $start)/1000,2,'.','') ).' мс.';
	echo "\n";
}

$vertices = generatePolygon();
click($vertices,0,0);
click($vertices,0,100);
click($vertices,100,100);
click($vertices,200,200);
click($vertices,500,500);

// POLYGON/POINT
function polyPoint($vertices,  $px, $py) {
  $collision = false;
  $next = 0;
  for ($current=0; $current<count($vertices); $current++) {
    $next = $current+1;
    if ($next == count($vertices)) $next = 0;
    $vc = $vertices[$current];    
    $vn = $vertices[$next];       
    if ((($vc->y >= $py && $vn->y < $py) || ($vc->y < $py && $vn->y >= $py)) &&
         ($px < ($vn->x-$vc->x)*($py-$vc->y) / ($vn->y-$vc->y)+$vc->x)) {
            $collision = !$collision;
    }
  }
  return $collision;
}


?>

Результат

Нет входения Время выполнения скрипта: 0.00 мс.
Есть вхождение Время выполнения скрипта: 0.00 мс.
Есть вхождение Время выполнения скрипта: 0.00 мс.
Есть вхождение Время выполнения скрипта: 0.00 мс.
Нет входения Время выполнения скрипта: 0.00 мс.

Answer 2

[Rsa97]

MySQL Spatial Data, ST_Contains / ST_Within

Comments

[Alixx]

Использую postgresql

[Сергей Горностаев]

Alixx, тогда PostGIS и тот же ответ.

Answer 3

[Виталий Качан]

Ну из того, что я понял по описанию, я бы использовал Quad-tree для того, чтобы сгруппировать и точки и полигоны по областям. Минимальный уровень Qaud я бы делал таким, чтобы его размер был много меньше размера полигона, чтобы в случае пересечения полигоном Qaud-a он бы разбивался на 2 или несколько треугольников. Ну и далее сам алгоритм проверки: находим Qaud для точки (константная по времени операция, т.к. по позиции можно формулой определить), смотрим, есть ли в этом Qaud часть заданного полигона, проверяем, полностью ли эта часть содержится в Quad или нет., если полностью - все ок, если не полностью - делим на треугольники, образованные точками пересечения полигона и Quad-а и проверяем попадание точки в треугольник, принадлежащий полигону.

Comments

[WbICHA]

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

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

[Alixx]

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