How to displace a circle minimally outside a rectangle?

user_962155 0
Viewed 118

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?

game-physics collision-detection math algorithm javascript
2 Answers

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);
    }
}
user_156112700

Made the following modifications to the code:

  • Added function pointToSegmentDistance which calculates both the distance of a point to a line segment in addition to the corresponding perpendicular point on the line segment.

  • Added function pointInPolygon which determines whether a point resides inside or outside of a polygon.

  • Modified function getCircleRectangleDisplacement to perform the following:

    • Create a bounding polygon that extends the edges of the rectangle by the length of the radius. Then, if the circle center resides inside this bounding polygon, it needs to be moved to one of the four (4) extended edges. Function pointInPolygon determines whether the circle center is in the bounding polygon, and if so, then pointToSegmentDistance is used to find the closest point on one of the four (4) extended edges, a point which now represents the new circle center.
    • Otherwise, if the circle center is outside the bounding polygon, then the function checks if the circle center is less than the length of the radius to one of the four vertices, and if so, moves the circle center away from the vertex such that the distance is now the radius.

<html><head>

<style>
canvas { display: flex; margin: 0 auto; }
</style>

</head><body>

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


<script>

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

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

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

function drawSquare(x, y, w, h) {
  ctx.fillStyle = "#f0f";
  ctx.beginPath();
  ctx.rect(x, y, w, h);
  ctx.fill();
}

// Sourced and adapted from https://stackoverflow.com/a/6853926/7696162
function pointToSegmentDistance(point, segBeg, segEnd) {

  var A = point.x - segBeg.x;
  var B = point.y - segBeg.y;
  var C = segEnd.x - segBeg.x;
  var D = segEnd.y - segBeg.y;

  var dot = A * C + B * D;
  var len_sq = C * C + D * D;
  var param = -1;
  if (len_sq != 0) //in case of 0 length line
      param = dot / len_sq;

 let intersectPoint;

  if (param < 0) {
    intersectPoint = segBeg;
  }
  else if (param > 1) {
    intersectPoint = segEnd;
  }
  else {
    intersectPoint = { x: segBeg.x + param * C, y:segBeg.y + param * D };
  }

  var dx = point.x - intersectPoint.x;
  var dy = point.y - intersectPoint.y;
  return { intersect: intersectPoint, distance: Math.sqrt(dx * dx + dy * dy) };
}

// Sourced and adapted from https://www.algorithms-and-technologies.com/point_in_polygon/javascript
function pointInPolygon( point, polygon ) {
  let vertices = polygon.vertex;
  //A point is in a polygon if a line from the point to infinity crosses the polygon an odd number of times
  let odd = false;
  //For each edge (In this case for each point of the polygon and the previous one)
  for (let i = 0, j = polygon.length - 1; i < polygon.length; i++) {
    //If a line from the point into infinity crosses this edge
    if (((polygon[i].y > point.y) !== (polygon[j].y > point.y)) // One point needs to be above, one below our y coordinate
      // ...and the edge doesn't cross our Y corrdinate before our x coordinate (but between our x coordinate and infinity)
      && (point.x < ((polygon[j].x - polygon[i].x) * (point.y - polygon[i].y) / (polygon[j].y - polygon[i].y) + polygon[i].x))) {
      // Invert odd
      odd = !odd;
    }
    j = i;
  }
  //If the number of crossings was odd, the point is in the polygon
  return odd;
}

function getCircleRectangleDisplacement( rX, rY, rW, rH, cX, cY, cR ) {

  let rect = [
    { x: rX, y:rY },
    { x: rX + rW, y:rY },
    { x: rX + rW, y:rY + rH },
    { x: rX, y:rY + rH }
  ];

  let boundingPolygon = [
    { x: rX, y: rY },
    { x: rX, y: rY - cR },
    { x: rX + rW, y: rY - cR },
    { x: rX + rW, y: rY },
    { x: rX + rW + cR, y: rY },
    { x: rX + rW + cR, y: rY + rH },
    { x: rX + rW, y: rY + rH },
    { x: rX + rW, y: rY + rH + cR },
    { x: rX, y: rY + rH + cR },
    { x: rX, y: rY + rH },
    { x: rX - cR, y: rY + rH },
    { x: rX - cR, y: rY }
  ];
  
  // Draw boundingPolygon... This can be removed...
  ctx.setLineDash([2,2]);ctx.beginPath();ctx.moveTo(boundingPolygon[0].x,boundingPolygon[0].y);for (let p of boundingPolygon) {ctx.lineTo(p.x,p.y);} ctx.lineTo(boundingPolygon[0].x,boundingPolygon[0].y);ctx.stroke();
  
  circleCenter = { x: cX, y: cY };
  // If the circle center is inside the bounding polygon...
  if ( pointInPolygon( circleCenter, boundingPolygon ) ) {
    let newCircleCenter;
    let minDistance = Number.MAX_VALUE;
    // ...then loop through the 4 segments of the bounding polygon that are
    // extensions of the original rectangle, looking for the point that is
    // closest to the circle center.
    for ( let i = 1; i < boundingPolygon.length; i += 3 ) {
      let pts = pointToSegmentDistance( circleCenter, boundingPolygon[ i ], boundingPolygon[ i + 1 ] );
      if ( pts.distance < minDistance ) {
          newCircleCenter = pts.intersect;
          minDistance = pts.distance;
      }
    }
    circleCenter = newCircleCenter;
  } else {
    // ...otherwise, if the circle center is outside the bounding polygon,
    // let's check to see if the circle center is closer than the radius
    // to one of the corners of the rectangle.
    let newCircleCenter;
    let minDistance = Number.MAX_VALUE;
    for ( let i = 0; i < boundingPolygon.length; i += 3 ) {
      let d = Math.sqrt( ( circleCenter.x - boundingPolygon[ i ].x ) ** 2 + ( circleCenter.y - boundingPolygon[ i ].y ) ** 2 );
      if ( d < cR && d < minDistance ) {
        // Okay, the circle is too close to a corner.  Let's move it away...
        newCircleCenter = {
          x: boundingPolygon[ i ].x  + ( circleCenter.x - boundingPolygon[ i ].x ) * cR / d,
          y: boundingPolygon[ i ].y  + ( circleCenter.y - boundingPolygon[ i ].y ) * cR / d
        }
        minDistance = d;
      }
    }
    if ( newCircleCenter ) {
      circleCenter = newCircleCenter;
    }
  }
  return circleCenter;
}

function displace() {

  ctx.fillStyle = "#b2c7ef";
  ctx.fillRect(0, 0, 800, 800);
  
  circlePos.x += 1;
  circlePos.y += 1;
  circlePos = getCircleRectangleDisplacement(squarePos.x, squarePos.y, squareW, squareH, circlePos.x, circlePos.y, circleR);
  
  draw();
  
  if ( maxIterations < iterations++ ) {
    clearInterval( timer );
  }
}

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

let circleR = 50;

let squareW = 100;
let squareH = 100;

let iterations = 0;
let maxIterations = 200;
let timer = setInterval(displace, 50);

</script>


</body></html>

I believe this algorithm can be extended to simple polygons (ie, convex polygons, not concave polygons) although with a bit more trigonometry and/or matrix math...

user_76961620
Related