检查给定点是否在旋转元素的边界内

Question

我有一个旋转 45° 的矩形，如下所示，我有四个角的点，我需要找出给定点是否在旋转矩形的边界内。请注意，旋转将更改为任意数字，因此旋转需要以某种方式成为公式的一部分。

所以我们有：

宽度：10

身高：10

旋转度数：45°

旋转后的矩形坐标：A B C D

给定坐标：E

感谢任何帮助。

Answer 1

任何多面体都可以表示为封闭半空间的有限交集。半空间由线性不等式给出，例如 x+y+5<=0 这是通过 (-5,0) 和 (0,-5) 的线的下部。

有关详细信息，请参阅任何有关凸性的书籍或维基百科link：

https://en.wikipedia.org/wiki/Polytope#Properties https://en.wikipedia.org/wiki/Half-space_(geometry)

Answer 2

假设您没有矩形的变换矩阵。

如果您有矩阵，则将该点乘以逆变换矩阵。然后只需根据矩形顶部、左侧、右侧和底部的边界测试该点

凸多边形内的点

考虑一个点按顺时针方向环绕的凸多边形。

如果点位于多边形的每条边（线）的左侧，则该点位于该多边形内。

如果该点位于一条或多条边的右侧，则它位于多边形之外。

左侧定义为您的左侧，就像站在线的起点沿线的长度方向看一样。或者看钟面，分针在 3 分针左边是 4 右边是 2.

叉积

要找出点在直线的哪一侧，您需要从直线起点到终点的向量与从直线起点到该点的向量的叉积。如果叉积为正，则点在左边，如果为零，则在直线上，否则在右边。

剩下

const Point = (x, y) => ({x, y});
const Line = (p1, p2) => ({p1, p2});

function isPointLeft(l, p) { // l is line, p is point
    return 0 < (l.p2.x - l.p1.x) * (p.y - l.p1.y) - (l.p2.y - l.p1.y) * (p.x - l.p1.x);
}

顺时针检查

因此给出一组按顺时针顺序表示矩形的点，对照点检查每一边。如果都离开了，你就在里面。

函数 returns 如果点在多边形内部则为真。假设多边形的点按顺时针顺序排列

function isPointInsidePoly(point, poly) {
    var i = 0;
    const line = Line(poly[poly.length - 1]);
    while (i < poly.length) {
         line.p2 = poly[i++];
         if (!isPointLeft(line, point)) { return false }
         line.p1 = line.p2;
    }
    return true;
}

演示

简单演示创建一组点并旋转一个矩形。

渲染每个点。如果点在矩形内，则点画得大一点。

const Point = (x = 0, y = 0) => ({x, y});
const Line = (p1, p2) => ({p1, p2});
function isPointLeft(l, p) { // l is line, p is point
    return 0 < (l.p2.x - l.p1.x) * (p.y - l.p1.y) - (l.p2.y - l.p1.y) * (p.x - l.p1.x);
}
function isPointInsidePoly(point, poly) {
    var i = 0;
    const line = Line(poly[poly.length - 1]);
    while (i < poly.length) {
         line.p2 = poly[i++];
         if (!isPointLeft(line, point)) { return false }
         line.p1 = line.p2;
    }
    return true;
}


requestAnimationFrame(renderLoop);
const ctx = canvas.getContext("2d");
const [W, H] = [canvas.width, canvas.height];
const rand = (m, M) => Math.random() * (M - m) + m;
const setOf = (count, cb, i = 0, a = []) => {while (i < count) { a.push(cb(i++)) } return a}
function drawPoint(p, size) {
    ctx.strokeStyle = "#000";
    ctx.beginPath();
    ctx.arc(p.x, p.y, size, 0, Math.PI * 2);
    ctx.stroke();
}
const rect = {
    x: W / 2, y: H / 2,// x,y center of rectangle
    w: 80, h: 20,      // w h from center
    points: [Point(), Point(), Point(), Point()],
    update(angle) {
        const transform = (x, y, res) => {
            res.x = x * ax - y * ay + this.x;
            res.y = x * ay + y * ax + this.y;
        }
        const [ax, ay] = [Math.cos(angle), Math.sin(angle)];
        const p = this.points;
        transform( this.w,  this.h, p[0]);
        transform(-this.w,  this.h, p[1]);
        transform(-this.w, -this.h, p[2]);
        transform( this.w, -this.h, p[3]);  
    },
    draw(ctx) {
        ctx.lineWidth = 1;
        ctx.strokeStyle = "red";
        ctx.beginPath();
        for (const p of this.points) { ctx.lineTo(p.x, p.y) }
        ctx.closePath();
        ctx.stroke();
     }
}; 
const testPoints = setOf(20, () => Point(rand(20, W - 20), rand(20, H - 20)));
function renderLoop(time) {
    ctx.clearRect(0, 0, W, H);
    rect.update(time / 2300);
    rect.draw(ctx);
    for (const p of testPoints) {
        if (isPointInsidePoly(p, rect.points)) { drawPoint(p, 3) }
        drawPoint(p, 1);
    }
    requestAnimationFrame(renderLoop);
}

<canvas id="canvas" width="200" height="200"></canvas>

Answer 3

您首先需要通过计算任意两个对角的平均坐标来获得矩形的中心。然后，您还需要获得矩形的二维，这可以通过确定具有最大 y 值的点以及最小和最大 x 值的两个点来实现。旋转前的水平尺寸是第一点和第二点之间的距离，旋转前的垂直尺寸是第一点和第三点之间的距离。

下一步是检查点 E 是否足够靠近矩形的中心以使其位于矩形内部。最简单的方法是在旋转之前检查它与中心的水平和垂直距离，如果它们小于或等于，如果你在边缘上很好，相应尺寸的一半，那么它在矩形内。您可以使用任何旋转角度的适当 rotation matrix 获得旋转前的原始水平和垂直距离。

// center of rectangle
xO = (xA + xC) / 2;
yO = (yA + yC) / 2;
// point of largest y value
xPymax = xA;
yPymax = yA;
if (yB > yPymax)
{
    xPymax = xB;
    yPymax = yB;
}
if (yC > yPymax)
{
    xPymax = xC;
    yPymax = yC;
}
if (yD > yPymax)
{
    xPymax = xD;
    yPymax = yD;
}
// point of smallest x value
xPxmin = xA;
yPxmin = yA;
if (xB < xPxmin)
{
    xPxmin = xB;
    yPxmin = yB;
}
if (xC < xPxmin)
{
    xPxmin = xC;
    yPxmin = yC;
}
if (xD < xPxmin)
{
    xPxmin = xD;
    yPxmin = yD;
}
// point of largest x value
xPxmax = xA;
yPxmax = yA;
if (xB > xPxmax)
{
    xPxmax = xB;
    yPxmax = yB;
}
if (xC > xPxmax)
{
    xPxmax = xC;
    yPxmax = yC;
}
if (xD > xPxmax)
{
    xPxmax = xD;
    yPxmax = yD;
}
// dimensions of the rectangle
H = Math.sqrt((xPymax - xPxmin) * (xPymax - xPxmin) + (yPymax - yPxmin) * (yPymax - yPxmin));
V = Math.sqrt((xPymax - xPxmax) * (xPymax - xPxmax) + (yPymax - yPxmax) * (yPymax - yPxmax));
// calculating the original distances of point E from center
xdE = (xE - xO) * Math.cos(rot) + (yE - yO) * Math.sin(rot);
ydE = -(xE - xO) * Math.sin(rot) + (yE - yO) * Math.cos(rot);
// comparing to the dimentions of the rectangle
if (Math.abs(xdE) <= H / 2 && Math.abs(ydE) <= V / 2)  // this will consider a point on any edge as inside the rectangle, if you don't want this, just remove "="
    // the point is inside the rectangle
else
    // the point is outside the rectangle

检查给定点是否在旋转元素的边界内

Check if a given point is within the boundary of the rotated element

html

javascript

math

geometry

凸多边形内的点

叉积

剩下

顺时针检查

演示