Finding nearest points and points within a radius

Question

I have implemented the following two methods which are described in 1. and 2..

Is there another better simpler way to implements those methods?

1. A static method, nearestPoint , accepts an array of points (objects of type Point ) and one point (an object of type Point), and returns that point in the array which is closest to the given point. Create that method.

2. A circle in the plane, with radius \$r\$ and midpoint at the origin, is given by the following equation: \$x^2 + y^2 = r^2\$

   A static method, internalPoints , accepts an array of points (objects of type Point) and the radius of a circle, and returns those points (in an array) that are inside the given circle. Create that method.

3. Create an array of points (objects of type Point) and a point (an object of type Point). Establish also the radius of the circle.
   Use the method nearestPoint to determine the point in the array that is closest to the given point. Then use the method internalPoints to determine the points that are inside the circle.

public class Point {
// the coordinates of the point
private double x;
private double y;

public Point(double x, double y) {
    this.x = x;
    this.y = y;
}

public double getX() {
    return this.x;
}

public double getY() {
    return this.y;
}

// distance returns the distance between this point and a given point
public double distance(Point p) {
    return Math.sqrt((p.x - this.x) * (p.x - this.x) +
            (p.y - this.y) * (p.y - this.y));
}

public String toString() {
    String s = "";
    //for (int i = 0; i < s.length(); i++) {
    s = "(" + this.getX() + "," + this.getY() + ")";

    return s;
}

public static Point nearestPoint(Point[] points, Point point) {
    Point p = points[0];
    for (int i = 0; i < points.length; i++) {
        if (points[i].distance(point) < p.distance(point)) {
            p = points[i];
        }
    }
    return p;
}

public static Point[] internalPoints(Point[] points, double radius) {

    int countPoints = 0;
    for (int i = 0; i < points.length; i++) {
        double xp = points[i].getX();
        double yp = points[i].getY();
        // points are inside the circle if d^2 <= r^2
        // d^2 = (Xp-Xc)^2 + (Yp-Yc)^2
        // Xp and Yp is the point that should be checked
        // Xc and Xc is the point center (orgin)
        // Xc and Yc are 0 you end up with d^2 = (Xp-Xc)^2 + (Yp-Yc)^2
        if (xp * xp + yp * yp <= radius * radius) {
            countPoints++;
        }
    }
    int companionVar = 0;
    Point[] pointsInside = new Point[countPoints];
    for (int j = 0; j < countPoints; j++) {
        pointsInside[companionVar] = points[j];
        companionVar++;
    }
    return pointsInside;

}

public static void main(String[] args) {
    Point[] points = {new Point(1, 2),
            new Point(2, 3),
            new Point(5, 2)};
    new Point(12, 13); // points outside the circle
    Point point = new Point(1, 1);
    double r = 7;
    Point nearestPoint = nearestPoint(points, point);
    Point[] internalPoints = internalPoints(points, 7);

    System.out.println(nearestPoint + "   " + Arrays.toString(internalPoints));
}

}

Answer 1

Bug

The internalPoints method has a bug: you count the number of points that fall within the radius, but then, instead of adding those points in the output array, you take the first N points of the input array, some of which may not be within the radius. Try for example with this input:

Point[] points = {
        new Point(1, 2),
        new Point(19, 29),
        new Point(2, 3),
        new Point(5, 2)
};

Comparing distances

Do you really need to compare \$\sqrt{dx^2 + dy^2}\$ ? Computing the square root can be expensive, and comparing \$dx^2 + dy^2\$ would be enough.

public double dsquare(Point p) {
    double dx = p.x - this.x;
    double dy = p.y - this.y;
    return dx * dx + dy * dy;
}

Finding the nearest point

In this loop, the distance between point and the nearest point may be repeatedly recalculated:

Point p = points[0];
for (int i = 0; i < points.length; i++) {
    if (points[i].distance(point) < p.distance(point)) {
        p = points[i];
    }
}
return p;

You could save the known nearest distance in a variable to avoid repeated computations. Also, you could start iterating from i = 1 instead of i = 0:

Point nearest = points[0];
double nearestDistance = point.dsquare(nearest);
for (int i = 1; i < points.length; i++) {
    double distance = points[i].dsquare(point);
    if (distance < nearestDistance) {
        nearest = points[i];
        nearestDistance = distance;
    }
}
return nearest;

Simplify

The s variable in toString is pointless, you could directly return the concatenated value.

Answer 2

a) A static method, nearestPoint , accepts an array of points (objects of type Point ) and one point (an object of type Point ), and returns that point in the array which is closest to the given point. Create that method.

It would be better to have it as non-static method, like this:

Point nearestPoint = new Point(0, 0).nearest(points);

---

A static method, internalPoints , accepts an array of points (objects of type Point ) and the radius of a circle, and returns those points (in an array) that are inside the given circle. Create that method.

That method name doesn't make any sense.

---

// the coordinates of the point
...
// distance returns the distance between this point and a given point

Javadoc, Javadoc, Javadoc.

---

public double getX() {
    return this.x;
}

You don't need this here (and most other places). Only use this if the variable is ambiguous (like in the constructor).

---

Point is supposed to be an immutable container, so consider making it final.

---

public String toString() {
    String s = "";
    //for (int i = 0; i < s.length(); i++) {
    s = "(" + this.getX() + "," + this.getY() + ")";

    return s;
}

Let's ignore that commented out line that doesn't make any sense (why is it still there?). Given that your class immutable, you should consider caching the String. "Normally", the String representation would look like this:

Point[x=0,y=0]

But if you want to get fancy, you can also throw the System.identityHash in there:

Point@12345[x=0,y=0]

Some advice, favor getClass().getSimpleName() to get the name of the class instead of hardcoding it, saves you some headache if you start renaming classes.

---

public static Point nearestPoint(Point[] points, Point point) {
    Point p = points[0];
    for (int i = 0; i < points.length; i++) {
        if (points[i].distance(point) < p.distance(point)) {
            p = points[i];
        }
    }
    return p;
}

Okay, here is a simple rule naming variables:

Name variables after what they contain. You are never, ever, with the exception of dimensions (x, y, z), for whatever reason allowed to use a single character as variable name.

Also, a perfect example for using a foreach loop.

Calculating the distance is a rather expensive operation, you should cache the result. Imagine you have 10,000 points with the first one being the closest, you will calculate the distance for that first point 10,000 times.

Blank lines around the loop would make the function much easier to read.

---

I have no idea what you're doing inside internalPoints, are you really looking for the count of how many points are inside the circle, and then you return the first x points? I don't think that works.

Also, List and ArrayList make it easy to build lists, and you can create an array from them.

---

new Point(12, 13); // points outside the circle

You're never assigning that Point to anywhere.

---

double r = 7;
Point nearestPoint = nearestPoint(points, point);
Point[] internalPoints = internalPoints(points, 7);

You are creating a variable for the radius just to ignore it.

---

Your variable names and whitespace handling must get better, otherwise its a good start.