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

问题描述 投票:0回答:3

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

所以我们有:

宽度:10

高度:10

旋转角度:45°

旋转矩形的坐标:A B C D

给定坐标:E

enter image description here

感谢任何帮助。

javascript html math geometry
3个回答
6
投票

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

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

凸多边形内的点

考虑一个凸多边形,其点沿顺时针方向旋转。

如果一个点位于多边形每条边(线)的左侧,则该点位于该多边形内部。

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

左侧定义为您的左侧,就像站在线条的起点沿其长度看一样。

叉积

要找出某个点在一条直线的哪一侧,您可以得到从直线起点到终点的向量与从直线起点到该点的向量的叉积。如果叉积为正,则该点位于左侧,如果为零,则位于直线上,否则位于右侧。

剩下了

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

顺时针检查

因此按顺时针顺序给出一组表示矩形的点,检查各边与点的关系。如果一切都还剩你就在里面了。

如果点在多边形内部,函数返回 true。假设多边形的点按顺时针顺序

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>


1
投票

任何多面体都可以表示为闭半空间的有限交集。半空间由线性不等式给出,例如 x+y+5<=0 which is the lower part of the line going through (-5,0) and (0,-5).

请参阅任何有关凸性的书籍或维基百科链接了解详细信息:

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


1
投票

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

下一步是检查 E 点是否足够接近矩形的中心以使其位于矩形内部。最简单的方法是在旋转之前检查其距中心的水平和垂直距离,如果它们小于或等于(如果您擅长位于边缘)相应尺寸的一半,则它位于矩形内部。对于任何旋转角度,您都可以使用适当的旋转矩阵获得旋转前的原始水平和垂直距离。

// 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
© www.soinside.com 2019 - 2024. All rights reserved.