circle packing - java

Question

I have a task to draw a circle and then fill in with the most amount of circles without touching the sides. I can draw the circle, and I can make loops to pack the circle in a hexagonal/honeycomb format, but can't control whether they are inside or outside the circle.

I have used this: g.drawOval(50, 50, 300, 300); to specify my circle. Given I'm actually specifying a square as my boundaries I can't actually determine where the circle boundaries are. So I'm basically packing the square full of circles rather than the circle full of circles.

Can some please point me in the right direction? I'm new to java so not sure if I have done this the complete wrong way. My code is below. I have another class for the frame and another with the main in it.

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

class DrawCircle extends JPanel
{
    private int width, height, diameter;
    public DrawFrame d;

    public DrawCircle()
    {
     width = 400;
     height = 400;
     diameter = 300;
    }


    public void paintComponent(Graphics g)
    {
     super.paintComponent(g);
     g.setColor(Color.blue);
     g.drawOval(50, 50, 300, 300);

     for(int i=50; i<200; i=i+20)
     {
      for(int j=50; j<350; j=j+10)
      {
       g.drawOval(j, i, 10, 10);
      }
     }

     for(int i=60; i<200; i=i+20)
     {
      for(int j=55; j<350; j=j+10)
      {
       g.drawOval(j, i, 10, 10);
      }
     }

     for(int i=330; i>190; i=i-20)
     {
      for(int j=340; j>40; j=j-10)
      {
       g.drawOval(j, i, 10, 10);
      }
     }

     for(int i=340; i>190; i=i-20)
     {
      for(int j=345; j>40; j=j-10)
      {
       g.drawOval(j, i, 10, 10);
      }
     }




    }
}

Answer 1

All those magic numbers make me cringe a bit. You're new to Java, and it's homework, so I understand why you're doing it, but I would not recommend it if you do much programming in the future.

You need an algorithm or recipe for deciding when a small circle on the inside falls outside the big one you're trying to pack. Think about the ways you might do this:

1. If the distance between the center of the big circle and the small circle is is greater than the difference in their radii, the small circle will overlap the big circle or fall completely outside it.

You can add this check to your code: Just before you draw the circle, perform this check. Only draw if that circle passes.

Don't worry about Java for a second; draw yourself a picture on a piece of paper, draw that enclosing and packed circle, and see if that statement is correct. Then think about any corner situations that it might not cover, just as a check.

I'll make two more recommendations. First, do this by hand without a computer once so you'll see what the "right" answer might look like. Second, see if you can separate the calculation of the circles from the drawing part. It might make your job easier, because you can concentrate on one thing at a time. It's called "decomposition". You solve complex problems by breaking them up into smaller, more manageable pieces. In this case, it's also called "model-view separation". You might need to know that someday.

Maybe another way to think about this problem would be to imagine a 2D arrangement of circles, packed in their closest arrangement, extending to infinity in both the x- and y-directions. Now take your enclosing circle, put it on top of the 2D arrangement, and eliminate all the circles that overlap the big circle. I don't know if it'll be optimal, but it's easy to visualize.