Hope this will help many programmers looking for a code that will determine if a point falls within a polygon.
Original idea can be found at
http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/
This is MySQL version using stored functions:
DELIMITER //
CREATE FUNCTION minimum(x DECIMAL(18,15),y DECIMAL(18,15)) RETURNS DECIMAL(18,15) DETERMINISTIC
BEGIN
DECLARE result DECIMAL(18,15);
IF x<y THEN
SET result = x;
ELSE
SET result = y;
END IF;
RETURN result;
END;
//
CREATE FUNCTION maximum(x DECIMAL(18,15),y DECIMAL(18,15)) RETURNS DECIMAL(18,15) DETERMINISTIC
BEGIN
DECLARE result DECIMAL(18,15);
IF x>y THEN
SET result = x;
ELSE
SET result = y;
END IF;
RETURN result;
END;
//
CREATE FUNCTION point_inside_polygon(x DECIMAL(18,15),y DECIMAL(18,15),p TEXT) RETURNS INT(1) DETERMINISTIC
BEGIN
DECLARE counter INT DEFAULT 0;
DECLARE result INT(1) DEFAULT 0;
DECLARE n INT DEFAULT 0;
DECLARE str TEXT;
DECLARE str2 TEXT;
DECLARE pos INT;
DECLARE coords VARCHAR(50);
DECLARE coords_pos INT;
DECLARE px DECIMAL(18,15);
DECLARE py DECIMAL(18,15);
DECLARE p1x DECIMAL(18,15);
DECLARE p1y DECIMAL(18,15);
DECLARE p2x DECIMAL(18,15);
DECLARE p2y DECIMAL(18,15);
DECLARE m DECIMAL(18,15);
DECLARE i INT;
DECLARE j INT;
DECLARE modulus INT;
DECLARE xinters DECIMAL(18,15);
SET str = REPLACE(REPLACE(p,'POLYGON((',''),'))','');
SET str2 = CONCAT(str,',');
SET pos = INSTR(str,',');
SET coords = SUBSTRING(str,1,pos-1);
SET coords_pos = INSTR(coords,' ');
SET p1x = SUBSTRING(coords,1,coords_pos-1);
SET p1y = SUBSTRING(coords,coords_pos+1);
WHILE pos>0 DO
SET n = n + 1;
SET str = SUBSTRING(str,pos+1);
SET pos = INSTR(str,',');
END WHILE;
SET i = 0;
SET n = n + 1;
WHILE i<=n DO
SET modulus = i % n;
SET j = 0;
SET str = str2;
WHILE j<=modulus DO
SET j = j + 1;
SET pos = INSTR(str,',');
SET coords = SUBSTRING(str,1,pos-1);
SET coords_pos = INSTR(coords,' ');
SET px = SUBSTRING(coords,1,coords_pos-1);
SET py = SUBSTRING(coords,coords_pos+1);
SET str = SUBSTRING(str,pos+1);
END WHILE;
SET p2x = px;
SET p2y = py;
SET i = i + 1;
SELECT minimum(p1y,p2y) INTO m;
IF y>m THEN
SELECT maximum(p1y,p2y) INTO m;
IF y<=m THEN
SELECT maximum(p1x,p2x) INTO m;
IF x<=m THEN
IF p1y!=p2y THEN
SET xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x;
END IF;
IF p1x=p2x OR x<=xinters THEN
SET counter = counter + 1;
END IF;
END IF;
END IF;
END IF;
SET p1x = p2x;
SET p1y = p2y;
END WHILE;
IF counter%2!=0 THEN
SET result = 1;
END IF;
RETURN result;
END;
//
DELIMITER ;
-- usage example:
CREATE TABLE `polygons` (
`id` int(11) NOT NULL auto_increment,
`polygon_data` polygon NOT NULL,
PRIMARY KEY (`id`),
SPATIAL KEY `polygon_data` (`polygon_data`(32))
) ENGINE=MyISAM DEFAULT CHARSET=latin1;
SET @x = -79.12345678901234;
SET @y = 43.12345678901234;
SET @point = CONCAT('POINT(',@x,' ',@y,')');
SELECT id FROM polygons WHERE MBRContains(polygon_data,GeomFromText(@point)) AND point_inside_polygon(@x,@y,ASTEXT(polygon_data));
This code has not been tested properly but it seems to work for me.
The problem of the last function is obviously in the speed of execution as MySQL does not support array data type. I am aware that especially this part of my code can be optimized:
WHILE j<=modulus DO
SET j = j + 1;
SET pos = INSTR(str,',');
SET coords = SUBSTRING(str,1,pos-1);
SET coords_pos = INSTR(coords,' ');
SET px = SUBSTRING(coords,1,coords_pos-1);
SET py = SUBSTRING(coords,coords_pos+1);
SET str = SUBSTRING(str,pos+1);
END WHILE;
Somebody might want to come up with a version that optimizes the number of iterations or uses temporary tables instead of parsing strings repeatedly (sorry I have no time left for this). Please let me know of any faster version.
Edited 1 time(s). Last edit at 03/22/2008 11:41AM by Adam Smith.