Fastest algorithm to determine if a point is inside a region?

Question

PHP

There is a large area (polygon, 1000+- points) of complex shape (both convex and "convex") and an array of points (10-30). For each point, it is required to check its entry into the polygon.
Implementation in PHP and possibly JS.

I found neither one nor two algorithms, but those are just algorithms without speed comparison, and in order to conduct your own tests, you will have to implement each one, which is not that fast.

Maybe someone knows what algorithm is best suited for these purposes? Or maybe there are alternative options for the implementation of the following undertaking?

Description of the idea

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

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

Answer 1

Is the game very serious? I mean that

The client cannot be trusted

Think about it, it’s generally necessary for someone to climb to understand your code and replace requests, I think no one, well, let’s say everything is serious.
I would start by taking the first algorithm that came across and implementing it, in real life, while you wait for some kind of sensible answer, you could already implement all the algorithms and test it.
Most likely, the speed of the first algorithm that comes across should be enough if you do not have a crazy load and do not need to perform thousands of such checks every second.
Krch check on the first algorithm that comes across and if there is not enough speed, then come and think about how to optimize.
PS Made a "test stand" on js on canvas

On my machine, 100 thousand polygons are checked for 0.4ms

Answer 2

MySQL Spatial Data, ST_Contains / ST_Within

Answer 3

Well, from what I understood from the description, I would use a Quad-tree to group both points and polygons by area. I would make the minimum level of Qaud such that its size is much smaller than the size of the polygon, so that if it is intersected by the polygon Qaud-a, it would be divided into 2 or more triangles. Well, then the verification algorithm itself: we find Qaud for a point (a time-constant operation, since it can be determined by a formula by a position), we look if this Qaud contains a part of a given polygon, we check whether this part is completely contained in Quad or not ., if completely - everything is OK, if not completely - we divide into triangles formed by the intersection points of the polygon and Quad and check if the point hits the triangle belonging to the polygon.