我试图创建一个快速的2D点内多边形算法,用于命中测试(例如多边形.contains(p:点))。对有效技术的建议将不胜感激。


当前回答

Java版本:

public class Geocode {
    private float latitude;
    private float longitude;

    public Geocode() {
    }

    public Geocode(float latitude, float longitude) {
        this.latitude = latitude;
        this.longitude = longitude;
    }

    public float getLatitude() {
        return latitude;
    }

    public void setLatitude(float latitude) {
        this.latitude = latitude;
    }

    public float getLongitude() {
        return longitude;
    }

    public void setLongitude(float longitude) {
        this.longitude = longitude;
    }
}

public class GeoPolygon {
    private ArrayList<Geocode> points;

    public GeoPolygon() {
        this.points = new ArrayList<Geocode>();
    }

    public GeoPolygon(ArrayList<Geocode> points) {
        this.points = points;
    }

    public GeoPolygon add(Geocode geo) {
        points.add(geo);
        return this;
    }

    public boolean inside(Geocode geo) {
        int i, j;
        boolean c = false;
        for (i = 0, j = points.size() - 1; i < points.size(); j = i++) {
            if (((points.get(i).getLongitude() > geo.getLongitude()) != (points.get(j).getLongitude() > geo.getLongitude())) &&
                    (geo.getLatitude() < (points.get(j).getLatitude() - points.get(i).getLatitude()) * (geo.getLongitude() - points.get(i).getLongitude()) / (points.get(j).getLongitude() - points.get(i).getLongitude()) + points.get(i).getLatitude()))
                c = !c;
        }
        return c;
    }

}

其他回答

下面是golang版本的@nirg答案(灵感来自于@@m-katz的c#代码)

func isPointInPolygon(polygon []point, testp point) bool {
    minX := polygon[0].X
    maxX := polygon[0].X
    minY := polygon[0].Y
    maxY := polygon[0].Y

    for _, p := range polygon {
        minX = min(p.X, minX)
        maxX = max(p.X, maxX)
        minY = min(p.Y, minY)
        maxY = max(p.Y, maxY)
    }

    if testp.X < minX || testp.X > maxX || testp.Y < minY || testp.Y > maxY {
        return false
    }

    inside := false
    j := len(polygon) - 1
    for i := 0; i < len(polygon); i++ {
        if (polygon[i].Y > testp.Y) != (polygon[j].Y > testp.Y) && testp.X < (polygon[j].X-polygon[i].X)*(testp.Y-polygon[i].Y)/(polygon[j].Y-polygon[i].Y)+polygon[i].X {
            inside = !inside
        }
        j = i
    }

    return inside
}

答案取决于你用的是简单多边形还是复杂多边形。简单多边形不能有任何线段交点。所以它们可以有洞,但线不能交叉。复杂区域可以有直线交点,所以它们可以有重叠的区域,或者只有一点相交的区域。

对于简单多边形,最好的算法是光线投射(交叉数)算法。对于复杂多边形,该算法不检测重叠区域内的点。所以对于复杂多边形你必须使用圈数算法。

下面是一篇用C实现这两种算法的优秀文章。我试过了,效果不错。

http://geomalgorithms.com/a03-_inclusion.html

令人惊讶的是之前没有人提出这个问题,但是对于需要数据库的实用主义者来说:MongoDB对Geo查询提供了出色的支持,包括这个查询。

你需要的是:

db.neighborhoods。findOne({geometry: {$geoIntersects: {$geometry: { type: "Point",坐标:["经度","纬度"]}}} })

communities是存储一个或多个标准GeoJson格式多边形的集合。如果查询返回null,则表示不相交,否则为。

这里有详细的记录: https://docs.mongodb.com/manual/tutorial/geospatial-tutorial/

在330个不规则多边形网格中,超过6000个点分类的性能不到一分钟,没有任何优化,包括用各自的多边形更新文档的时间。

下面是Rust版本的@nirg答案(Philipp Lenssen javascript版本) 我给出这个答案是因为我从这个网站得到了很多帮助,我翻译javascript版本rust作为一个练习,希望可以帮助一些人,最后一个原因是,在我的工作中,我会把这段代码翻译成一个wasm,以提高我的画布的性能,这是一个开始。我的英语很差……,请原谅我 `

pub struct Point {
    x: f32,
    y: f32,
}
pub fn point_is_in_poly(pt: Point, polygon: &Vec<Point>) -> bool {
    let mut is_inside = false;

    let max_x = polygon.iter().map(|pt| pt.x).reduce(f32::max).unwrap();
    let min_x = polygon.iter().map(|pt| pt.x).reduce(f32::min).unwrap();
    let max_y = polygon.iter().map(|pt| pt.y).reduce(f32::max).unwrap();
    let min_y = polygon.iter().map(|pt| pt.y).reduce(f32::min).unwrap();

    if pt.x < min_x || pt.x > max_x || pt.y < min_y || pt.y > max_y {
        return is_inside;
    }

    let len = polygon.len();
    let mut j = len - 1;

    for i in 0..len {
        let y_i_value = polygon[i].y > pt.y;
        let y_j_value = polygon[j].y > pt.y;
        let last_check = (polygon[j].x - polygon[i].x) * (pt.y - polygon[i].y)
            / (polygon[j].y - polygon[i].y)
            + polygon[i].x;
        if y_i_value != y_j_value && pt.x < last_check {
            is_inside = !is_inside;
        }
        j = i;
    }
    is_inside
}


let pt = Point {
    x: 1266.753,
    y: 97.655,
};
let polygon = vec![
    Point {
        x: 725.278,
        y: 203.586,
    },
    Point {
        x: 486.831,
        y: 441.931,
    },
    Point {
        x: 905.77,
        y: 445.241,
    },
    Point {
        x: 1026.649,
        y: 201.931,
    },
];
let pt1 = Point {
    x: 725.278,
    y: 203.586,
};
let pt2 = Point {
    x: 872.652,
    y: 321.103,
};
println!("{}", point_is_in_poly(pt, &polygon));// false
println!("{}", point_is_in_poly(pt1, &polygon)); // true
println!("{}", point_is_in_poly(pt2, &polygon));// true

`

这只适用于凸形状,但是Minkowski Portal Refinement和GJK也是测试一个点是否在多边形中的很好的选择。您使用闵可夫斯基减法从多边形中减去点,然后运行这些算法来查看多边形是否包含原点。

另外,有趣的是,你可以用支持函数更隐式地描述你的形状,它以一个方向向量作为输入,并输出沿该向量的最远点。这可以让你描述任何凸形状..弯曲的,由多边形制成的,或混合的您还可以执行一些操作,将简单支持函数的结果组合起来,以生成更复杂的形状。

更多信息: http://xenocollide.snethen.com/mpr2d.html

此外,game programming gems 7讨论了如何在3d中做到这一点(: