如何将一个圆形最小化地置于一个矩形外部？

Question

这似乎很简单，但我找不到任何清晰的答案。假设我有一个圆和矩形。如果圆在矩形外面，它应该保持其当前位置。然而，如果它在矩形内部，它应该被最小程度地移动，以便它仅仅位于矩形外面。

我已经创建了下面的完整演示，展示了我的当前工作进展。我的最初想法是将圆夹紧到最近的边缘，但那似乎没有正常工作。我认为可能有一种解决方案涉及分离轴定理，但我不确定它是否适用于这种情况，或者是否过于复杂。

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>

从演示中可以看出，500毫秒后圆圈会跳动一下，试图正确地移动自己，但它并没有移动到正确的位置。是否有一种算法可以找到圆的新位置，并且尽可能少地移动它以使其移出矩形的范围？

- Ryan Peschel

---

嗯，不确定，我没有考虑到那个。那会改变很多东西吗？在我的特定用例中，我认为所有的矩形都是16x16的图块，需要被移动的圆形都会比这小，但我想未来可能会有更大的单位。 - Ryan Peschel

我建议您从简单的问题开始。例如，给定一个圆和一条直线y=k，找到最靠近其起始位置的圆的位置，使其切线于该直线并在其下方（y<k）。这非常容易，一旦您将其工作正常，就可以进一步处理任意直线，然后是矩形的边缘，最后是矩形的角落。小矩形情况有点棘手。 - Beta

这个问题没有现成的算法吗？ - Ryan Peschel

Rocco的删除答案是正确执行此操作的最简单方法。无法逃避需要对圆角矩形进行命中测试，成功后从8种情况中选择最小修正。也许一些代码可以重构为函数，但唯一的影响是（稍微）增加执行时间。 - j_random_hacker

我建议在他的其他答案下发表评论，请求他将其恢复。如果他不想这样做，我可以将其复制到Pastebin中，但我更希望他知道并得到认可。 - j_random_hacker

Answer 1

看这里，核心在calc()函数中，它是Java而不是JavaScript，但我认为你可以轻松地翻译它。

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

- Rocco

---

我不是有意冒犯，但难道真的没有比100行函数更好的方法来完成这个任务吗？这段代码在我的项目中会经常被调用，所以它必须非常高效和简洁。 - Ryan Peschel

@RyanPeschel 不冒犯，当然这只是第一（工作）草稿，代码可能可以缩小一些，但是你必须区分几种情况。代码正在检查圆的中心是否在一个圆角形状内，其中每个点与原始矩形的距离相等。如果是这种情况，则计算从矩形到最小距离向量，并将其调整为半径长度。不要认为它可以在不使用管理任意形状的库的情况下大大减少。 - Rocco

Answer 2

对代码进行了以下修改：

• 添加了函数 pointToSegmentDistance，该函数计算点到线段的距离以及线段上垂足点。

• 添加了函数 pointInPolygon，该函数确定点是否在多边形内或外。

• 修改了函数 getCircleRectangleDisplacement，执行以下操作：

  • 创建一个绑定的多边形，将矩形的边沿扩展半径长度。然后，如果圆心位于此绑定多边形内，则需要将其移动到四个（4）扩展边之一。函数 pointInPolygon 确定圆心是否在绑定多边形中，如果是，则使用 pointToSegmentDistance 查找最接近四个（4）扩展边之一的点，该点现在表示新的圆心。
  • 否则，如果圆心在绑定多边形外，则函数检查圆心是否小于半径长度到达四个顶点之一，并且如果是，则将圆心远离顶点，使距离现在为半径。

<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://dev59.com/fXRA5IYBdhLWcg3wuAcp#6853926
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>

我相信这个算法可以扩展到简单多边形（即凸多边形，而不是凹多边形），尽管需要更多的三角学和/或矩阵数学...

- Trentium