Efficient way of locating and/or selecting graphic object in a fixed grid

Question

I have a panel that is filled with a large number of circles (Ellipse2D). The circles are stored in a 2 dimensional array (rows and columns).

My goal is to be able to "paint" the circles as I drag the mouse over them. I will eventually want to use selection shapes that will change the color of all the circles contained within the selection shape.

I'm using a mouse dragging listener that continually scans the entire 2d array and checks is the current point is inside on of the circles. Like so:

        addMouseMotionListener(new MouseAdapter() {

        public void mouseDragged(MouseEvent e) {

            currentColor = ColorSliderPanel.getRGB();

            for (int x = 0; x < numColumns; x++) {
                for (int y = 0; y < numRows; y++) {
                    if (circle[x][y].contains(e.getX(), e.getY())) {

                        circle[x][y].setColor(currentColor);
                        repaint();
                    }
                }
            }

        }
    });

The above code works, but it's really slow (1000+ circles), as it is checking every single object.

There must be a better way. I've read a little about a Quadtree, but I'm not sure if a quadtree is more horsepower than I need.

Thanks

I made the following changes based on some of the comments below. Circles is now a linear ArrayList. The draw method simply fill the circle. Making this change improved the speed by two orders of magnitude. It works much better now. Although, I can still sweep across the panel with moderate speed and miss a few circles. So I may need to optimize futher.

  Graphics2D g2d = (Graphics2D) getGraphics();

            for (Circle2D c : circles) {
                if (c.contains(p)) {
                    c.setColor(currentColor);
                   //Graphics2D g2d = (Graphics2D) getGraphics(); (moved)
                    c.draw(g2d);
                }
            }

Answer 1

The way I'd personally do this is so:

• make a linear array of circles (or a linked list, your choice).
• in your event listener you iterate linearly over the array, hit testing every circle against your mouse position, and if the test passes, you change the color
• here's the biggest optimization: since we're talking about drawing with a fairly high frequency (every mouse movement), you want to determine what circles have to be redrawn. As you're iterating over the array above, keep a running count of the biggest bounding box that has to be changed (a rectangle that surrounds every circle that has to be redrawn)
• now you delete the rectangle calculated above and iterate over the circles again, drawing only the circles that are inside the rectangle (potentially cutting off certain bits of circles, but drawing everything that fits inside the rectangle and not touching the outside).

Note: Iterating over 1k+ circles twice will be almost instantaneous, your real problem is in the drawing of the circles (and your weird x/y storage mechanism). Graphics I/O is and always will be slow, especially the Java way of doing it.

A further optimization is to create a memory bitmap and draw your rectangle in there, then blit it all at once on your main surface, to further reduce flicker (which are caused by slow redraw passes at every update)