地理空间查询：PHP实现点在多边形内检测的教程

本教程详细介绍了如何通过php实现点在多边形内的检测，主要采用射线法（ray-casting algorithm）。文章首先阐述了该算法的基本原理，随后提供了完整的php代码示例及其详细解析，帮助开发者理解并应用此功能。最后，探讨了在mongodb等数据库环境中，客户端计算与数据库原生地理空间查询的权衡与选择，为实际项目提供了优化建议。

引言：地理空间查询的重要性

在现代应用开发中，地理空间数据处理变得越来越普遍。例如，在物流配送、区域管理或地理围栏（Geofencing）等场景中，经常需要判断一个给定的点（例如用户当前位置）是否落入某个预定义的多边形区域（例如配送区域）。这类查询的核心问题是“点在多边形内检测”（Point-in-Polygon Test）。虽然一些现代数据库系统（如MongoDB）提供了原生的地理空间查询能力，但理解其底层原理或在特定场景下进行客户端计算仍然非常重要。

点在多边形内检测的核心算法

判断一个点是否在多边形内部，最常用且直观的算法之一是射线法（Ray-Casting Algorithm），也称为奇偶规则（Even-Odd Rule）。其基本思想是从待检测点向任意方向（通常是水平向右）发射一条射线，然后计算这条射线与多边形所有边的交点数量。

• 如果交点数量为奇数，则该点在多边形内部。
• 如果交点数量为偶数（包括0），则该点在多边形外部。

需要注意的是，当射线恰好经过多边形的顶点或边时，需要进行特殊处理以避免计算错误。

PHP实现：射线法检测点在多边形内

以下是一个使用PHP实现射线法判断点是否在多边形内的示例代码。

立即学习“PHP免费学习笔记（深入）”；

代码示例

<?php

/**
 * 判断一个点是否在给定的多边形内部
 *
 * @param int $nvert 多边形的顶点数量
 * @param array $vertx 包含所有顶点X坐标的数组
 * @param array $verty 包含所有顶点Y坐标的数组
 * @param float $testx 待检测点的X坐标
 * @param float $testy 待检测点的Y坐标
 * @return bool 如果点在多边形内部则返回 true，否则返回 false
 */
function inpoly($nvert, $vertx, $verty, $testx, $testy) {
  $i = $j = $c = 0;
  // 遍历多边形的每条边
  // $i 为当前顶点索引，$j 为前一个顶点索引
  for ($i = 0, $j = $nvert - 1; $i < $nvert; $j = $i++) {
    // 检查射线是否与当前边相交
    // 条件1: 判断当前边的两个端点是否分别位于射线上下两侧
    // (verty[$i] > testy) != (verty[$j] > testy)
    // 条件2: 如果条件1成立，计算交点的X坐标，并判断交点是否在testx的右侧
    // testx < (vertx[$j] - vertx[$i]) * (testy - verty[$i]) / (verty[$j] - verty[$i]) + vertx[$i]
    if ((($verty[$i] > $testy) != ($verty[$j] > $testy)) &&
        ($testx < ($vertx[$j] - $vertx[$i]) * ($testy - $verty[$i]) / ($verty[$j] - $verty[$i]) + $vertx[$i])) {
      $c = !$c; // 切换计数器状态
    }
  }
  return $c; // 返回最终的奇偶状态
}

// 示例用法
$vertx = [10, 100, 150, 20]; // 多边形所有顶点的X坐标
$verty = [10, 20, 100, 90];  // 多边形所有顶点的Y坐标
$nvert = count($vertx);      // 顶点数量

$x = 50;  // 待检测点的X坐标
$y = 50;  // 待检测点的Y坐标

$test = inpoly($nvert, $vertx, $verty, $x, $y); // 调用函数进行检测

if ($test) {
    echo "点 ($x, $y) 在多边形内部。\n"; // 预期输出
} else {
    echo "点 ($x, $y) 在多边形外部。\n";
}

$x_out = 10;
$y_out = 5;
$test_out = inpoly($nvert, $vertx, $verty, $x_out, $y_out);
if ($test_out) {
    echo "点 ($x_out, $y_out) 在多边形内部。\n";
} else {
    echo "点 ($x_out, $y_out) 在多边形外部。\n"; // 预期输出
}

?>

代码解析

1. inpoly 函数定义:

   • $nvert: 多边形的顶点数量。
   • $vertx, $verty: 分别存储多边形所有顶点的X和Y坐标的数组。这些数组的索引必须对应，即($vertx[i], $verty[i])构成一个顶点。
   • $testx, $testy: 待检测点的X和Y坐标。
   • $c: 一个布尔标志，初始化为false。每次射线与多边形的一条边相交时，其状态会反转。最终$c为true表示奇数次交点，false表示偶数次交点。

2. 循环遍历多边形的边:

   • for ($i = 0, $j = $nvert - 1; $i < $nvert; $j = $i++): 这个循环巧妙地遍历了多边形的所有边。($vertx[$i], $verty[$i])是当前顶点，($vertx[$j], $verty[$j])是前一个顶点，它们共同构成一条边。当$i从0到$nvert-1时，$j会从$nvert-1到$nvert-2，确保了所有边都被检查，包括首尾相连的边。

3. 射线与边交点判断:

   • (($verty[$i] > $testy) != ($verty[$j] > $testy)): 这个条件判断多边形当前边的两个端点是否分别位于待检测点水平射线的上方和下方。如果一个在上方一个在下方，说明这条边可能与水平射线相交。
   • ($testx < ($vertx[$j] - $vertx[$i]) * ($testy - $verty[$i]) / ($verty[$j] - $verty[$i]) + $vertx[$i]): 如果前一个条件成立，这个条件会计算射线与边的交点的X坐标。
     • ($testy - $verty[$i]) / ($verty[$j] - $verty[$i]) 计算了待检测点Y坐标相对于当前边两个端点Y坐标的比例。
     • 将这个比例乘以边的X坐标差 ($vertx[$j] - $vertx[$i])，得到X方向上的偏移量。
     • 加上 +$vertx[$i] 得到交点的X坐标。
     • 最后，$testx < ... 判断交点的X坐标是否大于待检测点的X坐标，即交点是否在射线的右侧。
   • 如果两个条件都满足，说明射线与当前边在待检测点右侧发生有效交点，此时 $c = !$c 反转标志。

4. 返回结果: 循环结束后，$c的值即为判断结果。true表示点在内部，false表示点在外部。

   

   Writer

   企业级AI内容创作工具

   176

   查看详情

实际应用与MongoDB集成考量

虽然上述PHP代码提供了一个功能完善的客户端解决方案，但在实际项目中，特别是与MongoDB等支持地理空间查询的数据库结合时，需要权衡客户端计算与数据库原生查询的优劣。

客户端计算的优势与局限

• 优势:
  • 独立性: 不依赖特定数据库的地理空间功能，可以在任何PHP环境中运行。
  • 灵活性: 对于少量数据或复杂自定义几何计算，客户端脚本可能更灵活。
  • 即时性: 如果数据已经在内存中，可以避免数据库往返的延迟。
• 局限:
  • 性能: 对于大规模多边形或大量点的查询，客户端计算可能效率低下，尤其是当需要遍历所有多边形来查找匹配项时。
  • 数据同步: 如果多边形数据存储在数据库中，每次查询都需要从数据库中检索所有多边形数据，增加了I/O开销。
  • 维护: 客户端代码需要自行处理所有几何算法的细节，可能引入更多错误。

MongoDB原生地理空间查询（$geoWithin）

MongoDB从2.4版本开始提供了强大的地理空间查询功能，特别是$geoWithin操作符，可以高效地判断一个点是否在一个或多个多边形内。这需要为存储地理空间数据的字段创建2dsphere索引。

MongoDB示例查询:

假设您在MongoDB集合中存储了名为delivery_zones的文档，每个文档包含一个geometry字段，存储GeoJSON格式的多边形：

{
  "_id": ObjectId("..."),
  "name": "Zone A",
  "geometry": {
    "type": "Polygon",
    "coordinates": [
      [ [10, 10], [100, 20], [150, 100], [20, 90], [10, 10] ]
    ]
  }
}

要查询一个点[50, 50]是否在任何一个delivery_zones多边形内，可以使用$geoWithin：

db.delivery_zones.find({
  geometry: {
    $geoIntersects: { // 或 $geoWithin，取决于您的GeoJSON版本和具体需求
      $geometry: {
        type: "Point",
        coordinates: [50, 50]
      }
    }
  }
})

或者，如果您的多边形存储在文档中，而您想查询某个点是否在某个文档的多边形内，且该点也存储在文档中：

// 查找点 [50, 50] 所在的区域
db.delivery_zones.find({
  geometry: {
    $geoIntersects: {
      $geometry: {
        type: "Point",
        coordinates: [50, 50]
      }
    }
  }
})

优点:

• 性能优越: 数据库利用2dsphere索引进行优化查询，尤其适用于大规模数据。
• 简洁: 查询语句直观，无需编写复杂的几何算法。
• 可伸缩性: 数据库层面的优化能够更好地支持高并发查询。

何时选择客户端计算，何时选择数据库计算

• 选择客户端计算:
  • 多边形数据量极小且不经常变动，或者多边形数据已在客户端缓存。
  • 需要进行非常规或自定义的几何运算，而数据库原生功能无法满足。
  • 对数据库的依赖性有严格限制，或数据库不支持地理空间查询。
• 选择数据库计算:
  • 多边形数据量大，且需要频繁进行点在多边形内查询。
  • 需要利用数据库的索引优化查询性能。
  • 对数据一致性和实时性要求较高。
  • 应用场景涉及复杂的地理空间关系（如交集、并集等）。

注意事项与性能优化

1. 多边形闭合: 确保多边形的第一个顶点和最后一个顶点是相同的，以形成一个闭合的多边形。上述PHP代码假设多边形是闭合的。
2. 简单多边形: 提供的射线法代码主要适用于简单多边形（非自相交）。对于复杂或自相交的多边形，可能需要更复杂的算法（如回转数算法Winding Number Algorithm）或预处理来确保准确性。
3. 浮点数精度: 地理坐标通常是浮点数，浮点数运算可能存在精度问题。在进行比较时，可能需要考虑一个小的容差值。
4. 性能: PHP客户端计算的性能瓶颈在于循环遍历多边形的边。对于包含大量顶点的多边形，或者需要对大量点进行检测时，性能会显著下降。在这种情况下，优先考虑使用支持地理空间索引的数据库。
5. MongoDB索引: 如果选择使用MongoDB的$geoWithin或$geoIntersects，务必为存储地理空间数据的字段创建2dsphere索引，这是性能的关键。

总结

点在多边形内检测是地理空间应用中的一项基本功能。通过PHP实现的射线法提供了一个直观且易于理解的客户端解决方案。然而，在考虑性能、数据规模和系统架构时，应充分利用MongoDB等数据库提供的原生地理空间查询能力，通过2dsphere索引和$geoWithin等操作符实现更高效、可伸缩的解决方案。理解这两种方法的原理和适用场景，有助于开发者在项目中做出明智的技术选型。

以上就是地理空间查询：PHP实现点在多边形内检测的教程的详细内容，更多请关注php中文网其它相关文章！