Iterate grid squares in a rotated rectangle

Question

Given a rectangle with a defined width, height, x coordinate, and y coordinate is applied to a grid and rotated.

How can I find and iterate through all the cells inside the rectangle?

Example image with the rectangle in black and desired cells in red.

Preferred solution in Javascript but I'm happy to accept anything I can port.

https://stackoverflow.com/a/41899250/2027146 This allows me to find the corners of the rectangle but I'm not sure how to iterate through the inner cell positions — Milk, Sep 07 '22 at 02:01

Richard Henage · Accepted Answer · 2022-09-07T03:52:59.077

THIS WORKS NOW
Basically, find the corners, loop through all the squares between those corners and grab only the ones that have the right angles between the square and the containing rectangle corners, compared to the angles between the corners of the containing rectangle.
Angle from top corner to square in question > angle from top corner to right corner (and the same for the other corners, except the bottom right corner, which has an additional case)

use the arrow keys to rotate the rectangle

function drawRect (angle) {
  let rotated = rotateRect(30, 21, angle)
  // Rectangle is rotated around its center

  let newHTML = ""
  rotated.forEach(square=>{
    newHTML += `<div class="square" style="left: ${square.x * 10}px; top: ${square.y * 10}px"></div>`
  })
  document.body.innerHTML = newHTML + "<div>Use the Left and Right Arrow Keys</div>"
}

let angle = 1
drawRect(angle)

document.addEventListener("keydown", event=>{
  if (event.key == "ArrowRight") {
    angle += 0.1
  }
  if (event.key == "ArrowLeft") {
    angle -= 0.1
  }
  drawRect(angle)
})


function rotateRect(width, height, rotate /* in radians */) {
  // Call the center of the rectangle [0,0]
    rotate = Math.round(rotate * 1000) / 1000
  while (rotate <= 0) rotate += Math.PI * 2
  let fourCorners = []
  fourCorners.push({x: Math.cos(Math.atan2(-height, -width) + rotate) * distance(width/2, height/2), y: Math.sin(Math.atan2(-height, -width) + rotate) * distance(width/2, height/2)})
  fourCorners.push({x: Math.cos(Math.atan2(-height, width) + rotate) * distance(width/2, height/2), y: Math.sin(Math.atan2(-height, width) + rotate) * distance(width/2, height/2)})
  fourCorners.push({x: Math.cos(Math.atan2(height, width) + rotate) * distance(width/2, height/2), y: Math.sin(Math.atan2(height, width) + rotate) * distance(width/2, height/2)})
  fourCorners.push({x: Math.cos(Math.atan2(height, -width) + rotate) * distance(width/2, height/2), y: Math.sin(Math.atan2(height, -width) + rotate) * distance(width/2, height/2)})

  for (let i = 1; i < rotate / (Math.PI / 2); i++) {
      fourCorners.unshift(fourCorners.pop())
  }
    
  // let leftCorner = fourCorners.sort((a, b)=>a.x-b.x)[0]
  // let rightCorner = fourCorners.sort((a, b)=>b.x-a.x)[0]
  // let topCorner = fourCorners.sort((a, b)=>a.y-b.y)[0]
  // let bottomCorner = fourCorners.sort((a, b)=>b.y-a.y)[0]
  let topCorner = fourCorners[0]
  let rightCorner = fourCorners[1]
  let bottomCorner = fourCorners[2]
  let leftCorner = fourCorners[3]
  
  let yMin = topCorner.y
  let xMax = rightCorner.x
  let yMax = bottomCorner.y
  let xMin = leftCorner.x
  
  let t_l_angle = Math.atan2(topCorner.y - leftCorner.y, topCorner.x - leftCorner.x)
  let t_r_angle = Math.atan2(rightCorner.y - topCorner.y, rightCorner.x - topCorner.x)
  let b_r_angle = Math.atan2(bottomCorner.y - rightCorner.y, bottomCorner.x - rightCorner.x)
  let b_l_angle = Math.atan2(leftCorner.y - bottomCorner.y, leftCorner.x - bottomCorner.x)
  
  
  let coveredSquares = []
  for (let x = Math.ceil(xMin); x < Math.floor(xMax); x++) {
    for (let y = Math.ceil(yMin); y < Math.floor(yMax); y++) {
      let local_t_l_angle = Math.atan2(y - leftCorner.y, x - leftCorner.x)
      let local_t_r_angle = Math.atan2(y - topCorner.y, x+1 - topCorner.x)
      let local_b_r_angle = Math.atan2(y+1 - rightCorner.y, x+1 - rightCorner.x)
      let local_b_l_angle = Math.atan2(y+1 - bottomCorner.y, x - bottomCorner.x)
      if (
        (local_t_l_angle > t_l_angle) && 
        (local_t_r_angle > t_r_angle) && 
        (local_b_r_angle > b_r_angle || local_b_r_angle < b_r_angle - Math.PI) && 
        (local_b_l_angle > b_l_angle)
      ) {
        coveredSquares.push({x, y})
      }
    }  
  }
  console.log(coveredSquares)
  return coveredSquares
}

function distance(x, y) {
  return Math.sqrt((x*x)+(y*y))
}

body {
}

.square {
  position: absolute;
  background-color: red;
  width: 9px;
  height: 9px;
  z-index: 1000;
  transform: translate(150px, 150px);
}

Iterate grid squares in a rotated rectangle

1 Answers1