问题标签 [point-in-polygon]

我一直试图弄清楚如何编写一个简单的程序来计算 x,y 点以创建 n 边的正多边形。有人可以给我一些不使用绘制多边形的现有函数的代码示例吗？我想了解这个过程，我假设是这样的：

1. 选择一个角度从半径和中心点开始
2. 以某种方式计算距中心该距离处的 x,y 位置（如何？）
3. 将 360 除以边数，移动该距离并从第一个 x,y 点绘制下一条线
4. 继续直到角度= 360除以该数字。

假设我的假设是正确的，主要是了解如何计算 x,y 点。

更喜欢 Visual Basic（甚至旧式 Microsoft/Atari/Commodore BASIC）或人类可读的英语步骤的答案。如果您必须用数学公式回答，请用计算机语言进行，以便我可以阅读它，即使在 C 或 C++ 中我也可以弄清楚，但我不知道如何阅读数学符号。我使用的语言是一种类似于 Visual Basic 的语言，除了线条绘制之外几乎没有图形基元。

我需要确定某些 LatLngs 是否在 Google Maps Circle 内（其中之一： http ://code.google.com/apis/maps/documentation/javascript/overlays.html#Circles ）。我将如何解决这个问题？我制作圆圈的标记是：

我可以只使用半径吗？

我们需要找出一种快速且相当准确的方法，用于在谷歌地图上获取纬度/经度值和多边形的多边形点。经过一些研究 - 遇到了一些关于 mysql 几何扩展的帖子，并且也实现了 -

然而，这不适用于由大量点组成的多边形:(

经过更多研究 - 遇到了一种称为 Ray-casting 算法的标准算法，但在尝试在 MySQL 中开发查询之前，如果有人已经通过该算法或遇到一个显示如何实现的有用链接，我想借此机会MySQL / SQL-server 中的算法。

所以，缩短它 - 问题是：

谁能提供Ray Casting算法的MySQL/SQL-server实现？

附加细节：

• 多边形是凹的、凸的或复杂的。
• 目标是快速执行超过 100% 的准确度。

我正在创建一个飞镖评分程序（在我的飞镖室中使用我自己），并希望用户能够单击飞镖板图片的不同区域来注册投掷的飞镖。

这个程序可以调整大小，所以当用户改变程序窗口大小时，飞镖板的图片可以改变它的大小。

我使用多边形列表（pointF-arrays）来映射每个区域并运行一些计算以查看鼠标单击是否在多边形区域内，但是当图片框调整大小时如何正确缩放这些多边形？我的多边形经过硬编码，以特定尺寸映射图片的飞镖区域。

编辑：在 Olivier Jacot-Descombes 给出非常出色的回答之后，我使用 GetScaledPoint 函数修复了缩放，该函数将鼠标指针 x 和 y 值转换为与原始图片大小匹配的值，从而可以轻松检查原始多边形中的命中. 如果有人感兴趣，我已经在下面的代码中编辑了解决方案。在此示例中，Picture1 是飞镖板的图片（例如http://quizmasters.biz/Pub%20Genius/Darts/Gfx/Dartboard_05.jpg），设置为 sizemode=stretch 和 docking=fill。

我的主视图有几个（可能很多）多边形活动区域，它们实现为子视图。当用户触摸视图时，我想确定她是否点击了这些活动区域之一。

有什么比一个简单的算法更好的方法来遍历所有 [可能*] 活动区域的列表并询问它们中的每个点是否在其中？

我不能使用（不覆盖它）hitTest:withEvent:，因为它的文档指出“此方法忽略隐藏的、禁用用户交互或 alpha 级别小于 0.01 的视图对象。”。而且我的子视图确实是隐藏的（大部分时间）。

我可以看到这些选项：

• 实现我自己成熟的四叉树实现。这有点过早优化的味道，这是在重新发明轮子，因为我希望 Apple 的命中测试实现已经得到优化

• 通过保持每个最大和最小 x 和 y 坐标来限制 [可能*] 区域，并首先在该矩形上进行命中测试。事实上，我的子视图frame 就是那些矩形。我希望 Apple 的命中测试能够使用这些。

• 在我的子视图中覆盖 Cocoa TouchhitTest:withEvent:以删除记录的限制。希望这不会对我的应用程序产生不利影响（例如，我可以忽略子视图上的任何虚假触摸事件，或者将它们转发到我的主视图）。

• 天真并相信用户永远不会在实际使用中添加太多活动区域，以免天真的算法执行得太差。

有什么建议吗？

请注意，多边形总是简单的，但不一定是凸的。此外，我使用的最精确的命中测试是使用 Quartz 例程CGPathContainsPoint

我在 php 中使用多边形点检查，但我遇到了重大错误 - 因为不在多边形中的点出现在内部。

我的基本函数在下面输入（在这里找到，从一个类修改为一个简单的函数：http ://www.assemblysys.com/dataServices/php_pointinpolygon.php ）。我唯一能想到的是某处的某种舍入错误？

作为一个例子，我试图确定一个点是否在中央公园，一个简单的广场，但我从公园外的点得到肯定。

感谢您的任何见解，

-D

我试图弄清楚纬度/经度点是否包含在由代表地球上的点的顶点定义的多边形内（也是纬度/经度，按顺时针顺序排列）。这对于可以映射到 2D 纬度/经度空间的多边形来说是微不足道的。

这变得越来越困难的是圆圈（现在切换回 3D），它可能会从一个极点到另一个极点，覆盖半个地球。转换为纬度/经度看起来像一个正弦波。多边形测试中的 2D 点不再适用于这种情况。是否存在解决此问题的算法？

================== 澄清以下评论： =================== 多边形定义为（lon， lat) 对以度为单位，即 (60, 90), (60, 110), (-30, 110), (-30, 90)。

我确实有实现光线投射算法的代码，并且有效。但是，地球表面上的某些多边形不会转换为 2D 空间中的封闭多边形。

我有很多点（数十万个），我想检查哪些点在多边形内。对于一个相对较小的多边形（即，可能只包含数十或数百个点），我可以只使用多边形的边界框作为初始检查，然后对框内的这些点进行常规的多点检查. 但是想象一个大的（即，可能包含我的数千个点）、不规则形状的多边形。许多点将通过边界框检查，此外，多点检查将更昂贵，因为更大的多边形由更多点组成。所以我希望能够过滤掉大部分点，而不必进行完整的多点检查。

所以，我有一个计划，主要是我想知道我所描述的是否是一个众所周知的算法，如果是，它叫什么以及我可以在哪里找到它的现有代码。我不相信我所描述的是四叉树或 r-tree，我不知道如何搜索它。我在下面称它为“矩形树”。

这个想法是，要处理这些较大的多边形：

做一个“矩形树”预处理，矩形树的深度随多边形的大小而变化（即，允许更大的多边形有更多的深度）。矩形树将多边形的边界框分成四等分。它会检查每个四分之一矩形是否完全在多边形内，完全在多边形外，或者两者都不。在两者都不是的情况下，它不会递归地划分子矩形，以这种方式继续，直到所有矩形都完全在内部或外部，或者已经达到最大深度。所以这个想法是（a）制作这棵树的预处理时间，即使它本身会做几个多边形点检查，也是非常值得的，因为这个时间与要检查的点的数量相比相形见绌，

那个算法叫什么？代码在哪里？它实际上看起来并不难写，但我想在开始编码之前我会问一下。

这对你们计算机科学家来说是一个有点棘手的问题。假设我有一个 100 x 100 个条目的二维数组/矩阵，arr[i][j]。其中 i 和 j 从 0 到 99。这可以设想为一个正方形的点，每个点对应一个数据值。

现在，如果我定义了一个 4 点多边形并知道这 4 个点的索引：是否有可能（是否有一个聪明的算法）只循环遍历位于 4 点多边形内部的矩阵中的那些条目？也就是说，循环圈中 i 和 j 的每个值都对应于 arr[i][j] 中有趣的值（i 和 j 在 4 点多边形内）。

这清楚吗？我理解如果很难理解。

您忠诚的

我正在存储谷歌返回的边界。这些是 ne_lat、ne_lng、sw_lat 和 sw_lng 坐标的形式。

我在 mysql ploygons 函数中寻找一些实现，这里是带有一些示例条目的示例函数：

GeomFromText('多边形((0 0,0 3,3 3,3 0,0 0))')

谁能告诉我在上多边形函数中正确替换谷歌返回的边界？

我做了一些研究，得出的结论是：

GeomFromText('多边形((ne_lat ne_lng,ne_lat sw_lng,sw_lat sw_lng,sw_lat ne_lng,ne_lat ne_lng))')

我在多边形函数中做了正确的输入吗？

提前致谢！