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