Android — 判断点是否位于多边形内

最近参与一个室内AP定位的项目做Android客户端的开发。

自己写了一个静态地图控件，遇到了需要判断触摸点是否位于多边形指定区域内的问题。

网上资料很多，主流方法是利用光投射算法。Point in polygon - Wikipedia

CSDN上有一篇文章把原理讲的非常详细 点在多边形内算法——判断一个点是否在一个复杂多边形的内部

参考 StackOverFlow 上一个回答的写法，翻译成 JAVA 如下：

/**
 * 利用光投射算法计算点是否在多边形内
 * 
 * @param point 需要判断的点的坐标
 * @param vertices 多边形按顺时针或逆时针顺序的顶点坐标集合
 * @return 点是否在多边形内
 */
public static boolean isPointInPolygon(PointF point, List<PointF> vertices) {
	boolean contains = false;
	for(int i = 0, j = vertices.size() - 1; i < vertices.size(); j = i++) {
		if(((vertices.get(i).y >= point.y) != (vertices.get(j).y >= point.y)) &&
		   (point.x <= (vertices.get(j).x - vertices.get(i).x) * (point.y - vertices.get(i).y) / (vertices.get(j).y - vertices.get(i).y) + vertices.get(i).x))
			contains = !contains;
	}
	return contains;
}

为了方便使用，我将它封装到了我的 Polygon 类里。

public class Polygon {

    public static class Builder {
        private List<PointF> vertices = new ArrayList<>();
        public Polygon.Builder addVertice(PointF point){
            this.vertices.add(point);
            return this;
        }
        public Polygon build(){
            if (vertices.size() < 3) {
                throw new RuntimeException("Polygon must have at least 3 points");
            }
            return new Polygon(this.vertices);
        }
    }

    private List<PointF> vertices;

    public Polygon(List<PointF> vertices){
        this.vertices = vertices;
    }
    public Polygon() {
        this.vertices = new ArrayList<>();
    }

    public static Builder Builder(){
        return new Polygon.Builder();
    }

    public void setVertices(List<PointF> vertices) {
        this.vertices = vertices;
    }
    public List<PointF> getVertices() {
        return vertices;
    }

    public Path getPolygonPath(){
        int i = 0;
        Path path = new Path();
        for (PointF point : vertices) {
            if (i == 0) path.moveTo(point.x, point.y);
            else path.lineTo(point.x, point.y);
            i++;
        }
        path.close();
        return path;
    }

    public boolean contains(List<PointF> points){
        for (PointF point: points){
            if (!contains(point))
                return false;
        }
        return true;
    }
    public boolean contains(PointF point){
        return Polygon.isPointInPolygon(point, this.vertices);
    }

    /**
     * 利用光投射算法计算点是否在多边形内
     *
     * @param point 需要判断的点的坐标
     * @param vertices 多边形按顺时针或逆时针顺序的顶点坐标集合
     * @return 点是否在多边形内
     */
    public static boolean isPointInPolygon(PointF point, List<PointF> vertices) {
        boolean contains = false;
        for(int i = 0, j = vertices.size() - 1; i < vertices.size(); j = i++) {
            if(((vertices.get(i).y >= point.y) != (vertices.get(j).y >= point.y)) &&
                    (point.x <= (vertices.get(j).x - vertices.get(i).x) * (point.y - vertices.get(i).y) / (vertices.get(j).y - vertices.get(i).y) + vertices.get(i).x))
                contains = !contains;
        }
        return contains;
    }

}