Getting maximum rectangle inside polygon

Questions
1

I am using three.js and I draw polygons inside viewer this polygon represented as Vector2[].

I want to get the maximum rectangle can be drawn inside that polygon represented as Vector2[]

I want to have a function that I pass a Vector2[] that represents a polygon and it returns back Vector2[] that represents the max rectangle can be drawn inside that polygon.

This is the function i use but it someetimes draw the rectangle outside the polygon

findLargestRectangle(polygon: Vector2[]): Vector2[] | null {
    let maxArea = 0;
    let bestRectangle: Vector2[] | null = null;
    
    for (let i = 0; i < polygon.length - 1; i++) { // Skip the last point
      for (let j = i + 1; j < polygon.length - 1; j++) { // Skip the last point
        const base1 = polygon[i];
        const base2 = polygon[j];
        const baseVector = new Vector2().subVectors(base2, base1);
        
        for (let k = 0; k < polygon.length - 1; k++) { // Skip the last point
          if (k === i || k === j) continue;
          
          const perpVector = new Vector2(-baseVector.y, baseVector.x).normalize();
          const height = perpVector.dot(new Vector2().subVectors(polygon[k], base1));
          
          const corner1 = base1.clone().add(perpVector.clone().multiplyScalar(height));
          const corner2 = base2.clone().add(perpVector.clone().multiplyScalar(height));
          
          // Check if both corner points are within the polygon
          if (PolygonHelperFunctions.isPointInPolygon(corner1, polygon) && PolygonHelperFunctions.isPointInPolygon(corner2, polygon)) {
            const rectangleArea = PolygonHelperFunctions.getRectangleArea(base1, base2, corner2, corner1);
            if (rectangleArea > maxArea) {
              maxArea = rectangleArea;
              bestRectangle = [base1, base2, corner2, corner1];
            }
          } else {
            // Handle the case where corners are outside the polygon
            const smallestEdge = PolygonHelperFunctions.findSmallestEdge(polygon);
            const smallBase1 = polygon[smallestEdge.index1];
            const smallBase2 = polygon[smallestEdge.index2];
            
            const smallBaseVector = new Vector2().subVectors(smallBase2, smallBase1);
            const smallHeight = perpVector.dot(new Vector2().subVectors(polygon[k], smallBase1));
            
            const smallCorner1 = smallBase1.clone().add(perpVector.clone().multiplyScalar(smallHeight));
            const smallCorner2 = smallBase2.clone().add(perpVector.clone().multiplyScalar(smallHeight));
            
            // Ensure it's a pure rectangle
            const smallBaseLength = smallBaseVector.length();
            const smallSide1 = smallCorner1.distanceTo(smallBase1);
            const smallSide2 = smallCorner2.distanceTo(smallBase2);
            
            if (
              smallBaseLength === smallBaseVector.length() &&
              smallSide1 === smallSide2 &&
              Math.abs(perpVector.dot(smallBaseVector)) < 1e-10 // Check that vectors are perpendicular
            ) {
              const smallRectangleArea = PolygonHelperFunctions.getRectangleArea(smallBase1, smallBase2, smallCorner2, smallCorner1);
              if (smallRectangleArea > maxArea) {
                maxArea = smallRectangleArea;
                bestRectangle = [smallBase1, smallBase2, smallCorner2, smallCorner1];
              }
            }
          }
        }
      }
    }
2

It is hard to guess what is wrong by staring at the code. My suggestion is to find the simplest possible case (e.g. with triangle) where the rectangle is wrong and then debug exactly this case by checking which calculation messes the things up.

1 Like
3

This also sounds like a problem with no optimal solution unless there are many constraints placed on the input geometry.
such as… axis aligned rectangle, and convex polygon… but even then. Sounds REAL hard.

1 Like