问题标签 [point-in-polygon]

所以我这里有一张地图

如何使用 Google Maps API 检测给定坐标是否在该多边形内？那可能吗？

提前致谢。

I can't figure out how to implement this in a performing way, so I decided to ask you guys.

I have a list of rectangles - actually atm only squares, but I might have to migrate to rectangles later, so let's stick to them and keep it a bit more general - in a 2 dimensional space. Each rectangle is specified by two points, rectangles can overlap and I don't care all too much about setup time, because the rectangles are basicly static and there's some room for precalculate any setup stuff (like building trees, sorting, precalculating additional vectors, whatever etc). Oh I am developing in JavaScript if this is of any concern.

To my actual question: given a point, how do I get a set of all rectangles that include that point?

Linear approaches do not perform well enough. So I look for something that performs better than O(n). I read some stuff, like on Bounding Volume Hierarchies and similar things, but whatever I tried the fact that rectangles can overlap (and I actually want to get all of them, if the point lies within multiple rectangles) seems to always get into my way.

Are there any suggestions? Have I missed something obvious? Are BVH even applicable to possibly overlapping bounds? If so, how do I build such a possibly overlapping tree? If not, what else could I use? It is of no concern to me if borders are inside, outside or not determined.

If someone could come up with anything helpfull like a link or a rant on how stupid I am to use BVH and not Some_Super_Cool_Structure_Perfectly_Suited_For_My_Problem I'd really appreciate it!

Edit: Ok, I played around a bit with R-Trees and this is exactly what I was looking for. Infact I am currently using the RTree implementation http://stackulator.com/rtree/ as suggested by endy_c. It performs really well and fullfills my requirements entirely. Thanks alot for your support guys!

我有一张地图，通过将不同颜色的区域转换为路径，我将它从光栅图形转换为 SVG 文件。

我知道如何在给定边缘数组的情况下进行基本的多边形点检查，但是这些svg:path元素表示多个多边形以及掩码（以考虑海洋等），并且通过解析d属性来提取该信息似乎相当笨拙。

是否有一个 JS 库可以让我简化检查？我基本上想创建随机点，然后检查它们是在陆地上（即多边形内部）还是水（即外部）。

由于 SVG 元素似乎允许处理鼠标事件，我认为这应该不是什么大问题（即，如果您可以判断鼠标指针是否位于元素顶部，那么您已经在解决指向性问题了多边形问题）。

编辑：使事情复杂一点，我应该提到svg:path元素似乎基于曲线而不是线条，因此仅解析d属性以创建边缘数组似乎不是一种选择。

由于元素可以采用fill属性，因此在画布上渲染 SVG，然后在给定点查找像素的颜色值的 ghetto 方法可能会起作用，但这似乎是一种非常非常糟糕的方法。

我已经搜索了很长时间，并没有完全找到答案。有几个接近，但似乎没有什么能准确回答我的问题！我想获取一组坐标，从中创建一个多边形，并确定给定位置是否在该多边形内。任何帮助将不胜感激！

我有一个关于 mysql 的几何数据类型多边形的典型问题。

我有多边形数据，以纬度和经度数组的形式，例如：

我有一个带有纬度和经度坐标的点（顶点），例如：

现在我想找出这个顶点（点）是否在多边形内。我怎么能在 php 中做到这一点？

我想知道确定大量点（O（100万）是否在多边形集合（O（10））内部或外部的最有效方法是什么？后者不一定是凸的，但不是他们有洞。目前我通过将它们的位置与边界框进行比较来修剪点的数量，然后在剩余的点上使用这种交叉数方法。但是也许有更快的方法？

我一直在查看有关确定一个点是否位于多边形内的帖子，而答案对我来说太模糊、抽象或复杂。因此，我将尝试针对我需要做什么提出我的问题。

我有一组描述非直线（有时是闭合多边形）的点。我有一个矩形“视图”区域。我需要尽可能有效地确定是否有任何线段（或多边形边界）通过视图区域。

我不能简单地测试每个点以查看它是否位于视图区域内。一个线段可以通过该区域而实际上没有任何点位于该区域内（即，该线被绘制穿过该区域）。

这是我要确定的示例（红色表示该函数应该为点集返回 true，蓝色表示它应该返回 false，示例使用直线和矩形，因为我不是艺术家）。

我希望能够解释的另一个条件（尽管方法/函数可能是单独的），不仅要确定多边形的边界是否穿过矩形区域，还要确定该区域是否完全被多边形包围。这里的细微差别是，在上面首先描述的情况下，如果我只关心绘制边框，该方法应该返回 false。但在此处描述的情况下，如果我需要填充多边形区域，那么我需要该函数返回 true。我目前不需要担心测试“甜甜圈”形状的多边形（感谢上帝！）。

这是一个说明细微差别的示例（红色矩形没有单个顶点或边框段穿过屏幕区域，但仍应将其视为在屏幕上）：

对于“是否有任何线段或多边形边框穿过或位于屏幕上？” 问题 我知道我可以想出一个解决方案（尽管可能不是一个有效的解决方案）。尽管它更冗长，但条件对我来说是清楚的。但第二个“是屏幕上的多边形区域吗？” 问题有点难。我希望有人可能对这样做有一个很好的建议。如果一个解决方案很容易在另一个之上实施，那么，booya。

与往常一样，提前感谢您的任何帮助或建议。

PS我有一个确定线交点的功能，但是使用它来比较每个段与屏幕区域的每一侧似乎有点过头了，因为屏幕区域总是一个普通的 [0, 0, width, height]长方形。不是有什么捷径吗？

查找一个点是否在以这种形式给出的矩形中的最快方法是什么：
我有两个点，它们是矩形相对边的中心，一个数字是这些边的高度。我希望这很清楚。
矩形（可能）未与轴对齐。我想知道给定这些数据是否有更快的算法，然后计算四个角、旋转等。

我想到但不确定如何实施（数学有问题）的一个想法是找到从点到两个中心之间的线的距离，如果它小于边长的一半矩形，也在线，然后它在矩形中。我不知道如何更好地解释这一点。

或许图片可以帮助解释：
A、B、C，以及A/B边的长度。基本上我认为如果CD小于A边的一半并且D在AB上，那么点就在矩形中。但是我该怎么做呢？
另一个想法：不是找D看它是否在AB上，而是检查角度ABC和BAC是否锐角，但我仍然不知道该怎么做。

我正在尝试检测一个点是否在 gwt-g2d 形状内。有谁知道这怎么可能？

我只能确定该点是否在上下文中的任何路径内。

假设我有一个包含两个矩形（A 和 B）的上下文，并且想确定鼠标在哪个矩形中，我该怎么做？

矩形只是示例，我还想确定该点是否为复杂形状。

我正在开发一个用 javaScript / jQuery 编写的游戏。我的部分代码在平铺网格上绘制了一个随机多边形（一个岛）。我需要检查一个点是否在多边形内。

我正在使用一个多边形交叉点脚本，我在 Stack Overflow的几个 地方找到了该脚本（此处为原文）。这在 Firefox 中运行良好。在 Chrome 中，脚本所说的多边形内有一些点不在其中。

在火狐中：

在 Chrome 中（岛是不同的，因为它们是随机生成的）：

请看这里的源代码，特别是 pointPolygonIntersect 函数： Point in Polygon Hit Test

谁能弄清楚为什么会这样？原始脚本是 C 语言，我使用的是 JavaScript 版本 - 这会导致问题吗？