最近参与一个室内AP定位的项目做Android客户端的开发。
自己写了一个静态地图控件,遇到了需要判断触摸点是否位于多边形指定区域内的问题。
网上资料很多,主流方法是利用光投射算法。Point in polygon - Wikipedia
CSDN上有一篇文章把原理讲的非常详细 点在多边形内算法——判断一个点是否在一个复杂多边形的内部
参考 StackOverFlow 上一个回答的写法,翻译成 JAVA 如下:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 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 类里。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 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); } 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; } }