问题标签 [point-in-polygon]

在编程竞赛中解决多边形中的点的最佳算法是什么？

我想看看一个点是否在多边形中。当然，我用谷歌搜索并查看了这个问题是否早先得到了回答，然后找到了这个算法： http: //www.ecse.rpi.edu/Homepages/wrf/Research/Short_Notes/pnpoly.html 这工作正常，除非多边形部分打开. 例如：

AE 被检测到，但 B 多边形的开放部分也被认为是封闭的！如果你运行这个示例代码，你会明白我的意思：

x2/y2 多边形由一个连接到部分开放块的封闭块组成。pnpoly 函数仍然认为开放块“中”的点位于多边形中。

我现在的问题是：我该如何解决这个问题？还是我忽略了什么？

提前致谢。

我正在寻找一种算法，我可以创建一个地理围栏并检查设备是否正在进入/离开围栏。我已经研究过多边形算法中的点（光线投射和缠绕数），但是是否有任何算法可以应用于圆形和任何不规则形状？重要的限制是时间效率。

谢谢你。

我有一种方法会占用我 25% 的 CPU 时间。我每秒调用这种方法大约 27,000 次。（是的，很多电话，因为它经常更新）。我想知道是否有人知道一种更快的方法来检测 2 个多边形是否重叠。基本上，我必须检查屏幕上的移动对象和屏幕上的静止对象。我正在使用 PathGeometry，下面的两个调用占用了我的程序使用的 CPU 时间的 25%。我传递的 PointCollection 对象仅包含代表多边形 4 个角的 4 个点。它们可能不会创建一个矩形区域，但所有点都是连接的。我想梯形将是形状。

这些方法很短而且很容易实现，但我想我可能想选择一个更复杂的解决方案，如果我可以让它比下面的代码运行得更快。有任何想法吗？

我有一个问题希望大家帮我解决。

我有一个 DbGeometry 点（或 DbGeography，我可以同时使用两者），我想检查它是否在 DbGeometry 多边形内（或者 DbGeography）。

我现在正在这样做：

所以我遍历区域（我的数据库的 EF 实体）并检查我拥有的这个点是否在这个边界内。

问题是它不返回任何结果，但我知道该点在该边界内，因为我手动创建了边界和该边界内的点。

谁能告诉我我做错了什么，是否有其他方法可以做到这一点或其他什么？

非常感谢。

曼努埃尔

如何在多边形内放置标记（这个多边形已经在地图上）？我的想法是：找到一种方法将例如圆内接到多边形并找到该圆的中心（这不是问题），但找不到内接圆的方法。

LatLngBounds 上的方法 getCenter() 无法按预期工作，因为多边形的数学中心可能在视觉上超出此多边形。

我需要在多边形MySQL 查询中指出一点。

我已经找到了这两个很好的解决方案：

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

光线投射算法的MySQL实现？

但是这些函数只能检查一个点是否在多边形内。我有一个查询，其中画中画部分应该只是查询的一部分，并检查多边形内的 x 点。

像这样的东西：

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

更新

我用这样的MBR函数进行了尝试：

G2 不应该在 G1 内，但MBR说它是。

我试图弄清楚如何最好地做到这一点，我有一张地图，Polygon上面画了一张。由于 Google Maps API V2 似乎没有在多边形上进行触摸检测。我想知道是否可以检测到触摸点是否在多边形内部？如果是这样，那么如何，我的主要目标是在地图上勾勒出一个状态，当用户点击该状态时，它将在自定义视图中显示更多详细信息。到目前为止，我能够捕获MapOnClick地图，但是当用户在里面点击时，Polygon我想要polygon.getID()在Toast. 我是新手，所以如果我不够清楚，我很抱歉。

好的，这就是我到目前为止的半工作

}

我遇到的问题是每个多边形左侧的触摸都是真实的，直到它到达另一个多边形。我的算法有什么问题会导致这个问题？任何帮助，将不胜感激。

我开始学习处理复杂和简单的多边形，确定点是否在多边形内部/外部等（例如http://geomalgorithms.com/a09-_intersect-3.html和相关页面）。我希望找到一个提供 Bentley-Ottmann 算法、绕组数、边缘交叉等实现的 R 包。

或者，是否有 CGAL 库或类似工具集的 R 接口？Rcpp 是解决此问题的最佳（或唯一）方法吗？

在过去的几个月里，我设法自学了 PHP、PDO 和 SQL，并按照 PHP/SQL 最佳实践构建了一个具有用户注册/电子邮件激活/和登录注销功能的基本动态网站。现在我被困在下一个任务上......

我创建了一个巨大的正方形/多边形数据集（300 万+），每 1 分钟的纬度和经度大小，存储在一个带有一组坐标（左上角）的 PHP 数组中。为了推断出一个类似正方形的形状，我只需在每个方向上添加 0.016 度（约 1 分钟）并生成其他 3 个坐标。

我现在需要检查所述阵列中的每个多边形是否至少在美国的某些土地上......即如果要生成我完成的数据集的图形输出并查看旧金山海岸线，他们会看到这样的东西。

它类似于多边形中的点问题，除了它处理的是另一个多边形而不是一个点，另一个多边形是国家边界，我不只是在看交叉点。我想检查是否：

• 多边形/正方形与多边形相交。（想想海岸线/边界）。
• 多边形/正方形位于多边形内。（想想美国大陆）。
• 多边形/正方形包含多边形的一部分。（想想小岛）。

用我粗略绘制的图像说明了这一点：

如果它符合这三个条件中的任何一个，我想保留正方形。如果它无论如何都不与大多边形交互（即它在水面上），则丢弃它。

我在想大多边形将是美国的 shapefile，或者是一个 KML 文件，我可以从中剥离坐标以创建一个非常复杂的多边形。

然后，我想我会将这些匹配的正方形和正方形 ID 传递给 csv 文件，以便集成到包含每个正方形的一组坐标的 MySQL 表中（事实上，我什至不确定处理表的最佳实践MySQL 中的那个大小，但我会在需要的时候来讨论）。最终的目标是通过 Javascript 使用 Google Maps API 开发地图，以在我正在编码的网站上的地图上显示这些方块（显然只在视点内显示方块以确保我不会对我的数据库征税致死）。我很确定我也必须先通过 PHP 传递这些信息。但与实际制作所述数据集的任务相比，所有这些似乎都相对容易。

这显然是手工无法完成的事情，因此需要自动化。我知道一点Python，那会有帮助吗？关于从哪里开始的任何其他提示？有人愿意为我写一些代码吗？