logo标签列表

检查一个点是否存在于包含4个顶点的给定区域中。

javageometry
5
4个回答
5

测试一个点是否在任意多边形内（允许凹面，任意多边形），方法是选择一个你知道在多边形外的点；如果连接测试点和在多边形外的点的线段穿过奇数个多边形边界，那么这个点就在多边形内。

这是约旦曲线定理的一个推论。http://en.wikipedia.org/wiki/Jordan_curve_theorem - Jason S
@JasonS：有趣；我刚学到它是“测试一个点是否在任意多边形内的方法”。不过，我学习这个知识的来源可能也是从那个定理得来的。 - Paul Sonier
请澄清这是否适用于球体，还是仅适用于平面（或某些更广泛的非球形表面）。 - erickson
4
这是一个关于球面坐标系上的点在多边形内问题，它有几个微妙之处，使它比“常规”的X-Y平面上的点在多边形内问题更加困难：
1）什么在内部和外部？（例如，如果我有一个边长为1英里的小“正方形”，它是否包含1平方英里或地球表面的其余部分？对于非常大的多边形来说，除非明确指定，否则可能不清楚哪些应该在内部，哪些应该在外部。）
2）多边形的线段是否为大圆线段？如果是，则在纬度-经度坐标系中，除了子午线或赤道，它们不代表直线，而需要在几何上处理曲线而不是直线。球面几何是正确的方法。

3）坐标系的“边缘”（国际日期变更线和极点） - 由经度+179.9度，-179.9度和纬度+0.1度，-0.1度所限定的“正方形”通常不会被认为包含点0 N，0 W，并且将被认为包含点0 N，180 W。但是，如果您简单地检查纬度/经度点的不等式，您将得到相反的答案。

因此，我没有答案，但这些是需要考虑的微妙问题。（将其视为“确保将其包括为测试用例”！）

编辑：我找到了spheres包，它有SphericalPolygon.contains方法，可能可以做到你要找的功能。但是我个人没有使用过这个包，而且它是GPL，不是LGPL，所以如果你想在专有产品中使用它，它会“污染”你的源代码。
另一个问题是多边形的边缘是否可以相互交叉。一个由4个顶点组成的多边形可以是一个简单的实体，也可以是由两个三角形组成的实体。 - jmucchiello
如果您的顶点按顺序给出，则内部是正确的一侧。 - MSalters
那也是真的。 :) 我之前忽略了这种情况，因为虽然可能存在，但从GIS数据库中提取这样的数据并不明智。 - Jason S
@MSalters：这需要通过众所周知的约定达成一致。（为什么不是左边？）但我同意，这就是地理信息系统处理它和处理空洞的方式。 - Jason S
你好 Jason，是的，你建议参考的球形包由于GPL许可证无法使用，请你提供其他好的解决方案。期待你的回复。 - shoaib
1

你是指编程上的还是数学上的？如果你理解了数学上的，编程上就很容易了。基本上，顶点定义了线条。你只需要知道哪一侧的线条构成了“内部”。然后，将你的顶点转换为方程，但使用小于或大于而不是等于。

也就是说，假设你有以下方程定义的矩形： x=1，x=3，y=1，y=3

如果你想知道(2,2)是否在该区域内，只需评估每个方程： x > 1，x < 3，y > 1，y < 3。

如果这四个方程都成立，则该点在该区域内。

如果它不是与纬度和经度线完全对齐的矩形（即倾斜的），那该怎么办？ - Steve Kuo
是的，这是一个用于三角形的好技术，但对于任意多边形来说并不是很好，因为如果它们是凹多边形，你可能会得到无效的结果。不过，如果你的多边形是凸的，这个方法确实非常有效。 - Paul Sonier
我不明白如何用四个顶点表示凹面或凸面，而且这种方法适用于不仅仅是矩形。无论你有多少个顶点，你只需要评估每条线并比较<或>……就这样。关键是要知道你的点是否应该在线的左侧还是右侧。我不明白为什么这么难？ - D. Patrick
你好，D.Patrick先生，您的意思是该网址 http://pietschsoft.com/post/2008/07/Virtual-Earth-Polygon-Search-Is-Point-Within-Polygon.aspx 的代码适用于以下文件页码7-9所给出的区域吗？ http://www.weather.gov/directives/sym/pd01008006curr.pdf - shoaib
-1
你好Jvenema！ 上面链接中你建议的代码是否适用于下面文件第7-9页给出的区域： http://www.weather.gov/directives/sym/pd01008006curr.pdf - shoaib
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接