为了完整起见,在这里我想做几个注释:
从API 19开始,路径有一个交集操作。您可以在测试点周围创建一个非常小的正方形路径,将其与路径相交,并查看结果是否为空。
您可以将路径转换为区域并执行包含()操作。但是,区域使用整数坐标,并且我认为它们使用变换后的(像素)坐标,因此您必须处理这些内容。我还怀疑转换过程计算密集。
Hans发布的边界穿越算法很好且快速,但是您必须非常小心,以避免某些角落情况,例如光线直接通过顶点、相交水平边缘或舍入误差成为问题时,这总是存在的。
绕数方法非常可靠,但涉及大量三角函数计算,计算成本高。
Dan Sunday的这篇论文提供了一种混合算法,与绕数一样准确,但计算简单,类似于射线投射算法。它的优雅之处让我惊叹不已。
我的代码
这是我最近用Java编写的一些代码,用于处理由线段和圆弧组成的路径。(还有圆,但那些是自成一体的完整路径,所以这是一种退化情况。)
package org.efalk.util;
public class PathUtil {
static final double RAD = (Math.PI/180.);
static final double DEG = (180./Math.PI);
protected static final int LINE = 0;
protected static final int ARC = 1;
protected static final int CIRCLE = 2;
public static class PathElement {
public int type;
public float x0,y0,x1,y1;
public float a0,a1;
}
public static boolean inside(float x, float y, PathElement[] path) {
int wn = 0;
for (PathElement pe : path) {
switch (pe.type) {
case LINE:
if (pe.x0 < x && pe.x1 < x)
break;
if (pe.y0 <= y) {
if (pe.y1 > y) {
if (isLeft(pe, x, y) > 0)
++wn;
}
}
else {
if (pe.y1 <= y) {
if (isLeft(pe, x, y) < 0)
--wn;
}
}
break;
case ARC:
wn += arcCrossing(pe, x, y);
break;
case CIRCLE:
float rx = (pe.x1-pe.x0)/2;
float ry = (pe.y1-pe.y0)/2;
float xc = (pe.x1+pe.x0)/2;
float yc = (pe.y1+pe.y0)/2;
return (x-xc)*(x-xc)/rx*rx + (y-yc)*(y-yc)/ry*ry <= 1;
}
}
return wn != 0;
}
private static float
isLeft(float x0, float y0, float x1, float y1, float x, float y)
{
return (x1 - x0) * (y - y0) - (x - x0) * (y1 - y0);
}
private static float isLeft(PathElement pe, float x, float y) {
return isLeft(pe.x0,pe.y0, pe.x1,pe.y1, x,y);
}
private static int arcCrossing(PathElement pe, float x, float y) {
if (pe.x1 < x || pe.y1 < y || pe.y0 > y) return 0;
float rx = (pe.x1-pe.x0)/2;
float ry = (pe.y1-pe.y0)/2;
float xc = (pe.x1+pe.x0)/2;
float yc = (pe.y1+pe.y0)/2;
if (rx == 0 || ry == 0) return 0;
if (rx < 0) rx = -rx;
if (ry < 0) ry = -ry;
x -= xc;
y -= yc;
if (x > rx || y > ry || y < -ry) return 0;
x /= rx;
y /= ry;
double x0 = 1 - y*y;
if (x0 <= 0) return 0;
x0 = Math.sqrt(x0);
if (x > x0) return 0;
int wn = arcXing1(x0,y, pe.a0, pe.a1);
if (x < -x0) wn -= arcXing1(-x0,y, pe.a0, pe.a1);
return wn;
}
private static int arcXing1(double x, float y, float a0, float a1) {
double a = Math.atan2(y,x) * DEG;
if (a < 0) a += 360;
if (a1 > 0) {
if (a < a0) a += 360;
return a0 + a1 > a ? 1 : 0;
} else {
if (a0 < a) a0 += 360;
return a0 + a1 <= a ? -1 : 0;
}
}
}
编辑:按照要求,添加一些使用此功能的示例代码。
import PathUtil;
import PathUtil.PathElement;
public class Area {
public float lat0, lon0, lat1, lon1;
Path path = null;
PathElement[] pathList;
public boolean pointInBounds(float lat, float lon) {
if (lat < lat0 || lat > lat1 || lon < lon0 || lon > lon1)
return false;
return PathUtil.inside(lon, lat, pathList);
}
static void loadBounds() {
int n = number_of_elements_in_input;
path = new Path();
pathList = new PathElement[n];
for (Element element : elements_in_input) {
PathElement pe = new PathElement();
pathList[i] = pe;
pe.type = element.type;
switch (element.type) {
case LINE:
pe.x0 = element.x0;
pe.y0 = element.y0;
pe.x1 = element.x1;
pe.y1 = element.y1;
break;
case ARC:
pe.x0 = element.xmin;
pe.y0 = element.ymin;
pe.x1 = element.xmax;
pe.y1 = element.ymax;
pe.a0 = a0; pe.a1 = a1;
break;
case CIRCLE:
pe.x0 = element.xmin;
pe.y0 = element.ymin;
pe.x1 = element.xmax;
pe.y1 = element.ymax;
break;
}
}
path.close();
}