How to displace a circle minimally outside a rectangle?

Question

This seems like it should be pretty simple but I could not find any clear answers on it. Say I have a single circle and rectangle. If the circle is outside of the rectangle, it should maintain its current position. However, if it is inside the rectangle at all, it should be displaced minimally such that it is barely outside the rectangle.

I have created a full demo below that demonstrates my current work-in-progress. My initial idea was to clamp the circle to the closest edge, but that seemed to not be working properly. I think there might be a solution involving Separating Axis Theorem, but I'm not sure if that applies here or if it's overkill for this sort of thing.

let canvas = document.querySelector("canvas");
let ctx = canvas.getContext("2d");

function draw() {
  ctx.fillStyle = "#b2c7ef";
  ctx.fillRect(0, 0, 800, 800);
  
  ctx.fillStyle = "#fff";
  drawCircle(circlePos.x, circlePos.y, circleR);
  drawSquare(squarePos.x, squarePos.y, squareW, squareH);
}

function drawCircle(xCenter, yCenter, radius) {
  ctx.beginPath();
  ctx.arc(xCenter, yCenter, radius, 0, 2 * Math.PI);
  ctx.fill();
}

function drawSquare(x, y, w, h) {
  ctx.beginPath();
  ctx.rect(x, y, w, h);
  ctx.stroke();
}

function clamp(value, min, max) {
  return Math.min(Math.max(value, min), max);
}

function getCircleRectangleDisplacement(rX, rY, rW, rH, cX, cY, cR) {
  let nearestX = clamp(cX, rX, rX + rW);
  let nearestY = clamp(cY, rY, rY + rH);

  let newX = nearestX - cR / 2;
  let newY = nearestY - cR / 2;

  return { x: newX, y: newY };
}

function displace() {
  circlePos = getCircleRectangleDisplacement(squarePos.x, squarePos.y, squareW, squareH, circlePos.x, circlePos.y, circleR);
  
  draw();
}

let circlePos = { x: 280, y: 70 };
let squarePos = { x: 240, y: 110 };

let circleR = 50;

let squareW = 100;
let squareH = 100;

draw();

setTimeout(displace, 500);

canvas { display: flex; margin: 0 auto; }

<canvas width="800" height="800"></canvas>

As you can see in the demo, after 500 milliseconds the circle jumps a bit in an attempt to displace itself properly, but it does not move to the correct location. Is there an algorithm to find the circle's new location that would require as little movement as possible to move it outside of the bounds of the rectangle?

Answer 1

Have a look here, core is in calc() function, it's Java, not JavaScript , but I think that you can easily translate it.

package test;

import java.awt.Color;
import java.awt.Dimension;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.MouseAdapter;
import java.awt.event.MouseEvent;
import java.awt.geom.Ellipse2D;
import java.awt.geom.Point2D;
import java.awt.geom.Rectangle2D;

import javax.swing.JComponent;
import javax.swing.JFrame;

public class CircleOutside extends JComponent {
    protected Rectangle2D rect;
    protected Point2D originalCenter;
    protected double radius;
    protected Point2D movedCenter;
    
    @Override
    protected void paintComponent(Graphics g) {
        super.paintComponent(g);

        Graphics2D g2=(Graphics2D) g;
        g2.draw(rect);
        g.setColor(Color.red);
        g2.draw(new Ellipse2D.Double(originalCenter.getX()-radius, originalCenter.getY()-radius, 2*radius, 2*radius));
        g.setColor(Color.green);
        g2.draw(new Ellipse2D.Double(movedCenter.getX()-radius, movedCenter.getY()-radius, 2*radius, 2*radius));
        
        addMouseListener(new MouseAdapter() {
            @Override
            public void mouseClicked(MouseEvent e) {
                originalCenter=e.getPoint();
                calc();
                repaint();
            }
        });
    }
    
    public void calc() {
        movedCenter=originalCenter;
        
        //Circle center distance from edges greater than radius, do not move 
        if (originalCenter.getY()+radius<=rect.getY()) {
            return;
        }
        if (originalCenter.getY()-radius>=rect.getY()+rect.getHeight()) {
            return;
        }
        if (originalCenter.getX()+radius<=rect.getX()) {
            return;
        }
        if (originalCenter.getX()-radius>=rect.getX()+rect.getWidth()) {
            return;
        }

        double moveX=0;
        double moveY=0;
        boolean movingY=false;
        boolean movingX=false;

        //Center projects into rectangle's width, move up or down
        if (originalCenter.getX()>=rect.getX()&&originalCenter.getX()<=rect.getX()+rect.getWidth()) {
            System.out.println("X in width");
            double moveUp=rect.getY()-originalCenter.getY()-radius;
            double moveDown=rect.getY()+rect.getHeight()-originalCenter.getY()+radius;
            if (Math.abs(moveUp)<=Math.abs(moveDown)) {
                moveY=moveUp;
            } else {
                moveY=moveDown;
            }
            System.out.println("UP "+moveUp+" DOWN "+moveDown);
            movingY=true;
        }

        //Center projects into rectangle's height, move left or right
        if (originalCenter.getY()>=rect.getY()&&originalCenter.getY()<=rect.getY()+rect.getHeight()) {
            double moveLeft=rect.getX()-originalCenter.getX()-radius;
            double moveRight=rect.getX()+rect.getWidth()-originalCenter.getX()+radius;
            if (Math.abs(moveLeft)<=Math.abs(moveRight)) {
                moveX=moveLeft;
            } else {
                moveX=moveRight;
            }
            movingX=true;
        }
            
        //If circle can be moved both on X or Y, choose the lower distance
        if (movingX&&movingY) {
            if (Math.abs(moveY)<Math.abs(moveX)) {
                moveX=0;
            } else {
                moveY=0;
            }
        }

        //Note that the following cases are mutually excluding with the previous ones
        
        //Center is in the arc [90-180] centered in upper left corner with same radius as circle, calculate distance from corner and adjust both axis 
        if (originalCenter.getX()<rect.getX()&&originalCenter.getY()<rect.getY()) {
            double dist=originalCenter.distance(rect.getX(),rect.getY());
            if (dist<radius) {
                double factor=(radius-dist)/dist;
                moveX=factor*(originalCenter.getX()-rect.getX());
                moveY=factor*(originalCenter.getY()-rect.getY());
            }
        }

        //Center is in the arc [0-90] centered in upper right corner with same radius as circle, calculate distance from corner and adjust both axis 
        if (originalCenter.getX()>rect.getX()+rect.getWidth()&&originalCenter.getY()<rect.getY()) {
            double dist=originalCenter.distance(rect.getX()+rect.getWidth(),rect.getY());
            if (dist<radius) {
                double factor=(radius-dist)/dist;
                moveX=factor*(originalCenter.getX()-rect.getX()-rect.getWidth());
                moveY=factor*(originalCenter.getY()-rect.getY());
            }
        }

        //Center is in the arc [270-360] centered in lower right corner with same radius as circle, calculate distance from corner and adjust both axis 
        if (originalCenter.getX()>rect.getX()+rect.getWidth()&&originalCenter.getY()>rect.getY()+rect.getHeight()) {
            double dist=originalCenter.distance(rect.getX()+rect.getWidth(),rect.getY()+rect.getHeight());
            if (dist<radius) {
                double factor=(radius-dist)/dist;
                moveX=factor*(originalCenter.getX()-rect.getX()-rect.getWidth());
                moveY=factor*(originalCenter.getY()-rect.getY()-rect.getHeight());
            }
        }

        //Center is in the arc [180-270] centered in lower left corner with same radius as circle, calculate distance from corner and adjust both axis 
        if (originalCenter.getX()<rect.getX()&&originalCenter.getY()>rect.getY()+rect.getHeight()) {
            double dist=originalCenter.distance(rect.getX(),rect.getY()+rect.getHeight());
            if (dist<radius) {
                double factor=(radius-dist)/dist;
                moveX=factor*(originalCenter.getX()-rect.getX());
                moveY=factor*(originalCenter.getY()-rect.getY()-rect.getHeight());
            }
        }

        movedCenter=new Point2D.Double(originalCenter.getX()+moveX,originalCenter.getY()+moveY);
    }
    
    
    public static void main(String[] args) {
        Rectangle2D rect=new Rectangle2D.Double(240, 110, 100, 100);
        Point2D center=new Point2D.Double(280, 70);
        double radius=50;
        
        CircleOutside o=new CircleOutside();
        o.rect=rect;
        o.originalCenter=center;
        o.radius=radius;
        o.calc();
        o.setPreferredSize(new Dimension(800,600));
        JFrame frame=new JFrame("Test circle");
        frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        
        frame.setContentPane(o);
        frame.pack();
        frame.setVisible(true);
    }
}