fork(1) download
  1. import java.util.Arrays;
  2. import java.util.List;
  3.  
  4. class LineSegment {
  5. public static class Point {
  6. public final double x;
  7. public final double y;
  8.  
  9. public Point(double x, double y) {
  10. this.x = x;
  11. this.y = y;
  12. }
  13.  
  14. public String toString() {
  15. return "(" + x + "," + y + ")";
  16. }
  17. }
  18.  
  19. public static void main(String[] args) {
  20. LineSegment segment = new LineSegment(new Point(0, 3), new Point(2, 0));
  21. List<Point> pointList =
  22. Arrays.asList(new Point[] { new Point(-5, 3), new Point(1, 1),
  23. new Point(2, 3), new Point(0, 5) });
  24.  
  25. Point answer = segment.closestPoint(pointList);
  26. System.out.println("The closest point is: " + answer);
  27. }
  28.  
  29. private static double sqr(double x) {
  30. return x * x;
  31. }
  32.  
  33. private static double distanceSquared(Point v, Point w) {
  34. return sqr(v.x - w.x) + sqr(v.y - w.y);
  35. }
  36.  
  37. private final Point firstSegPoint;
  38. private final Point secondSegPoint;
  39. private final double segmentDistance;
  40. private double xDifference;
  41. private double yDifference;
  42.  
  43. public LineSegment(Point firstSegPoint, Point secondSegPoint) {
  44. this.firstSegPoint = firstSegPoint;
  45. this.secondSegPoint = secondSegPoint;
  46. this.segmentDistance = distanceSquared(firstSegPoint, secondSegPoint);
  47. this.xDifference = secondSegPoint.x - firstSegPoint.x;
  48. this.yDifference = secondSegPoint.y - firstSegPoint.y;
  49. }
  50.  
  51. public Point closestPoint(List<Point> pointList) {
  52. double minDistance = Double.POSITIVE_INFINITY;
  53. Point answer = null;
  54.  
  55. for (Point point : pointList) {
  56. double distSquared = distToSegmentSquared(point);
  57. if (distSquared < minDistance) {
  58. answer = point;
  59. minDistance = distSquared;
  60. }
  61. }
  62.  
  63. return answer;
  64. }
  65.  
  66. private double distToSegmentSquared(Point input) {
  67. if (segmentDistance == 0)
  68. return distanceSquared(input, firstSegPoint);
  69.  
  70. double xComponent = (input.x - firstSegPoint.x) * xDifference;
  71. double yComponent = (input.y - firstSegPoint.y) * yDifference;
  72. double t = (xComponent + yComponent) / segmentDistance;
  73. if (closestPointIsFirst(t))
  74. return distanceSquared(input, firstSegPoint);
  75. if (closestPointIsSecond(t))
  76. return distanceSquared(input, secondSegPoint);
  77. Point closestPointOnLine =
  78. new Point(firstSegPoint.x + t * xDifference, firstSegPoint.y
  79. + t * yDifference);
  80. return distanceSquared(input, closestPointOnLine);
  81. }
  82.  
  83. private boolean closestPointIsFirst(double t) {
  84. return t < 0;
  85. }
  86.  
  87. private boolean closestPointIsSecond(double t) {
  88. return t > 1;
  89. }
  90. }
  91.  
  92.  
Success #stdin #stdout 0.11s 320256KB
stdin
Standard input is empty
stdout
The closest point is: (1.0,1.0)