largestRect not correct

[bhaktatejas922]

Expected Behavior

I should be getting a max rectangle but I get some really weird results. Why is this happening? Using lat/long for my points as shown

Current Behavior

https://stackoverflow.com/questions/74083520/non-max-rectangle-when-using-d3plus-largestrect

Steps to Reproduce (for bugs)

1. use this geojson and code here https://stackoverflow.com/questions/74083520/non-max-rectangle-when-using-d3plus-largestrect

When I use d3plus.largestRect it often doesnt return the largest inscribed rectangle. Any ideas whats going on, or what I should do to try to debug?

Someone took it from d3plus and made it its own repo here if its helpful.

https://github.com/rossjs/largest-rect-in-poly-geojson

export function maxRect(polygon, userOptions) {
    // 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
    // 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]];
    });
    if (userOptions) {
        console.log("userOptions", userOptions)
        var options = userOptions;
    } else {
        var options = {
        };
    }
    // we use d3plus to calculate the rectangle
    // aspect ratio is the ratio of width to height
    // var rect = largestRectInPoly(points, options);
    var rect = largestRect(points, options);
    console.log(rect)
    return rect;
}

Example where rectangle is wrong. This happens regardless of which options I pass to it

{
                    "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
                            ]
                        ]
                    ]
                }

Some examples:

[bhaktatejas922]

@dsmilkov any ideas why this may be?

[davelandry]

@bhaktatejas922 the largestRect function was originally intended to accept an array of pixel-based polygonal points as it's first argument, not an array of lat/long coordinate points. In some cases it probably works fine, but my guess here is that the lat/long coordinate points are too close together in pixel space to get an accurate estimate, as we may be bumping into sub-pixel rounding errors in JavaScript (if you round all the coordinates you provided to the nearest whole pixel, you will get a list of identical points).

I can't see the steps in your code that you used to take the output and draw the final polygon, but I would recommend moving your largestRect calculation after the place in your code where you calculate it's pixel x/y coordinates for drawing, and pass those x/y positions to the largestRect function.

Another thing you may want to test here, is that lat/long positions typically map to y/x positions, not x/y, so that underlying function might need to change it's map function to [coord[1], coord[0]]

[bhaktatejas922]

Ah yeah should've mentioned that those original coordinates are already in long, lat form.

I'm just taking the outputted points and pasting them into geojson.io directly for display.

I should probably explore making it less prone to rounding errors it sounds like. Do you think multiplying it by 1000 or 1000000 would help? Tried that already

[bhaktatejas922]

so those issues with the ultra small rectangles I resolved (repeat points). However I still get max rectangles that are not actually fitting at times. Weirdly, they seem to happen mostly at the 90 degree and 0 degree angle. Tried to specify angles such that 90, -90 and 0 arent included but it still tries -0, -90 as an angle for some reason