在Android中对点是否在多边形内进行测试

Question

前些日子，我写了一个Java类来计算一个point(X,Y)是否在多边形内部。（其中的X和Y是double类型，因为它们是地理坐标）。

我知道Java有Polygon类，但我不得不使用Path2D和Point2D，因为Polygon只允许使用整数值，而不能使用double。

当我利用Path2D完成多边形之后，我使用了contains方法（该方法已经包含在Path2D中），这样我的问题就解决了。

但现在，我想要将这个程序导入到Android中，遇到了一些问题。因为Path2D需要导入：

import java.awt.geom.Path2D;
import java.awt.geom.Point2D;

在Android中不存在awt，所以我无法使用它。

那么，是否有类似于具有contains方法的Path2D的类？或者我需要自己计算？

以下是我在Java中如何使用Path2D实现的：

private void ConstructPolygon(Vector<Point2D> coodinates)
{       
    this.polygon.moveTo(coodinates.get(0).getX(), coodinates.get(0).getY());        

    //System.out.println(coodinates.get(0).getX() + "   " + coodinates.get(0).getY());
    //System.out.println("asda");

    for(int i = 1; i < this.num_points; i++)
    {
        //System.out.println(coodinates.get(i).getX() + "   " + coodinates.get(i).getY());
        this.polygon.lineTo(coodinates.get(i).getX(), coodinates.get(i).getY());
    }
    this.polygon.closePath();
}
public boolean InsideCity(Point2D punto)
{
    return this.polygon.contains(punto);                
}

- Shudy

---

也许你可以将所有的“double”值乘以10,000，然后与Java的“Polygon”类一起使用？ - Carlos P

Answer 1

您可以正好使用我的简单库完成此操作：https://github.com/snatik/polygon-contains-point。

准备多边形：

Polygon polygon = Polygon.Builder()
    .addVertex(new Point(1, 3))
    .addVertex(new Point(2, 8))
    .addVertex(new Point(5, 4))
    .addVertex(new Point(5, 9))
    .addVertex(new Point(7, 5))
    .addVertex(new Point(6, 1))
    .addVertex(new Point(3, 1))
    .build();

检查点是否在多边形内：

Point point = new Point(4.5f, 7);
boolean contains = polygon.contains(point);

它适用于浮点类型和包含孔的多边形 :)

- sromku

---

嗨@sromku！ 我有一个问题，我必须读取一个KML文件以获取坐标，但这可能超过100个点...那么我如何为所有这些点使用Builder？因为我的想法是读取kml，在向量中获取点（例如），然后构建多边形...所以...我不知道如何像你一样使用:( 你能帮我吗？谢谢！（代码完美运行！） - Shudy

请注意，此代码无法通过测试用例，如果您恰好使用奇怪的斜线射线直接击中顶点。 - Tatarize

这个库即使是最简单的形状也存在问题，请在考虑之前查看问题列表。https://github.com/sromku/polygon-contains-point/issues - Fernando N.

@KaveeshKanwal 是的，它会。 - sromku

@sromku 在地图坐标的情况下，正确的顺序是 new Point(lat, lon) 还是 new Point(lon, lat)？ - Inosh Perera

Answer 2

你可以使用Google Maps PolyUtil：

import com.google.maps.android.PolyUtil;

boolean inside = PolyUtil.containsLocation(new LatLng(...), poly, true);

- Fernando N.

Answer 3

以下是我在Android中的实现方式。 这是基于这个Java程序（射线投影算法）： https://gis.stackexchange.com/questions/42879/check-if-lat-long-point-is-within-a-set-of-polygons-using-google-maps/46720#46720

    public boolean pointInPolygon(LatLng point, Polygon polygon) {
        // ray casting alogrithm http://rosettacode.org/wiki/Ray-casting_algorithm
        int crossings = 0;
        List<LatLng> path = polygon.getPoints();
        path.remove(path.size()-1); //remove the last point that is added automatically by getPoints()

        // for each edge
        for (int i=0; i < path.size(); i++) {
            LatLng a = path.get(i);
            int j = i + 1;
            //to close the last edge, you have to take the first point of your polygon
            if (j >= path.size()) {
                j = 0;
            }
            LatLng b = path.get(j);
            if (rayCrossesSegment(point, a, b)) {
                crossings++;
            }
        }

        // odd number of crossings?
        return (crossings % 2 == 1);
     }

    public boolean rayCrossesSegment(LatLng point, LatLng a,LatLng b) {
                // Ray Casting algorithm checks, for each segment, if the point is 1) to the left of the segment and 2) not above nor below the segment. If these two conditions are met, it returns true
                double px = point.longitude,
                py = point.latitude,
                ax = a.longitude,
                ay = a.latitude,
                bx = b.longitude,
                by = b.latitude;
            if (ay > by) {
                ax = b.longitude;
                ay = b.latitude;
                bx = a.longitude;
                by = a.latitude;
            }
            // alter longitude to cater for 180 degree crossings
            if (px < 0 || ax <0 || bx <0) { px += 360; ax+=360; bx+=360; }
            // if the point has the same latitude as a or b, increase slightly py
            if (py == ay || py == by) py += 0.00000001;


            // if the point is above, below or to the right of the segment, it returns false
            if ((py > by || py < ay) || (px > Math.max(ax, bx))){ 
                return false;
            }
            // if the point is not above, below or to the right and is to the left, return true
            else if (px < Math.min(ax, bx)){ 
                return true;
            }
            // if the two above conditions are not met, you have to compare the slope of segment [a,b] (the red one here) and segment [a,p] (the blue one here) to see if your point is to the left of segment [a,b] or not
            else {
                double red = (ax != bx) ? ((by - ay) / (bx - ax)) : Double.POSITIVE_INFINITY;
                double blue = (ax != px) ? ((py - ay) / (px - ax)) : Double.POSITIVE_INFINITY;
                return (blue >= red);
            }

     }

- ylag75

---

请分享获取多边形类的链接。 - user2045814

Answer 4

抱歉@sromku，我自己解决了这个问题（我从未使用过这种东西）。如果有人遇到同样的问题，以下是我的解决方法。

Builder poly2 = new Polygon.Builder();
    for(int i = 0; i< xpoints.length;i++){
        poly2.addVertex(new Point(xpoints[i],ypoints[i]));
    }
    Polygon polygon2 = poly2.build();

- Shudy

---

你从哪里导入了 Polygon.Builder();？ - Muhammad Saqib

感谢@sromku。https://github.com/sromku/polygon-contains-point/blob/master/src/main/java/com/snatik/polygon/Polygon.java - necip