Find rectangle vertices given its coordinates, width and height

Question

I have a rectangle, that could be rotated. At every rotation, I need to to know its new top, left, right and bottom vertices.

I've tried to loop through the new rectangle coordinates, but I want to calculate vertices without a loop to reduce execution time

At first, I calculate new rotated coordinates and then I find new vertices.

rotatedRectCorners(element, center, angle) {
    const theta = (Math.PI / 180) * angle
    const ox = center.x
    const oy = center.y
    const xAx = Math.cos(theta)  // x axis x
    const xAy = Math.sin(theta)  // x axis y
    const x = element.left - ox  // move rectangle onto origin
    const y = element.top - oy

    return {
        topLeft: {
            x: x * xAx - y * xAy + ox,   // Get the top left rotated position
            y: x * xAy + y * xAx + oy
        },
        topRight: {
            x: (x + element.width) * xAx - y * xAy + ox,   // Get the top right rotated position
            y: (x + element.width) * xAy + y * xAx + oy
        },
        bottomRight: {
            x: (x + element.width) * xAx - (y + element.height) * xAy + ox,   // Get the bottom right rotated position
            y: (x + element.width) * xAy + (y + element.height) * xAx + oy
        },
        bottomLeft: {
            x: x * xAx - (y + element.height) * xAy + ox,   // Get the bottom left rotated position
            y: x * xAy + (y + element.height) * xAx + oy
        }
    }
}

rectVertices(element, center, angle) {
    const corners = rotatedRectCorners(element, center, angle)
    const vertices = {
        top: {x: 0, y: 0},
        left: {x: 0, y: 0},
        right: {x: 0, y: 0},
        bottom: {x: 0, y: 0}
    }
    let maxX = null
    let minX = null
    let minY = null
    let maxY = null
    each(corners, (corner) => {
        if (maxX === null) {
            maxX = corner.x
            vertices.right = corner
        }
        if (minX === null) {
            minX = corner.x
            vertices.left = corner
        }
        if (minY === null) {
            minY = corner.y
            vertices.top = corner
        }
        if (maxY === null) {
            maxY = corner.y
            vertices.bottom = corner
        }
        if (corner.y > maxY) {
            maxY = corner.y
            vertices.bottom = corner
        }
        if (corner.x > maxX) {
            maxX = corner.x
            vertices.right = corner
        }
        if (corner.x < minX) {
            minX = corner.x
            vertices.left = corner
        }
        if (corner.y < minY) {
            minY = corner.y
            vertices.top = corner
        }
    })

    return vertices
}

Without a loop? Complex computations need algorithms like a loop otherwise why use a program? Using loops is what reduces the times or at least properly written ones. — zer00ne
@BohdanVovchuck you're right in that this sort of problem can be solved with matrix multiplication, but in order to implement matrix multiplication in javascript, you're going to need a loop. zer00ne is right, loops aren't automatically inefficient. — rh16
If you're intention is to improve the execution time then you could improve the rotatedRectCorners function by storing the product calculations (e.g. x * xAx) in an intermediate variable, at present each one is calculated twice before a result is returned. You can also reduce the number of conditionals in rectVertices by half e.g. if (maxX === null || corner.x > maxX) { maxX = corner.x; vertices.right = corner } This will reduce the number of instructions the processor needs to execute but the speed improvement will be in fractions of milliseconds. — Dan Nagle

MBo MBo · Accepted Answer · 2019-05-28T04:13:09

Let number rectangle vertices from top left corner in clockwise direction. We can see that V[0] is the leftmost vertex in angle range 0..Pi/2 (90 degrees, angle in CCW direction), V[1] becomes the leftmost one in angle range Pi/2..Pi and so on.

So we can reconsile two arrays cyclically corresponding to rotation angle

V[0]    V[1]    V[2]    V[3]   
           <==>                      //small angle
left    top     right  bottom


V[2]    V[3]     V[0]    V[1]   
           <==>                     //angle in range 180..270 (Pi..3Pi/2)
left    top     right  bottom




left_index = angle / 90   //integer division if possible in JS
top_index = (1 + angle / 90) % 4 
right_index = (2 + angle / 90) % 4 
bottom_index = (3 + angle / 90) % 4

Not that in any case you have to calculate vertices coordinates (much more time)

Find rectangle vertices given its coordinates, width and height

1 Answers