Errors with finding largest non-axis aligned rectangle inscribed in polygon or geojson

108 Views Asked by At

I'm using d3plus.largestRect for this. It should be doing an approximation like this: https://web.archive.org/web/20210506163248/https://d3plus.org/blog/behind-the-scenes/2014/07/08/largest-rect/ and seems to generally get the right area, but it does not return a rectangle (with 90 degree angles) It returns a parallelogram.

I've seen a lot of stackoverflow posts and couldn't find anyone with this issue. I'm fine with using another library/code if needed.

// A file with a function that will return the maximum rectangle of a given geojson polygon
// using d3plus, Author: Daniel Smilkov

import "https://cdn.jsdelivr.net/npm/d3plus@2";
// const largestRect = require("d3plus").largestRect;
export function maxRect(polygon) {
    // polygon is a geojson polygon and aspectRatio is a number that is the ratio of width to height
    // we want to return a geojson polygon that is the maximum rectangle that fits inside the polygon
    // and has the given aspect ratio
    console.log(d3plus)
    // we need to convert the geojson polygon to an array of points
    var points = polygon.coordinates[0].map(function (coord) {
        return [coord[0], coord[1]];
    });

    // we use d3plus to calculate the rectangle
    var rect = d3plus.largestRect(points);
    console.log(rect)
    // we need to convert the rectangle back to a geojson polygon. rect.points will be an array of 5 points
    // the first and last point are the same
    var rectPolygon = {
        "type": "Polygon",
        "coordinates": [
            [
                [rect.points[0][0], rect.points[0][1]],
                [rect.points[1][0], rect.points[1][1]],
                [rect.points[2][0], rect.points[2][1]],
                [rect.points[3][0], rect.points[3][1]],
                [rect.points[0][0], rect.points[0][1]]
            ]
        ]
    };
    return rectPolygon;
}

// run the function
var polygon ={
          "type": "Polygon",
          "coordinates": [
            [
              [
                -110.06669998168945,
                27.583459194048213
              ],
              [
                -110.06601333618164,
                27.581709456471202
              ],
              [
                -110.05614280700684,
                27.58490460838308
              ],
              [
                -110.05056381225586,
                27.573416842281983
              ],
              [
                -110.06249427795409,
                27.570449607879656
              ],
              [
                -110.06155014038086,
                27.56748229324079
              ],
              [
                -110.02970695495605,
                27.575014550647136
              ],
              [
                -110.0387191772461,
                27.593348490311683
              ],
              [
                -110.06635665893555,
                27.583383119081834
              ],
              [
                -110.06669998168945,
                27.583459194048213
              ]
            ]
          ]
        }
var newPolygon = maxRect(polygon);
console.log(JSON.stringify(newPolygon));

Here's what the rectangle it returns looks like: enter image description here

geojson for the second picture

{
                    "type": "Polygon",
                    "coordinates": [
                        [
                            [
                                -121.498361304,
                                38.622343198
                            ],
                            [
                                -121.498593986,
                                38.622343198
                            ],
                            [
                                -121.498593986,
                                38.622508322
                            ],
                            [
                                -121.498565407,
                                38.622508355
                            ],
                            [
                                -121.498565823,
                                38.622465787
                            ],
                            [
                                -121.498410255,
                                38.622463692
                            ],
                            [
                                -121.498409129,
                                38.622508534
                            ],
                            [
                                -121.498361664,
                                38.622508588
                            ],
                            [
                                -121.498361304,
                                38.622343198
                            ]
                        ]
                    ]
                }

Messed up largest rect

0

There are 0 best solutions below