Нахождение минимальной ограничивающей рамки повернутого прямоугольника

function transformXCoordinate(x, xOrigin, y, yOrigin, theta) {
  return xOrigin + (x - xOrigin) * Math.cos(theta) - (y - yOrigin) * Math.sin(theta);
}

function transformYCoordinate(x, xOrigin, y, yOrigin, theta) {
  return yOrigin - (x - xOrigin) * Math.sin(theta) + (y - yOrigin) * Math.cos(theta);
}

function computeBoundingBox(x, y, w, h, theta) {
  let xCenter = x + (w / 2);
  let yCenter = y + (h / 2);

  let transX1 = transformXCoordinate(x, xCenter, y, yCenter, theta);
  let transX2 = transformXCoordinate(x + w, xCenter, y, yCenter, theta);
  let transX3 = transformXCoordinate(x + w, xCenter, y + h, yCenter, theta);
  let transX4 = transformXCoordinate(x, xCenter, y + h, yCenter, theta);

  let transY1 = transformYCoordinate(x, xCenter, y, yCenter, theta);
  let transY2 = transformYCoordinate(x + w, xCenter, y, yCenter, theta);
  let transY3 = transformYCoordinate(x + w, xCenter, y + h, yCenter, theta);
  let transY4 = transformYCoordinate(x, xCenter, y + h, yCenter, theta);

  let min_x = Math.min(transX1, transX2, transX3, transX4);
  let max_x = Math.max(transX1, transX2, transX3, transX4);
  let min_y = Math.min(transY1, transY2, transY3, transY4);
  let max_y = Math.max(transY1, transY2, transY3, transY4);
  
  return { x: min_x, y: min_y, w: max_x - min_x, h: max_y - min_y };
}

Тестовая скрипка здесь: https://jsfiddle.net/qdu8kmv9/

Я хочу сделать это более эффективным. Я использую этот вопрос в качестве справки.

Я попытался реализовать ответ Трубадура так:

function computeBoundingBox(x, y, w, h, theta) {
  let ct = Math.cos(theta);
  let st = Math.sin(theta);

  let hct = h * ct;
  let wct = w * ct;
  let hst = h * st;
  let wst = w * st;

  if (theta > 0) {
    if (theta < 1.5708) { // 0 < theta < 90
      return { x1: x - hst, y1: y, x2: x + wct, y2: y + hct + wst };
    } else { // 90 <= theta <= 180
      return { x1: x - hst + wct, y1: y + hct, x2: x, y2: y + wst };
    }
  } else {
    if (theta > -1.5708) { // -90 < theta <= 0
      return { x1: x, y1: y + wst, x2: x + wct - hst, y2: y + hct };
    } else { // -180 <= theta <= -90
      return { x1: x + wct, y1: y + wst + hct, x2: x - hst, y2: y };
    }
  }
}

Но это дало неверные результаты. Я неправильно перевожу или его ответ неверен?

1 ответ
1

Избегайте числовых неточностей

Вы можете использовать вектор по оси x, рассчитанный как ct, st вывести квадрант, а не использовать Math.PI / 2 или приближение 1.5708
ct >= 0 для квадроциклов 1 и 4 и st >= 0 для квадроциклов 2 и 3

Уменьшить сложность

Вместо того, чтобы рассчитывать ширину {wct: w * ct, wst: w * st} и высота {hct: h * ct, hst: h * st}векторов в том же направлении, вы можете вычислить вектор высоты, повернутый на 90 по часовой стрелке {hct: -h * st, hst: h * ct}

Таким образом, все последующие вычисления являются дополнениями, а код немного легче читать и поддерживать.

Избегайте избыточного кода

Когда блок операторов возвращается, за ним не должно следовать предложение else.

например

if (foo) { 
   return bar; 
} else { 
   return foo; 
}

должно быть

if (foo) { 
    return bar; 
} 
return foo;

Избегайте повторения кода

Вы возвращаете один и тот же объект 4 раза. Используйте функцию для создания возвращаемого объекта. Смотрите переписать;

Переписать

  • Предполагая, что ось x направлена ​​вдоль w, а ось y направлена ​​вниз вдоль h.
  • Отсутствие начала координат предполагает, что вращение происходит в точке x, y.
function computeBoundingBox(x, y, w, h, theta) {
    const result = (x1, x2, y1, y2) => ({x1, y1, x2, y2});
    const ux = Math.cos(theta); // unit vector along w
    const uy = Math.sin(theta);
    const wx = w * ux, wy = w * uy; // vector along w
    const hx = h *-uy, hy = h * ux; // vector along h

    if (ux > 0) { 
        return uy > 0 ?
            result(x + hx, x + wx,      y,      y + hy + wy) :
            result(x,      x + wx + hx, y + wy, y + hy);                
    }
    return uy > 0 ?
        result(x + hx + wx, x,      y + hy,      y + wy) :
        result(x + wx,      x + hx, y + wy + hy, y);                
}

Использование вычитания, поскольку оно немного быстрее (проверка типа не требуется) и немного компактнее.

function computeBoundingBox(x, y, w, h, theta) {
    const result = (x1, x2, y1, y2) => ({x1, y1, x2, y2});
    const ux = -Math.cos(theta); 
    const ny = Math.sin(theta), uy = -ny;
    return ux < 0 ? 
        (uy < 0 ?
            result(x - h*ny, x - w*ux, y, y - h*ux - w*uy) :
            result(x, x - w*ux - h*ny, y - w*uy, y - h*ux)) : 
        (uy < 0 ?
            result(x - h*ny - w*ux, x, y - h*ux, y - w*uy) :
            result(x - w*ux, x - h*ny, y - w*uy - h*ux, y));
}       

Или без функции возврата

function computeBoundingBox(x, y, w, h, theta) {
    const ux = -Math.cos(theta); 
    const ny = Math.sin(theta), uy = -ny;
    return ux < 0 ? 
        (uy < 0 ?
            {x1: x - h*ny, x2: x - w*ux, y1: y, y2: y - h*ux - w*uy} :
            {x1: x, x2: x - w*ux - h*ny, y1: y - w*uy, y2: y - h*ux}) : 
        (uy < 0 ?
            {x1: x - h*ny - w*ux, x2: x, y1: y - h*ux, y2: y - w*uy} :
            {x1: x - w*ux, x2: x - h*ny, y1: y - w*uy - h*ux, y2: y});
}       

Пример

const ctx = canvas.getContext("2d");
var x = 90, y = 75, w = 70, h = 25;
var x1 = 210, y1 = 75;
function computeBoundingBox(x, y, w, h, theta) {
    const result = (x1, x2, y1, y2) => ({x1, y1, x2, y2});
    const ux = Math.cos(theta); // unit vector along w
    const uy = Math.sin(theta);
    const wx = w * ux, wy = w * uy; // vector along w
    const hx = h *-uy, hy = h * ux; // vector along h

    if (ux > 0) { 
        return uy > 0 ?
            result(x + hx, x + wx,      y,      y + hy + wy) :
            result(x,      x + wx + hx, y + wy, y + hy);                
    }
    return uy > 0 ?
        result(x + hx + wx, x,      y + hy,      y + wy) :
        result(x + wx,      x + hx, y + wy + hy, y);                
}

function computeAABBCenter(x, y, w, h, theta) {
    const ux = Math.cos(theta) * 0.5; // half unit vector along w
    const uy = Math.sin(theta) * 0.5;
    const wx = w * ux, wy = w * uy; // vector along w
    const hx = h *-uy, hy = h * ux; // vector along h
    
    // all point from top left CW
    const x1 = x - wx - hx;
    const y1 = y - wy - hy;
    const x2 = x + wx - hx;
    const y2 = y + wy - hy;
    const x3 = x + wx + hx;
    const y3 = y + wy + hy;
    const x4 = x - wx + hx;
    const y4 = y - wy + hy;
    
    return {
      x1: Math.min(x1, x2, x3, x4),
      y1: Math.min(y1, y2, y3, y4),
      x2: Math.max(x1, x2, x3, x4),
      y2: Math.max(y1, y2, y3, y4),
    };
}



function draw(x,y,w,h,a) {
    ctx.setTransform(1,0,0,1,x,y);
    ctx.rotate(a);
    ctx.strokeRect(0, 0,w,h);
    ctx.setTransform(1,0,0,1,0,0);
}
function drawCentered(x,y,w,h,a) {
    ctx.setTransform(1,0,0,1,x,y);
    ctx.rotate(a);
    ctx.strokeRect(-w/2,-h/2,w,h);
    ctx.setTransform(1,0,0,1,0,0);
}
function drawBounds(bounds) {
    ctx.strokeRect(bounds.x1,bounds.y1, bounds.x2-bounds.x1, bounds.y2-bounds.y1);
}

requestAnimationFrame(renderLoop);
function renderLoop(time) {
    ctx.setTransform(1,0,0,1,0,0);
    ctx.clearRect(0, 0, 300, 150);
    const ang = time / 1000;
    ctx.strokeStyle = "#F00";
    drawBounds(computeBoundingBox(x, y, w, h, ang));
    drawBounds(computeAABBCenter(x1, y1, w, h, ang));
    ctx.strokeStyle = "#000";
    draw(x, y, w, h, ang);
    drawCentered(x1, y1, w, h, ang);
    requestAnimationFrame(renderLoop);

}
canvas { border: 1px solid black }
<canvas id="canvas"></canvas>

  • Это хороший ответ. Не уверен, кто проголосовал за него, но я предполагаю, что причина в том, что у него все еще есть проблема, когда он вращается вокруг нижнего левого угла, а не в центре, поэтому у него все те же проблемы, что и в исходном сообщении.

    – Райан Пешель

  • @RyanPeschel Объекты обычно вращаются вокруг начала координат, в этом случае начало координат задается координатами x, y. Если OP хочет повернуться вокруг любого из углов, установите начало координат x, y в угол, например, внизу справа. computeBoundingBox(x + w, y + h, w, h, ang); в правом верхнем углу computeBoundingBox(x + w, y , w, h, ang); и так далее

    – Слепой67

  • Итак, если я хочу, чтобы ограничивающая рамка прямоугольника вращалась вокруг его центра, я просто делаю computeBoundingBox(x + w / 2, y + h / 2, w / 2, h / 2, ang); ? Кроме того, ваш код выдает некоторые ошибки, например xax а также xay не определены. Есть идеи, что это должно быть?

    – Райан Пешель



  • @RyanPeschel. Я поменял имена и забыл скопировать это во второй фрагмент. xax и xay – единичный вектор, например, ось x x и ось x y. Исправлю сейчас

    – Слепой67

  • Привет, спасибо за исправление. Был ли мой последний вопрос о ограничивающей рамке правильным? Потому что я пытаюсь computeBoundingBox(x + w / 2, y + h / 2, w / 2, h / 2, ang); с вашим кодом, и он все еще не дает мне правильную ограничивающую рамку. Извините, но я действительно борюсь с этим (пытаюсь заставить ограничивающую рамку прямоугольника вращаться вокруг его центра)

    – Райан Пешель

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *