0
\$\begingroup\$

Question from the book: (Geometry: closest pair of points) Write a program that lets the user click on the panel to dynamically create points. Initially, the panel is empty. When a panel has two or more points, highlight the pair of closest points. Whenever a new point is created, a new pair of closest points is highlighted. Display the points using small circles and highlight the points using filled circles, as shown in Figure 16.26a–c. (Hint: store the points in an ArrayList.)

Solution attempt:

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.util.*;

public class ClosestPairOfPoints extends JFrame {
    private PointsPanel pointsPanel = new PointsPanel();

    public ClosestPairOfPoints() {
        add(pointsPanel);
    }
    //Main method
    public static void main(String[] args) {
        JFrame frame = new ClosestPairOfPoints();
        frame.setTitle("Exercise16_22");
        frame.setSize(300, 300);
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        frame.setLocationRelativeTo(null);
        frame.setVisible(true);
    }


    private class PointsPanel extends JPanel {
        private ArrayList<Point> points = new ArrayList<Point>();
        private int[] closestPairIndices = {2, 2};

        public PointsPanel() {
            addMouseListener(new MouseAdapter() {
                @Override
                public void mousePressed(MouseEvent e) {
                    addPoint();
                    repaint();
                }
            });
        }

        /** Add new random point **/
        public void addPoint() {
            int randomX = (int)(Math.random() * getWidth());
            int randomY = (int)(Math.random() * getHeight());

            points.add(new Point(randomX, randomY));
            if (points.size() > 1) {
                updateClosestPair();
            }
        }

        /** Alternate method **/
        private int minDistance = Integer.MAX_VALUE;
        private void updateClosestPair() {
            if (minDistance == Integer.MAX_VALUE) {     // Obtain first actual minDistance
                minDistance = getDistance(points.get(0), points.get(1));
                closestPairIndices[0] = 0;
                closestPairIndices[1] = 1;
            }
            else {      // Compare previous points with latest point
                for (int i = 0; i < points.size() - 1; i++) {
                    int testDistance = getDistance(points.get(i), points.get(points.size() - 1));
                    if (testDistance < minDistance) {
                        minDistance = testDistance;
                        closestPairIndices[0] = i;
                        closestPairIndices[1] = points.size() - 1;
                    }
                }
            }
        }


        private int getDistance(Point p1, Point p2) {
            double a = (double)Math.abs(p1.getX() - p2.getX());
            double b = (double)Math.abs(p1.getY() - p2.getY());

            return (int)Math.sqrt(a * a + b * b);
        }

        /** Paint Points from ArrayList and highlight the Points at closestPairIndices **/
        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);

            // Draw every point
            for (int i = 0; i < points.size(); i++) {
                if (i == closestPairIndices[0] || i == closestPairIndices[1]) {
                    g.fillOval((int)points.get(i).getX(), (int)points.get(i).getY(), 5, 5);
                }
                else {
                    g.drawOval((int)points.get(i).getX(), (int)points.get(i).getY(), 5, 5);
                }
            }
        }
    }
}
\$\endgroup\$
2
\$\begingroup\$

I think the logic for getting the minimal distance between the points would work even without the explicit check against MAX_INT:

private void updateClosestPair() {
    for (int i = 0; i < points.size() - 1; i++) {
        int testDistance = getDistance(points.get(i), points.get(points.size() - 1));
        if (testDistance < minDistance) {
            minDistance = testDistance;
            closestPairIndices[0] = i;
            closestPairIndices[1] = points.size() - 1;
        }
    }
}

Although I did not run the above code, I am convinced that it would just work also for the first pair (or it could be fixed with minimal changes), since it would just check the second point against the first one, and set their distance as the minimum. Going one step further, you also don't need to check that there are at least two points, when calling updateClosestPair. In this case, the iteration would never start at all.

| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ Ahh very nice, it worked out as you described. \$\endgroup\$ – Legate Aug 15 '16 at 21:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.