用于确定圆线段SEGMENT相交的代码是否正确? [英] Is this code for determining if a circle and line SEGMENT intersects correct?

问题描述

显然很难找到段和圆是否相交的答案.例如，如果您使用Google搜索，则会发现此问题，甚至是顶部两个答案似乎是错误的.

接受的答案有一条评论说:这似乎是在计算圆与直线而不是线段的交点向下滚动到下一个答案，您会发现另一条评论说此答案是否不完整?它查找圆和线是否相交，而不是线段.

然后，我尝试搜索一个函数，以确定是否仅 segment 与圆相交，但无济于事.我能找到的最好的方法是此处的伪代码说明.

我试图改编他的代码，尽管它似乎可以工作，但似乎太冗长，而且我不确定我的实现是否正确.我在问这是否正确，如果正确，是否确实没有更好的方法来确定这一点?确定线段和圆是否相交的理想方法是什么?请注意，我只需要知道它们相交的地方，而不是它们相交的地方.

我在下面提供了完整的演示副本，因此您也可以将其可视化.

 函数lineSegmentIntersectsCircle(x1，y1，x2，y2，cx，cy，r){令deltaX = x2-x1;令deltaY = y2-y1;让mag = Math.sqrt(deltaX * deltaX + deltaY * deltaY);让unitX = deltaX/mag;让unitY = deltaY/mag;令d =(cx-x1)* unitY-(cy-y1)* unitX;if(d< -r || d> r){返回false；}令x1CXDelta = x1-cx;令y1CYDelta = y1-cy;令x2CXDelta = x2-cx;令y2CYDelta = y2-cy;让pointOneWithinCircle = x1CXDelta * x1CXDelta + y1CYDelta * y1CYDelta<r * r;如果(pointOneWithinCircle){返回true;}let pointTwoWithinCircle = x2CXDelta * x2CXDelta + y2CYDelta * y2CYDelta<r * r;如果(pointTwoWithinCircle){返回true;}令foo = unitX * x1 + unitY * y1;设bar = unitX * cx + unitY * cy;令baz = unitX * x2 + unitY * y2;return(foo< bar&& bar< baz)||(baz< bar&& bar< foo);}让ctx = document.querySelector("canvas").getContext("2d");函数drawCircle(xCenter，yCenter，半径){ctx.beginPath();ctx.arc(xCenter，yCenter，radius，0，2 * Math.PI);ctx.fill();}函数drawLine(x1，y1，x2，y2){ctx.beginPath();ctx.moveTo(x1，y1);ctx.lineTo(x2，y2);ctx.stroke();}让circleX = 340;让circleY = 250;让circleR = 60;令lineX1 = 50;设Y1 = 350;令lineX2 = 285;令lineY2 = 250;画=()=>{ctx.fillStyle =#b2c7ef";ctx.fillRect(0，0，800，800);ctx.fillStyle ="#ffffff";drawCircle(circleX，circleY，circleR);drawLine(lineX1，lineY1，lineX2，lineY2);}console.log(lineSegmentIntersectsCircle(lineX1，lineY1，lineX2，lineY2，circleX，circleY，circleR))draw();  

  canvas {display:flex;保证金:0自动;}  

 <画布宽度="400" height ="400"></canvas>  

解决方案

我认为(1)计算线-磁盘相交点(它是空的，一个点或一条线段)(2)会更简单.测试交点是否与线段相交.

对于所有真实的 t ，直线的点为((1-t)x1 + t x2，(1-t)y1 + t y2).令 x(t)=(1-t)x1 + t x2-cx 和 y(t)=(1-t)y1 + t y2-cy .当且仅当多项式 x(t)^ 2 + y(t)^ 2-r ^ 2 = 0 具有实根时，线-磁盘交点才是非空的.在这种情况下，线盘交点在 [t1，t2] 中全部为 t .该线段是 [0，1] 中的所有 t .当且仅当 t1< == 1 和 t2> = 0 .

计算 t1 和 t2 需要平方根，我们可以避免.令 a，b，c 使得 x(t)^ 2 + y(t)^ 2-r ^ 2 = a t ^ 2 + b t + c .我们有 t1 + t2 = -b/a 和 t1 t2 = c/a .

• 当且仅当 b ^ 2-4-ac≥0 时，根 t1 和 t2 是真实的./p>

• 条件 t1< = 1 为假，当且仅当 t1-1-1>0 和 t2-1->0 ，当且仅当(t1-1)+(t2-1)>0 和(t1-1)(t2-1)>0 ，相当于 -b/a-2>0 和 c/a + b/a + 1>0 .由于 a>0 ，则简化为 -b>2 a 和 c + b + a>0 .

• 条件 t2> = 0 为假，当且仅当 t1<0 和 t2<0 ，当且仅当 t1 + t2 = -b/a<0 和 t1 t2 = c/a>0 .由于 a>0 ，则简化为 b>0 和 c>0 .

JavaScript的实现.

 函数lineSegmentIntersectsCircleOptimized(x1，y1，x2，y2，cx，cy，r){令x_linear = x2-x1;令x_constant = x1-cx;令y_linear = y2-y1;令y_constant = y1-cy;令a = x_linear * x_linear + y_linear * y_linear;让half_b = x_linear * x_constant + y_linear * y_constant;令c = x_constant * x_constant + y_constant * y_constant-r * r;返回 (half_b * half_b> = a * c&&(-half_b< = a || c + half_b + half_b + a< = 0)&&(half_b< = 0 || c< = 0));}函数lineSegmentIntersectsCircle(x1，y1，x2，y2，cx，cy，r){令deltaX = x2-x1;令deltaY = y2-y1;让mag = Math.sqrt(deltaX * deltaX + deltaY * deltaY);让unitX = deltaX/mag;让unitY = deltaY/mag;令d =(cx-x1)* unitY-(cy-y1)* unitX;如果(d< -r || d> r){返回false；}令x1CXDelta = x1-cx;令y1CYDelta = y1-cy;令x2CXDelta = x2-cx;令y2CYDelta = y2-cy;让pointOneWithinCircle =x1CXDelta * x1CXDelta + y1CYDelta * y1CYDelta<r * r;如果(pointOneWithinCircle){返回true；}让pointTwoWithinCircle =x2CXDelta * x2CXDelta + y2CYDelta * y2CYDelta<r * r;如果(pointTwoWithinCircle){返回true；}令foo = unitX * x1 + unitY * y1;设bar = unitX * cx + unitY * cy;令baz = unitX * x2 + unitY * y2;return(foo< bar&& bar< baz)||(baz< bar&& bar< foo);}功能测试() {for(令i = 0; i< 10000000; i ++){令x1 = Math.random();令y1 = Math.random();令x2 = Math.random();令y2 = Math.random();让cx = Math.random();令cy = Math.random();令r = Math.random();如果 (lineSegmentIntersectsCircle(x1，y1，x2，y2，cx，cy，r)！=lineSegmentIntersectsCircleOptimized(x1，y1，x2，y2，cx，cy，r)){console.log(坏")；休息;}}}测试(); 

It's apparently very hard to find the answer to whether a line segment and circle intersect. For example, if you google you'll find this question and even the top two answers seem wrong.

The accepted answer has a comment saying: This seems to compute the intersection of a circle with a line, not a segment Scroll down to the next answer and you'll find another comment saying Isn't this answer in incomplete? It finds whether a circle and line intersect, not a line segment.

I've then tried to search for a function for determining if just a segment intersects a circle, but to no avail. The best I could find is a pseudocode explanation here.

I've tried to adapt his code and while it seems to work, it seems overly verbose and I'm not sure if my implementation is correct. I'm asking whether or not this is correct and if it is, is there indeed no better way of determining this? What is the ideal way of determining if a line segment and circle intersects? Please note, I only need to know if they intersect, not where they intersect.

I've provided a full demo reproduction below so you can also visualize it.

function lineSegmentIntersectsCircle(x1, y1, x2, y2, cx, cy, r) {
  let deltaX = x2 - x1;
  let deltaY = y2 - y1;

  let mag = Math.sqrt(deltaX * deltaX + deltaY * deltaY);

  let unitX = deltaX / mag;
  let unitY = deltaY / mag;

  let d = (cx - x1) * unitY - (cy - y1) * unitX;

  if (d < -r || d > r) { return false; }

  let x1CXDelta = x1 - cx;
  let y1CYDelta = y1 - cy;

  let x2CXDelta = x2 - cx;
  let y2CYDelta = y2 - cy;

  let pointOneWithinCircle = x1CXDelta * x1CXDelta + y1CYDelta * y1CYDelta < r * r;
  if (pointOneWithinCircle) { return true; }

  let pointTwoWithinCircle = x2CXDelta * x2CXDelta + y2CYDelta * y2CYDelta < r * r;
  if (pointTwoWithinCircle) { return true; }

  let foo = unitX * x1 + unitY * y1;
  let bar = unitX * cx + unitY * cy;
  let baz = unitX * x2 + unitY * y2;

  return (foo < bar && bar < baz) || (baz < bar && bar < foo); 
}

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

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

function drawLine(x1, y1, x2, y2) {
  ctx.beginPath();
  ctx.moveTo(x1, y1);
  ctx.lineTo(x2, y2);
  ctx.stroke();
}

let circleX = 340;
let circleY = 250;
let circleR = 60;

let lineX1 = 50;
let lineY1 = 350;
let lineX2 = 285;
let lineY2 = 250;

draw = () => {
  ctx.fillStyle = "#b2c7ef";
  ctx.fillRect(0, 0, 800, 800); 

  ctx.fillStyle = "#ffffff";

  drawCircle(circleX, circleY, circleR);
  drawLine(lineX1, lineY1, lineX2, lineY2);
}

console.log(lineSegmentIntersectsCircle(lineX1, lineY1, lineX2, lineY2, circleX, circleY, circleR))

draw();

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

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

解决方案

I think it would be a simpler to (1) compute the line-disk intersection, which is either empty, a point, or a line segment (2) test whether the intersection intersects the line segment.

The points of the line are ((1-t) x1 + t x2, (1-t) y1 + t y2) for all real t. Let x(t) = (1-t) x1 + t x2 - cx and y(t) = (1-t) y1 + t y2 - cy. The line-disk intersection is nonempty if and only if the polynomial x(t)^2 + y(t)^2 - r^2 = 0 has real roots t1 <= t2. In this case, the line-disk intersection is all t in [t1, t2]. The line segment is all t in [0, 1]. The two intersect if and only if t1 <= 1 and t2 >= 0.

Computing t1 and t2 requires a square root, which we can avoid. Let a, b, c be such that x(t)^2 + y(t)^2 - r^2 = a t^2 + b t + c. We have t1 + t2 = -b/a and t1 t2 = c/a.

• The roots t1 and t2 are real if and only if b^2 - 4 a c >= 0.

• The condition t1 <= 1 is false if and only if t1 - 1 > 0 and t2 - 1 > 0, which in turn is true if and only if (t1 - 1) + (t2 - 1) > 0 and (t1 - 1) (t2 - 1) > 0, which is equivalent to -b/a - 2 > 0 and c/a + b/a + 1 > 0. Since a > 0, this simplifies to -b > 2 a and c + b + a > 0.

• The condition t2 >= 0 is false if and only if t1 < 0 and t2 < 0, which in turn is true if and only if t1 + t2 = -b/a < 0 and t1 t2 = c/a > 0. Since a > 0, this simplifies to b > 0 and c > 0.

Implementation in Javascript.

function lineSegmentIntersectsCircleOptimized(x1, y1, x2, y2, cx, cy, r) {
  let x_linear = x2 - x1;
  let x_constant = x1 - cx;
  let y_linear = y2 - y1;
  let y_constant = y1 - cy;
  let a = x_linear * x_linear + y_linear * y_linear;
  let half_b = x_linear * x_constant + y_linear * y_constant;
  let c = x_constant * x_constant + y_constant * y_constant - r * r;
  return (
    half_b * half_b >= a * c &&
    (-half_b <= a || c + half_b + half_b + a <= 0) &&
    (half_b <= 0 || c <= 0)
  );
}

function lineSegmentIntersectsCircle(x1, y1, x2, y2, cx, cy, r) {
  let deltaX = x2 - x1;
  let deltaY = y2 - y1;

  let mag = Math.sqrt(deltaX * deltaX + deltaY * deltaY);

  let unitX = deltaX / mag;
  let unitY = deltaY / mag;

  let d = (cx - x1) * unitY - (cy - y1) * unitX;

  if (d < -r || d > r) {
    return false;
  }

  let x1CXDelta = x1 - cx;
  let y1CYDelta = y1 - cy;

  let x2CXDelta = x2 - cx;
  let y2CYDelta = y2 - cy;

  let pointOneWithinCircle =
    x1CXDelta * x1CXDelta + y1CYDelta * y1CYDelta < r * r;
  if (pointOneWithinCircle) {
    return true;
  }

  let pointTwoWithinCircle =
    x2CXDelta * x2CXDelta + y2CYDelta * y2CYDelta < r * r;
  if (pointTwoWithinCircle) {
    return true;
  }

  let foo = unitX * x1 + unitY * y1;
  let bar = unitX * cx + unitY * cy;
  let baz = unitX * x2 + unitY * y2;

  return (foo < bar && bar < baz) || (baz < bar && bar < foo);
}

function test() {
  for (let i = 0; i < 10000000; i++) {
    let x1 = Math.random();
    let y1 = Math.random();
    let x2 = Math.random();
    let y2 = Math.random();
    let cx = Math.random();
    let cy = Math.random();
    let r = Math.random();
    if (
      lineSegmentIntersectsCircle(x1, y1, x2, y2, cx, cy, r) !=
      lineSegmentIntersectsCircleOptimized(x1, y1, x2, y2, cx, cy, r)
    ) {
      console.log("bad");
      break;
    }
  }
}

test();

这篇关于用于确定圆线段SEGMENT相交的代码是否正确?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！