Extend MySQL implementation of PiP Algorithm?

Question

I need to make a point in polygon MySQL query.

I already found these two great solutions:

http://forums.mysql.com/read.php?23,286574,286574

MySQL implementation of ray-casting Algorithm?

But these functions can only check if one point is inside a poly. I have a query where the PiP part should only be one part of the query and check for x points inside a polygon.

Something like this:

$points = list/array/whatever of points in language of favour

SELECT d.name
FROM data AS d
WHERE d.name LIKE %red%
// just bla bla

// how to do this ?
AND $points INSIDE d.polygon
AND myWithin( $points, d.polygo ) // or

UPDATE

I tried it with MBR functions like this:

SET @g1 = GeomFromText('Polygon((13.43971 52.55757,13.41293 52.49825,13.53378 52.49574, 13.43971 52.55757))');
SET @g2 = GeomFromText('Point(13.497834 52.540489)');
SELECT MBRContains(@g1,@g2);

G2 should NOT be inside G1 but MBR says it is.

What's wrong with [`MBRContains()`](http://dev.mysql.com/doc/en/functions-for-testing-spatial-relations-between-geometric-objects.html#function_mbrcontains)? — eggyal, Jan 16 '13 at 17:55
Did you check all the functions in the link @eggyal provided? — inhan, Jan 16 '13 at 18:20
I have read that MBR is not accurate enough, but diggin deeper now. — Mike, Jan 17 '13 at 12:02
MBR will not work as it works with boundig boxes. Detecting points inside a polygon will not be accurate. — Mike, Jan 17 '13 at 12:11
You will end up using procedural SQL, so why you don't use an imperative language to query the DB and perform the calculations you need? I don't see why SQL should do everything... Just asking. — gd1, Jan 17 '13 at 14:45
I did that at first and it works, but there are just too many locations i would end up inserting "result filtering" . If i manage to do it via SQL it would be only one operation working everywhere. — Mike, Jan 17 '13 at 14:53
i ended up prefiltering results server side like this: http://www.daniweb.com/web-development/php/threads/366489/point-lying-inside-the-polygon-or-not-in-google-map. Then i run my main query containing only results from the prefiltering. — Mike, Jan 18 '13 at 14:53

symcbean · Answer 1 · 2013-01-18T15:36:12.713

So really your question is how do you apply the same function to multiple values and return true only if all the call to the function return true. That's not very hard.

If it were me I'd put the points (and optionally polygons - not shown in example) into a table then write a MySQL function to apply the raycasting method to each point - returning false if any one interation returns false, then return true. In the example below I've assumed that the polygon is fetched from yourpolygon and identified by primary key, while points are indentified by a foreign key (using the function mywithin by zarun) :

 DECLARE FUNCTION allwithin(
     pointSetKey INT) 
 RETURNS INT(1)  
 BEGIN 

 DECLARE current POINT;

 DECLARE check CURSOR FOR SELECT p.point
     FROM yourpoints p
     WHERE p.set=pointSetKey;

 OPEN check;

 nextPoint: LOOP

    FETCH check INTO current;

    IF (0=mywithin(current, yourpolygon)) THEN
         RETURN 0;
    END IF;

 END LOOP;

 RETURN 1;

 END;

 INSERT INTO yourpoints (pointsetkey, point)
 VALUES (
      128,
      GeomFromText('Point(13.497834 52.540489)')
 ),
 (
      128,
      GeomFromText('Point(13.6 52.1)')
 ),
 ....
 ;

 SELECT allwithin(128
 , GeomFromText('Polygon((13.43971 52.55757,13.41293 52.49825,13.53378 52.49574, 13.43971 52.55757))')
 );

or...

 SELECT COUNT(*)
 FROM yourpoints p
 WHERE p.set=128
 AND mywithin(p.point
      , GeomFromText('Polygon((13.43971 52.55757,13.41293 52.49825,13.53378 52.49574, 13.43971 52.55757))')
      );

Will give you the number of points not inside the polygon (which is rather expensive when you only want to know if NONE of the points are outside).

On erflection this could be optimized a lot - but time forbids. — symcbean, Jan 18 '13 at 15:11

score 1 · Answer 2 · answered Jul 04 '13 at 12:59

what if you do

SET @g1 = GEOMFROMTEXT('Polygon((13.43971 52.55757,13.41293 52.49825,13.53378 52.49574, 13.43971 52.55757))');
SET @g2 = GEOMFROMTEXT('Point(13.497834 52.540489)');
SELECT  ST_Contains(@g1,@g2);

instead of MBRContains? As I understand MySQL spatial documentation. MBR* functions are Minimum-bounding-rectangle ones, so it shows you whether your point is within the minimum rectangle over your geometry, but not in the geometry itself (in case it is irregular polygon and the point is inside the MBR and not in the polygon)

score 0 · Answer 3 · answered Jul 13 '13 at 20:35

It seems to me as follows: you need to test whether multiple points are in a polygon. If all are, then so is their convex hull. Figure out their convex hull (basically: order them clock-wise or anti-clockwise), this creates a polygon. Now test whether the new polygon is inside d.polygon.

Extend MySQL implementation of PiP Algorithm?

3 Answers3