笛卡尔坐标算法b题

Question

在二维网格上，有一个直角坐标C(Cx,Cy)，它是正方形的中心，半径为'b'。

并且有两个点P1(x1,y1), P2(x2,y2)。当我直接用线连接P1和P2时，应该是一条直线。

我想做一个伪代码来检测P1和P2之间的直线是否在正方形区域

参数将是中心点和两个不同的点和半径。

正方形中心：(Cx,Cy)

两点：P1(x1,y1), P2(x2,y2)

半径：'b'

函数直线 ((x1,y1),(x2,y2),(Cx,Cy),b)

如果直线不在正方形区域上，它应该return true，如果它在正方形区域上，它应该return false。

Answer 1

您可以将此问题（通过投影坐标）转换为位于 (0, 0) 的正方形 "radius" 1.

判断线段（p₁,p₂）是否穿过正方形的顶边，可以先测试这些条件：

(y₂ - 1) * (y₂ - 1) > 0. 如果这是真的，表示线段完全在正方形顶部之上，或者完全在正方形顶部之下。
y₁ = y₂。如果为真，则线段与正方形平行。

在所有其他情况下，交点的 x 坐标为：

x = x₁ - y₁ * (x₂ - x₁) / (y₂ - y₁)

如果这个x不在[-1, 1]范围内，则线段不与正方形顶部相交

其他三边也可以做类似的操作

如果其中任何一个给出了 [-1, 1] 范围内的交点坐标，函数 straight 应该 return true，否则 false。

这是一个交互式 JavaScript 实现，您可以使用它在正方形附近绘制线段（通过 "dragging" 鼠标）。当调用 straight returns true:

时，方块将突出显示

function intersectionWithXaxis(x1, y1, x2, y2) {
    if (y1 * y2 > 0 || y1 === y2) return Infinity; // No intersection
    return x1 - y1 * (x2 - x1) / (y2 - y1); // x-coordinate of intersection
}

function straight(x1, y1, x2, y2, cx, cy, b) {
    // Project the coordinates so the square is at (0, 0) with "radius" 1
    x1 = (x1-cx)/b;
    y1 = (y1-cy)/b;
    x2 = (x2-cx)/b;
    y2 = (y2-cy)/b;
    let z;
    // Get intersections with top, bottom, left and right side of box:
    z = intersectionWithXaxis(x1, y1-1, x2, y2-1);
    if (Math.abs(z) <= 1) return true;
    z = intersectionWithXaxis(x1, y1+1, x2, y2+1);
    if (Math.abs(z) <= 1) return true;
    // We can use the same function for vertical line intersections by swapping x and y
    z = intersectionWithXaxis(y1, x1-1, y2, x2-1);
    if (Math.abs(z) <= 1) return true;
    z = intersectionWithXaxis(y1, x1+1, y2, x2+1);
    if (Math.abs(z) <= 1) return true;
    return false;
}

let cx = 100;
let cy = 60;
let b = 30;
let x1, y1, x2, y2;

// I/O handling

let canvas = document.querySelector("canvas");
let ctx = canvas.getContext("2d");
ctx.fillStyle = "yellow";
let isMouseDown = false;

function draw() {
    ctx.clearRect(0, 0, canvas.width, canvas.height);
    ctx.beginPath();
    ctx.rect(cx-b, cy-b, 2*b, 2*b);
    ctx.stroke();
    
    if (!isMouseDown) return;
    // Call the main function. If true, highlight the square
    if (straight(x1, y1, x2, y2, cx, cy, b)) ctx.fill();
    
    ctx.beginPath();
    ctx.moveTo(x1, y1);
    ctx.lineTo(x2, y2);
    ctx.stroke();
}

canvas.addEventListener("mousedown", function(e) {
    x1 = e.clientX - this.offsetLeft;
    y1 = e.clientY - this.offsetTop;
    isMouseDown = true;
});
canvas.addEventListener("mousemove", function(e) {
    if (!isMouseDown) return;
    x2 = e.clientX - this.offsetLeft;
    y2 = e.clientY - this.offsetTop;
    draw();
});
canvas.addEventListener("mouseup", function(e) {
    isMouseDown = false;
});

draw();

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

笛卡尔坐标算法b题

Cartesian coordinates algorithmb question

algorithm

pseudocode