Drawing Non-Intersecting Circles

Drawing non-intersecting circles

Set the aspect ratio via asp:

diam <- sqrt (2)
plot (c(-1,1), c(1,-1), xlim=c(-3,3), ylim=c(-3,3), asp=1)
symbols (c(-1,1), c(1,-1), circles=c(diam,diam), add=TRUE, inches=FALSE)

Updated to add Gavin Simpson's excellent insights from the comments and chat. My answer may be correct, but Gavin provides the very helpful reasons why asp=1 works and why it isn't the default behavior. Many thanks to him.

The default plotting device settings attempt to display the data without assuming anything about the scale of the relationship between the variables. To directly quote Gavin:

The reason asp = 1 is not the
default is that asp = 1 doesn't make
sense for data that do not share a
common unit of measurement, such as
height vs weight. Why should a change
of 1m in height be represented as a
change of 1kg in weight?

and

As a result, distance along the x axis
bears no relationship to those on the
y axis. As such, what is plotted is a
transformation of real circles - they
really are circles, just translated
because the coordinate system you are
plotting them into isn't appropriate.

A way to illustrate Gavin's points would be to plot the circles on the default device (not the jpeg device), then re-size the device. You can make the circles look all sorts of weird.

Draw random circles, coloring in red any circle not intersecting another circle

You have logic mistake in if statement inside the cycle - you can set black color then revert to red for some other pair circle. Possible solution draft:

  for (int j = 0; j < 20; j++)
    {   
        g.setColor(Color.RED);  //set non-intersect state
        for (int k = j + 1; k < 20; k++)  //avoid excessive work
        {   
                if (intersect test)
                  {
                    g.setColor(Color.BLACK);
                    break; //can stop here
                  };
            g.drawOval(x[j], y[j], diameter[j], diameter[j]);
        }
}

Python Pygame randomly draw non overlapping circles

You did not check against all other circles. I added a variable shouldprint which gets set to false if any other circle is too close.

import pygame, random, math

red = (255, 0, 0)
width = 800
height = 600
circle_num = 20
tick = 2
speed = 5

pygame.init()
screen = pygame.display.set_mode((width, height))

class circle():
    def __init__(self):
        self.x = random.randint(0,width)
        self.y = random.randint(0,height)
        self.r = 100

    def new(self):
        pygame.draw.circle(screen, red, (self.x,self.y), self.r, tick)

c = []
for i in range(circle_num):
    c.append('c'+str(i))
    c[i] = circle()
    shouldprint = True
    for j in range(len(c)):
        if i != j:
            dist = int(math.hypot(c[i].x - c[j].x, c[i].y - c[j].y))
            if dist < int(c[i].r*2):
                shouldprint = False
    if shouldprint:
        c[i].new()
        pygame.display.update()

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            pygame.quit()
            quit()

Random non overlapping circles(with circle number controlled) in python and pygame

Create a list of circles Each circle is a tuple with 3 components, the x and y coordinate and the radius. Append new circles as long the length of the list is less than n:

circle_list = []
while len(circle_list) < n:
    # [...]

Create a random position and radius:

r = random.randint(10, 20)
x = random.randint(r, display_width - r)
y = random.randint(r, display_height - r)

Evaluate if the circle intersects with a other circle wich is in the list:

collide = False
for x2, y2, r2 in circle_list:
    d = distance(x, y, x2, y2)
    if d < r + r2:
        collide = True
        break

Append the circle if it does not collide:

if not collide:
    circle_list.append((x, y, r))

Minimal example:

Sample Image

import random
import math
import pygame

def euclidean_distance(x1, y1, x2, y2):
    #return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
    return math.hypot((x1 - x2), (y1 - y2))

pygame.init()
window = pygame.display.set_mode((400, 400))
font50 = pygame.font.SysFont(None, 50)
clock = pygame.time.Clock()

pygame.time.delay(10000)

run = True
circle_list = []
while run:
    clock.tick(100)
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            run = False

    r = random.randint(10, 20)
    x = random.randint(10+r, window.get_width()- r-10)
    y = random.randint(10+r, window.get_height()-r-10)
    if not any((x2, y2, r2) for x2, y2, r2 in circle_list if euclidean_distance(x, y, x2, y2) < r + r2):
        circle_list.append((x, y, r))    

    window.fill((255, 255, 255))
    for x, y, r in circle_list:
        pygame.draw.circle(window, (0, 0, 0), (round(x), round(y)), int(r), 3)
    window.blit(font50.render(str(len(circle_list)), True, (255, 0, 0)), (10, 10))
    pygame.display.flip()
 
pygame.quit()
exit()

Non overlapping randomly located circles

you can save a list of all the previously drawn circles. After
randomizing a new circle check that it doesn't intersects the previously drawn circles.

code example:

nCircles = 20;
circles = zeros(nCircles ,2);
r = 0.5;

for i=1:nCircles
    %Flag which holds true whenever a new circle was found
    newCircleFound = false;
    
    %loop iteration which runs until finding a circle which doesnt intersect with previous ones
    while ~newCircleFound
        x = 0 + (5+5)*rand(1);
        y = 0 + (5+5)*rand(1);
        
        %calculates distances from previous drawn circles
        prevCirclesY = circles(1:i-1,1);
        prevCirclesX = circles(1:i-1,2);
        distFromPrevCircles = ((prevCirclesX-x).^2+(prevCirclesY-y).^2).^0.5;
        
        %if the distance is not to small - adds the new circle to the list
        if i==1 || sum(distFromPrevCircles<=2*r)==0
            newCircleFound = true;
            circles(i,:) = [y x];
            circle3(x,y,r)
        end
    
    end
    hold on
end

*notice that if the amount of circles is too big relatively to the range in which the x and y coordinates are drawn from, the loop may run infinitely.
in order to avoid it - define this range accordingly (it can be defined as a function of nCircles).

output example

Drawing outline of intersecting circles

First, imagine the background was not there. I'm pretty sure you'd know how to do it, draw each circle then draw their insides (as in a filled circle) to remove the arcs that are inside.

Now to do the same over an image, you could do either of these things. One thing you can do is to disable writing on the color buffer, do that procedure and change the stencil buffer. Then enable writing on the color buffer and draw a whole screen rectangle which consequently fills the pixels you have marked in the stencil buffer.

The stencil buffer may not be usable to you however for a couple of reasons, such as you are using it for something else. In this case, an alternative would be to do the same thing, but instead of rendering in the stencil buffer, you render in a texture. Then bind that texture and draw a rectangle on the screen.

I'm quite certain you could achieve this with the accumulation buffer too, but I have never used it so I can't really tell (if anyone knows about that, please edit my answer and tell us how)

Java Applets: Drawing circles that don't overlap one another?

There are several issues here.

don't call setBackground(Color) in the paint method. This method is solely intended for painting. Other modifications should be done in the constructor or the init method
Call super.paint(g) as the first line of your overridden paint method. This will clear the background
(Minor: Make the scope of variables as small as possible. So declare posX etc. only where they are really needed)

Concerning the placement of the circles:

At the moment, you are computing new positions and diameters for the circles each time the applet is repainted. So when you resize the window of the applet viewer, new, randomly placed circles will flicker all around. You should create the circles only once (in the constructor, probably). In the paint method, you should only paint them.

More importantly: How to you know that it is possible to place the circles without overlaps? In the end, this leads into the complex world of Circle Packing where you may epmploy some really sophisticated techniques to make sure that you place the circles as tightly as possible.

But for now, you can use a very simple approach: Each time that you create a new circle, you can try (several times) to assign a new position and diameter, until you found a configuration that does not overlap an already existing circle. Although it may seem tempting to use a method like

while (existingCircles.size() < 5)
{
    Circle circle = newRandomCircle();
    if (!circle.overlapsAny(existingCircles))
    {
        existingCircles.add(circle);
    }
}

the problem here is that this algorithm will not terminate when it is not possible to place the circles at all! (Note: This is pseudocode. But ... you should consider writing your code in a way so that it looks like the code above. That is, consider creating a Circle class, for example).

However, here is a very pragmatic solution, that only tries to place a new circle for 10 times, and simply does not place it when it does not succeed. While this is not very elegant, it's at least guaranteed to terminate.

import java.awt.Color;
import java.awt.Graphics;
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

import javax.swing.JApplet;

public class Circles extends JApplet
{   
    private final List<Point> positions;
    private final List<Integer> diameters;

    public Circles()
    {
        positions = new ArrayList<Point>();
        diameters = new ArrayList<Integer>();

        Random rand = new Random();

        for(int i=1; i <= 5 ; i++ )
        {
            int tries = 10;
            for (int t=0; t<tries; t++)
            {
                int diameter = rand.nextInt(75)+1;
                int posX = rand.nextInt(500);;
                int posY = rand.nextInt(500);
                Point position = new Point(posX, posY);

                if (!overlapsOther(position, diameter))
                {
                    positions.add(new Point(posX, posY));
                    diameters.add(diameter);
                    break;
                }
            }
        }
    }

    private boolean overlapsOther(Point position, int diameter)
    {
        int radius = diameter/2;
        int centerX = position.x + radius;
        int centerY = position.y + radius;

        for (int i=0; i<positions.size(); i++)
        {
            Point otherPosition = positions.get(i);
            int otherDiameter = diameters.get(i);
            int otherRadius = otherDiameter/2;
            int otherCenterX = otherPosition.x + otherRadius;
            int otherCenterY = otherPosition.y + otherRadius;

            int dx = centerX - otherCenterX;
            int dy = centerY - otherCenterY;
            double distance = Math.hypot(dx, dy);
            if (distance < radius + otherRadius)
            {
                return true;
            }
        }
        return false;
    }

    @Override
    public void paint(Graphics g) 
    {
        super.paint(g);

        for(int i=0; i<positions.size(); i++)
        {
            int posX = positions.get(i).x;
            int posY = positions.get(i).y;
            int diameter = diameters.get(i);

            if (diameter < 25)
            {
                g.setColor(Color.YELLOW);
                g.fillOval(posX, posY,diameter,diameter);
            }

            else if(diameter > 50)
            {
                g.setColor(Color.GREEN);
                g.fillOval(posX, posY,diameter,diameter);
            }
            else
            {
                g.setColor(Color.RED);
                g.drawOval(posX, posY,diameter,diameter);
            }

            System.out.println(diameter);
        }
    }
}

Drawing Non-Intersecting Circles