判断点与不规则多边形的位置关系
程序员文章站
2024-03-16 19:46:22
...
判断点与不规则多边形的位置关系可以有多种方式,这里采用射线法结合边界条件判断
原理参照https://wenku.baidu.com/view/5e3913a2b0717fd5360cdccf.html
实体类
public class Point{
/**
* x轴坐标
*/
double x;
/**
* y轴坐标
*/
double y;
public Point setPoint(Point point){
this.x = point.getX();
this.y = point.getY();
return this;
}
public Point() {
}
public Point(Float[] point){
this.x = point[0];
this.y = point[1];
}
public Point(Double[] point) {
this.x = point[0];
this.y = point[1];
}
public Point(double x, double y) {
this.x = x;
this.y = y;
}
public double getX() {
return x;
}
public void setX(double x) {
this.x = x;
}
public double getY() {
return y;
}
public void setY(double y) {
this.y = y;
}
}
工具类
import java.util.ArrayList;
import java.util.List;
public class GeometryUtil {
/**
* 判断点是否在多边形内
*
* @param point
* 检测点
* @param pts
* 多边形的顶点
* @return 点在多边形内返回true,否则返回false
*/
public static boolean IsPointInPolygon(Point point, List<Point> pts) {
int N = pts.size();
boolean boundOrVertex = true; // 边际条件判断,如果点位于多边形的顶点或边上,也算做点在多边形内,直接返回true
int intersectCount = 0;// cross points count of x
double precision = 2e-10; // 浮点类型计算时候与0比较时候的容差
Point p1, p2;// neighbour bound vertices
Point p = point; // 当前点
p1 = pts.get(0);// left vertex
for (int i = 1; i <= N; ++i) {// check all rays
if (p.equals(p1)) {
return boundOrVertex;// p is an vertex
}
p2 = pts.get(i % N);// right vertex
if (p.x < Math.min(p1.x, p2.x) || p.x > Math.max(p1.x, p2.x)) {
p1 = p2;
continue;// next ray left point
}
if (p.x > Math.min(p1.x, p2.x) && p.x < Math.max(p1.x, p2.x)) {
if (p.y <= Math.max(p1.y, p2.y)) {// x is before of ray
if (p1.x == p2.x && p.y >= Math.min(p1.y, p2.y)) {
return boundOrVertex;
}
if (p1.y == p2.y) {
if (p1.y == p.y) {
return boundOrVertex;
} else {// before ray
++intersectCount;
}
} else {// cross point on the left side
double xinters = (p.x - p1.x) * (p2.y - p1.y)
/ (p2.x - p1.x) + p1.y;// cross point of y
if (Math.abs(p.y - xinters) < precision) {
return boundOrVertex;
}
if (p.y < xinters) {// before ray
++intersectCount;
}
}
}
} else {
if (p.x == p2.x && p.y <= p2.y) {// p crossing over p2
Point p3 = pts.get((i + 1) % N); // next vertex
if (p.x >= Math.min(p1.x, p3.x)
&& p.x <= Math.max(p1.x, p3.x)) {
++intersectCount;
} else {
intersectCount += 2;
}
}
}
p1 = p2;// next ray left point
}
//交点数为偶数即在内部,否则是外部
return intersectCount % 2 == 0;
}
}
上一篇: 逐边裁剪法实现多边形裁剪