当前位置:   article > 正文

java-边界线查找-离散点最小(凸)包围边界查找_java 将最外围的点连接起来

java 将最外围的点连接起来

 就是一堆散点,需要把最外侧点链接起来成为一个多边形

先看效果图:有很多无序的点,把最外侧点链接起来成为一个多边形


效果图

最近,项目中有一需求,需要用一条闭合曲线将离散坐标点勾勒出来
根据Darel Rex Finley的程序,其实现了最小凸多边形边界查找(关于凸多边形及凹多边形的定义见 凸多边形 及 凹多边形

以下介绍java版的实现过程

离散点

首先建立离散点类:

  1. /**
  2. * <p>
  3. * <b>离散点</b>
  4. * <p>
  5. * <pre>
  6. * 离散点
  7. * </pre>
  8. *
  9. * @author ManerFan 2015年4月10日
  10. */
  11. public class Point {
  12. /**
  13. * x坐标
  14. */
  15. private double x;
  16. /**
  17. * y坐标
  18. */
  19. private double y;
  20. /**
  21. * 边界查找算法中 是否被找到
  22. */
  23. boolean founded = false;
  24. public Point() {
  25. }
  26. public Point(double x, double y) {
  27. this.x = x;
  28. this.y = y;
  29. }
  30. public double getX() {
  31. return x;
  32. }
  33. public void setX(double x) {
  34. this.x = x;
  35. }
  36. public double getY() {
  37. return y;
  38. }
  39. public void setY(double y) {
  40. this.y = y;
  41. }
  42. @Override
  43. public String toString() {
  44. return "(" + x + ", " + y + ")";
  45. }
  46. @Override
  47. public int hashCode() {
  48. final int prime = 31;
  49. int result = 1;
  50. long temp;
  51. temp = Double.doubleToLongBits(x);
  52. result = prime * result + (int) (temp ^ (temp >>> 32));
  53. temp = Double.doubleToLongBits(y);
  54. result = prime * result + (int) (temp ^ (temp >>> 32));
  55. return result;
  56. }
  57. @Override
  58. public boolean equals(Object obj) {
  59. if (this == obj)
  60. return true;
  61. if (obj == null)
  62. return false;
  63. if (getClass() != obj.getClass())
  64. return false;
  65. Point other = (Point) obj;
  66. if (Double.doubleToLongBits(x) != Double.doubleToLongBits(other.x))
  67. return false;
  68. if (Double.doubleToLongBits(y) != Double.doubleToLongBits(other.y))
  69. return false;
  70. return true;
  71. }
  72. }

离散点操作工具类

为更方便的实现算法,创建离散点操作工具类:

  1. /**
  2. * <p>
  3. * <b>离散点计算工具</b>
  4. * <p>
  5. * <pre>
  6. * 离散点计算工具
  7. *
  8. * y
  9. * ↑ · ·
  10. * │ · · ·
  11. * │ · · · ·
  12. * │ · ·
  13. * —│————————————→ x
  14. * </pre>
  15. *
  16. * @author ManerFan 2015年4月9日
  17. */
  18. public class DiscretePointUtil {
  19. /**
  20. * <p>
  21. * <b>查找离散点集中的(min_x, min_Y) (max_x, max_Y)</b>
  22. * <p>
  23. * <pre>
  24. * 查找离散点集中的(min_x, min_Y) (max_x, max_Y)
  25. * </pre>
  26. *
  27. * @author ManerFan 2015年4月9日
  28. * @param points 离散点集
  29. * @return [(min_x, min_Y), (max_x, max_Y)]
  30. */
  31. public static Point[] calMinMaxDots(final List<Point> points) {
  32. if (null == points || points.isEmpty()) {
  33. return null;
  34. }
  35. double min_x = points.get(0).getX(), max_x = points.get(0).getX();
  36. double min_y = points.get(0).getY(), max_y = points.get(0).getY();
  37. /* 这里存在优化空间,可以使用并行计算 */
  38. for (Point point : points) {
  39. if (min_x > point.getX()) {
  40. min_x = point.getX();
  41. }
  42. if (max_x < point.getX()) {
  43. max_x = point.getX();
  44. }
  45. if (min_y > point.getY()) {
  46. min_y = point.getY();
  47. }
  48. if (max_y < point.getY()) {
  49. max_y = point.getY();
  50. }
  51. }
  52. Point ws = new Point(min_x, min_y);
  53. Point en = new Point(max_x, max_y);
  54. return new Point[] { ws, en };
  55. }
  56. /**
  57. * <p>
  58. * <b>求矩形面积平方根</b>
  59. * <p>
  60. * <pre>
  61. * 以两个点作为矩形的对角线上的两点,计算其面积的平方根
  62. * </pre>
  63. *
  64. * @author ManerFan 2015年4月9日
  65. * @param ws 西南点
  66. * @param en 东北点
  67. * @return 矩形面积平方根
  68. */
  69. public static double calRectAreaSquare(Point ws, Point en) {
  70. if (null == ws || null == en) {
  71. return .0;
  72. }
  73. /* 为防止计算面积时float溢出,先计算各边平方根,再相乘 */
  74. return Math.sqrt(Math.abs(ws.getX() - en.getX()))
  75. * Math.sqrt(Math.abs(ws.getY() - en.getY()));
  76. }
  77. /**
  78. * <p>
  79. * <b>求两点之间的长度</b>
  80. * <p>
  81. * <pre>
  82. * 求两点之间的长度
  83. * </pre>
  84. *
  85. * @author ManerFan 2015年4月10日
  86. * @param ws 西南点
  87. * @param en 东北点
  88. * @return 两点之间的长度
  89. */
  90. public static double calLineLen(Point ws, Point en) {
  91. if (null == ws || null == en) {
  92. return .0;
  93. }
  94. if (ws.equals(en)) {
  95. return .0;
  96. }
  97. double a = Math.abs(ws.getX() - en.getX()); // 直角三角形的直边a
  98. double b = Math.abs(ws.getY() - en.getY()); // 直角三角形的直边b
  99. double min = Math.min(a, b); // 短直边
  100. double max = Math.max(a, b); // 长直边
  101. /**
  102. * 为防止计算平方时float溢出,做如下转换
  103. * √(min²+max²) = √((min/max)²+1) * abs(max)
  104. */
  105. double inner = min / max;
  106. return Math.sqrt(inner * inner + 1.0) * max;
  107. }
  108. /**
  109. * <p>
  110. * <b>求两点间的中心点</b>
  111. * <p>
  112. * <pre>
  113. * 求两点间的中心点
  114. * </pre>
  115. *
  116. * @author ManerFan 2015年4月10日
  117. * @param ws 西南点
  118. * @param en 东北点
  119. * @return 两点间的中心点
  120. */
  121. public static Point calCerter(Point ws, Point en) {
  122. if (null == ws || null == en) {
  123. return null;
  124. }
  125. return new Point(ws.getX() + (en.getX() - ws.getX()) / 2.0, ws.getY()
  126. + (en.getY() - ws.getY()) / 2.0);
  127. }
  128. /**
  129. * <p>
  130. * <b>计算向量角</b>
  131. * <p>
  132. * <pre>
  133. * 计算两点组成的向量与x轴正方向的向量角
  134. * </pre>
  135. *
  136. * @author ManerFan 2015年4月17日
  137. * @param s 向量起点
  138. * @param d 向量终点
  139. * @return 向量角
  140. */
  141. public static double angleOf(Point s, Point d) {
  142. double dist = calLineLen(s, d);
  143. if (dist <= 0) {
  144. return .0;
  145. }
  146. double x = d.getX() - s.getX(); // 直角三角形的直边a
  147. double y = d.getY() - s.getY(); // 直角三角形的直边b
  148. if (y >= 0.) { /* 1 2 象限 */
  149. return Math.acos(x / dist);
  150. } else { /* 3 4 象限 */
  151. return Math.acos(-x / dist) + Math.PI;
  152. }
  153. }
  154. /**
  155. * <p>
  156. * <b>修正角度</b>
  157. * <p>
  158. * <pre>
  159. * 修正角度到 [0, 2PI]
  160. * </pre>
  161. *
  162. * @author ManerFan 2015年4月17日
  163. * @param angle 原始角度
  164. * @return 修正后的角度
  165. */
  166. public static double reviseAngle(double angle) {
  167. while (angle < 0.) {
  168. angle += 2 * Math.PI;
  169. }
  170. while (angle >= 2 * Math.PI) {
  171. angle -= 2 * Math.PI;
  172. }
  173. return angle;
  174. }
  175. }

边界查找算法
算法的实现思路,简要如下

找到离散点中,保证y坐标最大的情况下,x坐标最小的点,记做A点
以A点为原点,x轴正反向射线(Ax−→Ax→)顺时针扫描,找到旋转角最小时扫描到的点,记做B点
以B点为原点,AB方向射线(AB−→−AB→)顺时针扫描,找到旋转角最小时扫描到的点,记做C点
以C点为原点,BC方向射线(BC−→−BC→)顺时针扫描,找到旋转角最小时扫描到的点,记做D点
以此类推,直到找到起始点A
思路图,简要如下


1
2
3
n

实现程序见下:

  1. /**
  2. * <p>
  3. * <b>最小(凸)包围边界查找</b>
  4. * <p>
  5. * <pre>
  6. * 最小(凸)包围边界查找
  7. *
  8. * Minimum Bounding Polygon (Convex Hull; Smallest Enclosing A Set of Points)
  9. * <b><a href="http://alienryderflex.com/smallest_enclosing_polygon/">©2009 Darel Rex Finley.</a></b>
  10. *
  11. * y
  12. * ↑ · ·
  13. * │ · · ·
  14. * │ · · · ·
  15. * │ · ·
  16. * —│————————————→ x
  17. *
  18. * </pre>
  19. *
  20. * @author ManerFan 2015年4月17日
  21. */
  22. public class MinimumBoundingPolygon {
  23. public static LinkedList<Point> findSmallestPolygon(List<Point> ps) {
  24. if (null == ps || ps.isEmpty()) {
  25. return null;
  26. }
  27. Point corner = findStartPoint(ps);
  28. if (null == corner) {
  29. return null;
  30. }
  31. double minAngleDif, oldAngle = 2 * Math.PI;
  32. LinkedList<Point> bound = new LinkedList<>();
  33. do {
  34. minAngleDif = 2 * Math.PI;
  35. bound.add(corner);
  36. Point nextPoint = corner;
  37. double nextAngle = oldAngle;
  38. for (Point p : ps) {
  39. if (p.founded) { // 已被加入边界链表的点
  40. continue;
  41. }
  42. if (p.equals(corner)) { // 重合点
  43. /*if (!p.equals(bound.getFirst())) {
  44. p.founded = true;
  45. }*/
  46. continue;
  47. }
  48. double currAngle = DiscretePointUtil.angleOf(corner, p); /* 当前向量与x轴正方向的夹角 */
  49. double angleDif = DiscretePointUtil.reviseAngle(oldAngle - currAngle); /* 两条向量之间的夹角(顺时针旋转的夹角) */
  50. if (angleDif < minAngleDif) {
  51. minAngleDif = angleDif;
  52. nextPoint = p;
  53. nextAngle = currAngle;
  54. }
  55. }
  56. oldAngle = nextAngle;
  57. corner = nextPoint;
  58. corner.founded = true;
  59. } while (!corner.equals(bound.getFirst())); /* 判断边界是否闭合 */
  60. return bound;
  61. }
  62. /** 查找起始点(保证y最大的情况下、尽量使x最小的点) */
  63. private static Point findStartPoint(List<Point> ps) {
  64. if (null == ps || ps.isEmpty()) {
  65. return null;
  66. }
  67. Point p = ps.get(0);
  68. ListIterator<Point> iter = ps.listIterator();
  69. while (iter.hasNext()) {
  70. Point point = iter.next();
  71. if (point.getY() > p.getY() || (point.getY() == p.getY() && point.getX() < p.getX())) { /* 找到最靠上靠左的点 */
  72. p = point;
  73. }
  74. }
  75. return p;
  76. }
  77. }

结合上边的几张图,相比不难看懂
以下附上一张实际效果图:

效果图

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Gausst松鼠会/article/detail/333177
推荐阅读
相关标签
  

闽ICP备14008679号