在多边形 PHP 中查找点
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5065039/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
提示：将鼠标放在中文语句上可以显示对应的英文。显示中英文
时间：2020-08-25 16:42:53 来源:igfitidea点击:
Find Point in polygon PHP
提问by shasi kanth
i have a typical question with the Geometric datatype of mysql, polygon.
我有一个关于 mysql，多边形的几何数据类型的典型问题。
I have the polygon data, in the form of an array of latitudes and longitudes, ex:
我有多边形数据，以纬度和经度数组的形式，例如：
[["x":37.628134, "y":-77.458334],
["x":37.629867, "y":-77.449021],
["x":37.62324, "y":-77.445416],
["x":37.622424, "y":-77.457819]]
And i have a point (Vertex) with coordinates of latitude and longitude, ex:
我有一个带有纬度和经度坐标的点（顶点），例如：
$location = new vertex($_GET["longitude"], $_GET["latitude"]);
Now i want to find whether this vertex (point) is inside the polygon. How can i do this in php ?
现在我想找出这个顶点（点）是否在多边形内。我怎样才能在 php 中做到这一点？
回答by Thariama
This is a function i converted from another language into PHP:
这是我从另一种语言转换为 PHP 的函数：
$vertices_x = array(37.628134, 37.629867, 37.62324, 37.622424); // x-coordinates of the vertices of the polygon
$vertices_y = array(-77.458334,-77.449021,-77.445416,-77.457819); // y-coordinates of the vertices of the polygon
$points_polygon = count($vertices_x) - 1; // number vertices - zero-based array
$longitude_x = $_GET["longitude"]; // x-coordinate of the point to test
$latitude_y = $_GET["latitude"]; // y-coordinate of the point to test
if (is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){
echo "Is in polygon!";
}
else echo "Is not in polygon";
function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)
{
$i = $j = $c = 0;
for ($i = 0, $j = $points_polygon ; $i < $points_polygon; $j = $i++) {
if ( (($vertices_y[$i] > $latitude_y != ($vertices_y[$j] > $latitude_y)) &&
($longitude_x < ($vertices_x[$j] - $vertices_x[$i]) * ($latitude_y - $vertices_y[$i]) / ($vertices_y[$j] - $vertices_y[$i]) + $vertices_x[$i]) ) )
$c = !$c;
}
return $c;
}
Additional:For more functions i advise you to use the polygon.php class available here.
Create the Class using your vertices and call the function isInsidewith your testpoint as input to have another function solving your problem.
附加：对于更多功能，我建议您使用这里可用的polygon.php 类。使用您的顶点创建类，并isInside使用您的测试点作为输入调用该函数，以使另一个函数解决您的问题。
回答by amh15
The popular answer above contains typos. Elsewhere, this code has been cleaned up. The corrected code is as follows:
上面的流行答案包含错别字。在其他地方，此代码已被清理。修正后的代码如下：
<?php
/**
From: http://www.daniweb.com/web-development/php/threads/366489
Also see http://en.wikipedia.org/wiki/Point_in_polygon
*/
$vertices_x = array(37.628134, 37.629867, 37.62324, 37.622424); // x-coordinates of the vertices of the polygon
$vertices_y = array(-77.458334,-77.449021,-77.445416,-77.457819); // y-coordinates of the vertices of the polygon
$points_polygon = count($vertices_x); // number vertices
$longitude_x = $_GET["longitude"]; // x-coordinate of the point to test
$latitude_y = $_GET["latitude"]; // y-coordinate of the point to test
//// For testing. This point lies inside the test polygon.
// $longitude_x = 37.62850;
// $latitude_y = -77.4499;
if (is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){
echo "Is in polygon!";
}
else echo "Is not in polygon";
function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)
{
$i = $j = $c = 0;
for ($i = 0, $j = $points_polygon-1 ; $i < $points_polygon; $j = $i++) {
if ( (($vertices_y[$i] > $latitude_y != ($vertices_y[$j] > $latitude_y)) &&
($longitude_x < ($vertices_x[$j] - $vertices_x[$i]) * ($latitude_y - $vertices_y[$i]) / ($vertices_y[$j] - $vertices_y[$i]) + $vertices_x[$i]) ) )
$c = !$c;
}
return $c;
}
?>
回答by Martin Joiner
If your polygons are self-closing, that is to say that it's final vertex is the line between it's last point and it's first point then you need to add a variable and a condition to your loop to deal with the final vertex. You also need to pass the number of vertices as being equal to the number of points.
如果您的多边形是自闭合的，也就是说它的最终顶点是它的最后一个点和它的第一个点之间的线，那么您需要在循环中添加一个变量和一个条件来处理最终顶点。您还需要传递顶点数等于点数。
Here is the accepted answer modified to deal with self-closing polygons:
这是为处理自闭合多边形而修改的公认答案：
$vertices_x = array(37.628134, 37.629867, 37.62324, 37.622424); // x-coordinates of the vertices of the polygon
$vertices_y = array(-77.458334,-77.449021,-77.445416,-77.457819); // y-coordinates of the vertices of the polygon
$points_polygon = count($vertices_x); // number vertices = number of points in a self-closing polygon
$longitude_x = $_GET["longitude"]; // x-coordinate of the point to test
$latitude_y = $_GET["latitude"]; // y-coordinate of the point to test
if (is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){
echo "Is in polygon!";
}
else echo "Is not in polygon";
function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)
{
$i = $j = $c = $point = 0;
for ($i = 0, $j = $points_polygon ; $i < $points_polygon; $j = $i++) {
$point = $i;
if( $point == $points_polygon )
$point = 0;
if ( (($vertices_y[$point] > $latitude_y != ($vertices_y[$j] > $latitude_y)) &&
($longitude_x < ($vertices_x[$j] - $vertices_x[$point]) * ($latitude_y - $vertices_y[$point]) / ($vertices_y[$j] - $vertices_y[$point]) + $vertices_x[$point]) ) )
$c = !$c;
}
return $c;
}
Thank you! I found this page and it's accepted answer very helpful and I am proud to offer this variation.
谢谢！我发现这个页面，它被接受的答案非常有帮助，我很自豪能提供这种变化。
回答by Renish Gotecha
Above solution is not working as i expect, instead of using the above solution you can prefer below solutions
上面的解决方案不像我期望的那样工作，而不是使用上面的解决方案，你可以更喜欢下面的解决方案
With PHP
function pointInPolygon($point, $polygon, $pointOnVertex = true) { $this->pointOnVertex = $pointOnVertex; // Transform string coordinates into arrays with x and y values $point = $this->pointStringToCoordinates($point); $vertices = array(); foreach ($polygon as $vertex) { $vertices[] = $this->pointStringToCoordinates($vertex); } // Check if the lat lng sits exactly on a vertex if ($this->pointOnVertex == true and $this->pointOnVertex($point, $vertices) == true) { return "vertex"; } // Check if the lat lng is inside the polygon or on the boundary $intersections = 0; $vertices_count = count($vertices); for ($i=1; $i < $vertices_count; $i++) { $vertex1 = $vertices[$i-1]; $vertex2 = $vertices[$i]; if ($vertex1['y'] == $vertex2['y'] and $vertex1['y'] == $point['y'] and $point['x'] > min($vertex1['x'], $vertex2['x']) and $point['x'] < max($vertex1['x'], $vertex2['x'])) { // Check if point is on an horizontal polygon boundary return "boundary"; } if ($point['y'] > min($vertex1['y'], $vertex2['y']) and $point['y'] <= max($vertex1['y'], $vertex2['y']) and $point['x'] <= max($vertex1['x'], $vertex2['x']) and $vertex1['y'] != $vertex2['y']) { $xinters = ($point['y'] - $vertex1['y']) * ($vertex2['x'] - $vertex1['x']) / ($vertex2['y'] - $vertex1['y']) + $vertex1['x']; if ($xinters == $point['x']) { // Check if lat lng is on the polygon boundary (other than horizontal) return "boundary"; } if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) { $intersections++; } } } // If the number of edges we passed through is odd, then it's in the polygon. if ($intersections % 2 != 0) { return "inside"; } else { return "outside"; } } function pointOnVertex($point, $vertices) { foreach($vertices as $vertex) { if ($point == $vertex) { return true; } } } function pointStringToCoordinates($pointString) { $coordinates = explode(" ", $pointString); return array("x" => $coordinates[0], "y" => $coordinates[1]); } // Function to check lat lng function check(){ $points = array("22.367582 70.711816", "21.43567582 72.5811816","22.367582117085913 70.71181669186944","22.275334996986643 70.88614147123701","22.36934302329968 70.77627818998701"); // Array of latlng which you want to find $polygon = array( "22.367582117085913 70.71181669186944", "22.225161442616514 70.65582486840117", "22.20736264867434 70.83229276390898", "22.18701840565626 70.9867880031668", "22.22452581029355 71.0918447658621", "22.382709129816103 70.98884793969023", "22.40112042636022 70.94078275414336", "22.411912121843205 70.7849142238699", "22.367582117085913 70.71181669186944" ); // The last lat lng must be the same as the first one's, to "close the loop" foreach($points as $key => $point) { echo "(Lat Lng) " . ($key+1) . " ($point): " . $this->pointInPolygon($point, $polygon) . "<br>"; } }With MySql
使用 PHP
function pointInPolygon($point, $polygon, $pointOnVertex = true) { $this->pointOnVertex = $pointOnVertex; // Transform string coordinates into arrays with x and y values $point = $this->pointStringToCoordinates($point); $vertices = array(); foreach ($polygon as $vertex) { $vertices[] = $this->pointStringToCoordinates($vertex); } // Check if the lat lng sits exactly on a vertex if ($this->pointOnVertex == true and $this->pointOnVertex($point, $vertices) == true) { return "vertex"; } // Check if the lat lng is inside the polygon or on the boundary $intersections = 0; $vertices_count = count($vertices); for ($i=1; $i < $vertices_count; $i++) { $vertex1 = $vertices[$i-1]; $vertex2 = $vertices[$i]; if ($vertex1['y'] == $vertex2['y'] and $vertex1['y'] == $point['y'] and $point['x'] > min($vertex1['x'], $vertex2['x']) and $point['x'] < max($vertex1['x'], $vertex2['x'])) { // Check if point is on an horizontal polygon boundary return "boundary"; } if ($point['y'] > min($vertex1['y'], $vertex2['y']) and $point['y'] <= max($vertex1['y'], $vertex2['y']) and $point['x'] <= max($vertex1['x'], $vertex2['x']) and $vertex1['y'] != $vertex2['y']) { $xinters = ($point['y'] - $vertex1['y']) * ($vertex2['x'] - $vertex1['x']) / ($vertex2['y'] - $vertex1['y']) + $vertex1['x']; if ($xinters == $point['x']) { // Check if lat lng is on the polygon boundary (other than horizontal) return "boundary"; } if ($vertex1['x'] == $vertex2['x'] || $point['x'] <= $xinters) { $intersections++; } } } // If the number of edges we passed through is odd, then it's in the polygon. if ($intersections % 2 != 0) { return "inside"; } else { return "outside"; } } function pointOnVertex($point, $vertices) { foreach($vertices as $vertex) { if ($point == $vertex) { return true; } } } function pointStringToCoordinates($pointString) { $coordinates = explode(" ", $pointString); return array("x" => $coordinates[0], "y" => $coordinates[1]); } // Function to check lat lng function check(){ $points = array("22.367582 70.711816", "21.43567582 72.5811816","22.367582117085913 70.71181669186944","22.275334996986643 70.88614147123701","22.36934302329968 70.77627818998701"); // Array of latlng which you want to find $polygon = array( "22.367582117085913 70.71181669186944", "22.225161442616514 70.65582486840117", "22.20736264867434 70.83229276390898", "22.18701840565626 70.9867880031668", "22.22452581029355 71.0918447658621", "22.382709129816103 70.98884793969023", "22.40112042636022 70.94078275414336", "22.411912121843205 70.7849142238699", "22.367582117085913 70.71181669186944" ); // The last lat lng must be the same as the first one's, to "close the loop" foreach($points as $key => $point) { echo "(Lat Lng) " . ($key+1) . " ($point): " . $this->pointInPolygon($point, $polygon) . "<br>"; } }使用 MySql
CREATE TABLE `TestPoly` ( `id` int(11) NOT NULL, `name` varchar(255) NOT NULL, `pol` polygon NOT NULL ) SET @g = 'POLYGON((22.367582117085913 70.71181669186944, 22.225161442616514 70.65582486840117, 22.20736264867434 70.83229276390898, 22.18701840565626 70.9867880031668, 22.22452581029355 71.0918447658621, 22.382709129816103 70.98884793969023, 22.40112042636022 70.94078275414336, 22.411912121843205 70.7849142238699, 22.367582117085913 70.71181669186944))'; INSERT INTO TestPoly (pol) VALUES (ST_GeomFromText(@g)) set @p = GeomFromText('POINT(22.4053386588057 70.86240663480157)'); select * FROM TestPoly where ST_Contains(pol, @p);
CREATE TABLE `TestPoly` ( `id` int(11) NOT NULL, `name` varchar(255) NOT NULL, `pol` polygon NOT NULL ) SET @g = 'POLYGON((22.367582117085913 70.71181669186944, 22.225161442616514 70.65582486840117, 22.20736264867434 70.83229276390898, 22.18701840565626 70.9867880031668, 22.22452581029355 71.0918447658621, 22.382709129816103 70.98884793969023, 22.40112042636022 70.94078275414336, 22.411912121843205 70.7849142238699, 22.367582117085913 70.71181669186944))'; INSERT INTO TestPoly (pol) VALUES (ST_GeomFromText(@g)) set @p = GeomFromText('POINT(22.4053386588057 70.86240663480157)'); select * FROM TestPoly where ST_Contains(pol, @p);
回答by awm
Here's a possible algorithm.
这是一个可能的算法。
- Define a new coordinate system with your point of interest at the center.
- In your new coordinate system, convert all of your polygon vertices into polar coordinates.
- Traverse the polygon, keeping track of the net change in angle, ?θ. Always use the smallest possible value for each change in angle.
- If, once you've traversed the polygon, your total ?θ is 0, then you're outside the polygon. On the other hand, if it's is ±2π, then you're inside.
- If, by chance ?θ>2π or ?θ<-2π, that means you have a polygon that doubles back on itself.
- 定义一个以您的兴趣点为中心的新坐标系。
- 在新坐标系中，将所有多边形顶点转换为极坐标。
- 遍历多边形，跟踪角度的净变化 ?θ。对于角度的每次变化，始终使用尽可能小的值。
- 如果，一旦你遍历了多边形，你的总 ?θ 是 0，那么你就在多边形之外。另一方面，如果它是±2π，那么你就在里面。
- 如果偶然 ?θ>2π 或 ?θ<-2π，这意味着你有一个多边形，它自身翻倍。
Writing the code is left as an exercise. :)
编写代码留作练习。:)
回答by user2455079
Updated code so i will be easier to use with google maps: It accept array like:
更新了代码，以便我更容易使用谷歌地图：它接受如下数组：
Array
(
[0] => stdClass Object
(
[lat] => 43.685927
[lng] => -79.745829
)
[1] => stdClass Object
(
[lat] => 43.686004
[lng] => -79.745954
)
[2] => stdClass Object
(
[lat] => 43.686429
[lng] => -79.746642
)
So it will be easier to use with google maps:
所以使用谷歌地图会更容易：
function is_in_polygon2($longitude_x, $latitude_y,$polygon)
{
$i = $j = $c = 0;
$points_polygon = count($polygon)-1;
for ($i = 0, $j = $points_polygon ; $i < $points_polygon; $j = $i++) {
if ( (($polygon[$i]->lat > $latitude_y != ($polygon[$j]->lat > $latitude_y)) &&
($longitude_x < ($polygon[$j]->lng - $polygon[$i]->lng) * ($latitude_y - $polygon[$i]->lat) / ($polygon[$j]->lat - $polygon[$i]->lat) + $polygon[$i]->lng) ) )
$c = !$c;
}
return $c;
}
回答by Renish Gotecha
I have created code in php codeigniter, in my controller i have create two functions like below
我在 php codeigniter 中创建了代码，在我的控制器中我创建了两个函数，如下所示
public function checkLatLng(){
$vertices_y = array(22.774,22.174,22.466,22.666,22.966,22.321); // x-coordinates of the vertices of the polygon (LATITUDES)
$vertices_x = array(70.190,70.090,77.118,77.618,77.418,77.757); // y-coordinates of the vertices of the polygon (LONGITUDES)
$points_polygon = count($vertices_x)-1;
$longitude_x = $this->input->get("longitude"); // Your Longitude
$latitude_y = $this->input->get("latitude"); // Your Latitude
if ($this->is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y)){
echo "Is in polygon!";
}
else
echo "Is not in polygon";
}
Another function for check the lat-lng is below
检查 lat-lng 的另一个功能如下
public function is_in_polygon($points_polygon, $vertices_x, $vertices_y, $longitude_x, $latitude_y){
$i = $j = $c = $point = 0;
for ($i = 0, $j = $points_polygon ; $i < $points_polygon; $j = $i++) {
$point = $i;
if( $point == $points_polygon )
$point = 0;
if ( (($vertices_y[$point] > $latitude_y != ($vertices_y[$j] > $latitude_y)) && ($longitude_x < ($vertices_x[$j] - $vertices_x[$point]) * ($latitude_y - $vertices_y[$point]) / ($vertices_y[$j] - $vertices_y[$point]) + $vertices_x[$point]) ) )
$c = !$c;
}
return $c;
}
For your testing purpose i passed below things
为了您的测试目的，我通过了以下内容
latitude=22.808059
longitude=77.522014
纬度=22.808059
经度=77.522014
My Polygon
我的多边形
