确定点是否在Java中的坐标集中 [英] Determine if point is in set of coordinates in java

问题描述

我一直在寻找这个问题的答案，但似乎找不到解决方法.我需要的是一组坐标(开始时长度未知)，并且需要确定一个点是否位于此坐标所确定的多边形内.但是，我不能使用 AWT (就像我最初认为的那样)，因为坐标可以在美国的任何地方变化.

I have searched for an answer to this question, but I cannot seem to find a solution. What I need is I have a set of coordinates (of unknown length in the beginning) and I need to determine if a point resides inside of the polygon determined by this coordinate. However, I cannot use the AWT (as I originally thought I could), as the coordinates can range anywhere in the US.

我认为我需要使用 for-loop ，并进行一系列小于，大于 检查.我是在正确的道路上，还是我没有想到的更简单的解决方案?任何帮助将不胜感激！

I think I need to use a for-loop, with a series of less than, greater than checks. Am I on the right path, or is there an easier solution that I am not thinking of? Any help would be greatly appreciated!

这是我正在使用的数据的示例:

Here is a sample of the data I am working with:

49.006452278468664, 115.10363050431958
48.993314385809654, 115.04009921106841
49.03510754434096, 115.02009771650923
49.04825271759021, 115.08366905978859

推荐答案

Eric Haines在这方面写了一篇很棒的文章:http://erich.realtimerendering.com/ptinpoly/

Eric Haines wrote a great article on this: http://erich.realtimerendering.com/ptinpoly/

您可以使用几种方法，约旦曲线定理相当不错，但是如果您的数据创建一个甜甜圈类型的多边形并且您的点在中间，则会遇到一些问题.

There are a few methods at your disposal, the Jordan Curve Theorem is fairly good but has some issues if your data creates a doughnut type polygon and your point is in the middle.

从本质上说，如果对于该点发出的任何射线，该射线与多边形的边缘之间的交叉点的数量为奇数，则该点位于多边形内部

Essentially, it says that a point is inside a polygon if, for any ray from this point, there is an odd number of crossings of the ray with the polygon's edges

您还可以使用角度求和测试"，该测试速度很慢，但是可以确定点是否在多边形内.

You could also use the Angle Summation Test which is pretty slow but a surefire way to test if a point is inside a polygon.

对每个边缘的端点在该点处形成的正负号角求和.如果总和接近零，则该点位于外面；如果没有，它就在里面(图2)

sum the signed angles formed at the point by each edge's endpoints. If the sum is near zero, the point is outside; if not, it's inside (Figure 2)

第三个方法是三角形测试"，如果您的多边形不太尖锐(我怀疑可能是这样)，它将很好地起作用:

A third method is Triangle Test which will work well if your polygon is not too pointy (which I suspect it might be):

将多边形视为从一个顶点发出的三角形的扇形，并通过计算其重心坐标来针对每个三角形测试该点.

The polygon is treated as a fan of triangles emanating from one vertex and the point is tested against each triangle by computing its barycentric coordinates.

如果您可以检查形状是否为凹形，可以使用其他方法，我建议您阅读本文，因为该文章讨论的解决方法比这里列出的方法还多.

If you can check that the shape is concave there are other methods at your disposal, I would recommend reading the article as it discusses many more ways to solve your problem than the ones listed here.

这篇关于确定点是否在Java中的坐标集中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！