java 确定坐标是否在多边形工具类内 - II：规范

最编程 2024-10-12 09:49:43

...

<1>射线法（Ray Casting Algorithm）

射线法是一种简单而直观的方法，它通过从待判断的点向任意方向发射一条射线，然后计算这条射线与多边形各边的交点数量。如果交点数量为奇数，则点在多边形内；如果为偶数，则点在多边形外。

示例代码

public class PointInPolygon {
    public static boolean isPointInPolygon(double x, double y, double[] polyX, double[] polyY) {
        int n = polyX.length;
        boolean inside = false;
        for (int i = 0, j = n - 1; i < n; j = i++) {
            if (polyY[i] > y != polyY[j] > y && x < (polyX[j] - polyX[i]) * (y - polyY[i]) / (polyY[j] - polyY[i]) + polyX[i]) {
                inside = !inside;
            }
        }
        return inside;
    }

    public static void main(String[] args) {
        double[] polyX = {1, 4, 4, 1};
        double[] polyY = {1, 1, 4, 4};
        double x = 2.5;
        double y = 2.5;
        System.out.println("Point (" + x + ", " + y + ") is " + (isPointInPolygon(x, y, polyX, polyY) ? "inside" : "outside") + " the polygon.");
    }
}

<2> 多边形三角剖分法

多边形三角剖分法将多边形分解成若干个三角形，然后判断点是否在这些三角形内。这种方法在处理凹多边形时非常有效。

示例代码

import java.util.ArrayList;
import java.util.List;

public class Triangle {
    double x1, y1, x2, y2, x3, y3;

    public Triangle(double x1, double y1, double x2, double y2, double x3, double y3) {
        this.x1 = x1;
        this.y1 = y1;
        this.x2 = x2;
        this.y2 = y2;
        this.x3 = x3;
        this.y3 = y3;
    }

    public boolean isPointInside(double px, double py) {
        double area = (x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)) / 2.0;
        double signedArea = (px * (y2 - y3) + x2 * (py - y3) + x3 * (y3 - py)) / 2.0;
        return signedArea > 0 == (area > 0);
    }
}

public class PointInPolygonTriangulation {
    public static boolean isPointInPolygon(double x, double y, double[] polyX, double[] polyY) {
        List<Triangle> triangles = triangulatePolygon(polyX, polyY);
        for (Triangle triangle : triangles) {
            if (triangle.isPointInside(x, y)) {
                return true;
            }
        }
        return false;
    }

    private static List<Triangle> triangulatePolygon(double[] polyX, double[] polyY) {
        // This is a placeholder for a triangulation algorithm.
        // A real implementation would use an algorithm like Ear clipping or the Bayazit algorithm.
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        double[] polyX = {1, 4, 4, 1};
        double[] polyY = {1, 1, 4, 4};
        double x = 2.5;
        double y = 2.5;
        System.out.println("Point (" + x + ", " + y + ") is " + (isPointInPolygon(x, y, polyX, polyY) ? "inside" : "outside") + " the polygon.");
    }
}

<3>向量叉积法

向量叉积法通过计算点与多边形顶点形成的向量叉积的符号来判断点的位置。如果所有叉积的符号相同，则点在多边形的同一侧，即点在多边形内。

示例代码：

public class PointInPolygonCrossProduct {
    public static boolean isPointInPolygon(double x, double y, double[] polyX, double[] polyY) {
        int n = polyX.length;
        boolean result = false;
        for (int i = 0, j = n - 1; i < n; j = i++) {
            if (((polyY[i] <= y && y < polyY[j]) || (polyY[j] <= y && y < polyY[i]))
                    && (x < (polyX[j] - polyX[i]) * (y - polyY[i]) / (polyY[j] - polyY[i]) + polyX[i])) {
                result = !result;
            }
        }
        return result;
    }

    public static void main(String[] args) {
        double[] polyX = {1, 4, 4, 1};
        double[] polyY = {1, 1, 4, 4};
        double x = 2.5;
        double y = 2.5;
        System.out.println("Point (" + x + ", " + y + ") is " + (isPointInPolygon(x, y, polyX, polyY) ? "inside" : "outside") + " the polygon.");
    }
}

<4>利用Java图形库

Java的java.awt.geom包提供了一些工具类，可以帮助我们进行点和多边形的碰撞检测。

示例代码

import java.awt.geom.Path2D;

public class PointInPolygonJavaAWT {
    public static boolean isPointInPolygon(double x, double y, double[] polyX, double[] polyY) {
        Path2D polygon = new Path2D.Double();
        polygon.moveTo(polyX[0], polyY[0]);
        for (int i = 1; i < polyX.length; i++) {
            polygon.lineTo(polyX[i], polyY[i]);
        }
        polygon.closePath();
        return polygon.contains(x, y);
    }

    public static void main(String[] args) {
        double[] polyX = {1, 4, 4, 1};
        double[] polyY = {1, 1, 4, 4};
        double x = 2.5;
        double y = 2.5;
        System.out.println("Point (" + x + ", " + y + ") is " + (isPointInPolygon(x, y, polyX, polyY) ? "inside" : "outside") + " the polygon.");
    }
}

<5>利用GIS库

对于复杂的GIS应用，我们可以使用专业的GIS库，如GeoTools或JTS Topology Suite，这些库提供了丰富的空间分析功能。

示例代码（使用JTS）

import org.locationtech.jts.geom.Coordinate;
import org.locationtech.jts.geom.GeometryFactory;
import org.locationtech.jts.geom.LinearRing;
import org.locationtech.jts.geom.Polygon;

public class PointInPolygonJTS {
    public static boolean isPointInPolygon(double x, double y, double[] polyX, double[] polyY) {
        GeometryFactory factory = new GeometryFactory();
        LinearRing shell = factory.createLinearRing(new Coordinate[] {
                new Coordinate(polyX[0], polyY[0]),
                new Coordinate(polyX[1], polyY[1]),
                new Coordinate(polyX[2], polyY[2]),
                new Coordinate(polyX[3], polyY[3]),
                new Coordinate(polyX[0], polyY[0])
        });
        Polygon polygon = factory.createPolygon(shell, null);
        return polygon.contains(factory.createPoint(new Coordinate(x, y)));
    }

    public static void main(String[] args) {
        double[] polyX = {1, 4, 4, 1};
        double[] polyY = {1, 1, 4, 4};
        double x = 2.5;
        double y = 2.5;
        System.out.println("Point (" + x + ", " + y + ") is " + (isPointInPolygon(x, y, polyX, polyY) ? "inside" : "outside") + " the polygon.");
    }
}

<6>总结

在Java中判断一个点是否在多边形内，我们有多种方法可以选择。每种方法都有其适用场景和优缺点。射线法简单直观，适合凸多边形；向量叉积法和多边形三角剖分法适合凹多边形；利用Java图形库或GIS库则提供了更为强大和通用的解决方案。选择哪种方法取决于具体的需求、多边形的复杂度以及性能要求。

性能考虑在选择实现方法时，性能也是一个重要的考虑因素。对于大规模的数据处理，射线法由于其简单性，通常具有较好的性能。然而，对于复杂的多边形或者需要频繁进行点内判断的情况，使用专门的GIS库可能会更加高效，因为这些库通常经过了优化，并且利用了底层的硬件加速。

上一篇：连接 Gitee 仓库的 PyCharm 工具

下一篇： RediSearch 是比 Es Search 更快的搜索引擎！