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

A few thousand method calls take something in the order of 10 micro seconds on a contemporary computer, which is definitely not a human-noticable delay, let alone "really slow".

The reason for your performance problem must therefore be elsewhere - presumably in the repaint(), which causes the container's paint() to be invoked. If this draws a few 1000 circles, this might well take nearly a second.

This is why, before optimizing, you should always measure where your performance bottleneck actually is.

Answer 2

Iterating over your entire set of circles for every call to mouseDragged is an incredible waste of time. One option you have is to take the lead from JTable and develop methods that will allow you to identify the row and column at the point contained in your MouseEvent. If you know widths of your columns and heights of your rows, it shouldn't be that difficult to identify the cell for your circle.

Answer 3

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)

Answer 4

This example features moveable, resizable, colored nodes that can be selected by dragging a boundary rectangle. The implementation highlights selected nodes by displaying a rectangular border. In the picture below, the green and black nodes have been selected. Altering color instead would be a simple change to the draw() method of Node.