How to find the maximum rectangle within a convex GIS polygon in Javascript
Background
Recently I was exploring on a new personal project and was considering to add this functionality of finding the maximum sized rectangle within a polygon based on GIS. I tried searching for such an algorithm and found a solution from the forums and tested it — https://community.esri.com/t5/spatial-data-science-questions/how-to-find-the-maximum-rectangle-contained-within-a-polygon/td-p/408977
In one of the replies within the post, there is another algorithm method by D3plus — https://d3plus.org/blog/behind-the-scenes/2014/07/08/largest-rect/. The article has 1st class visualization in explanation of the algorithm. Good to take a look.
While I am looking for a solution that works beyond convex polygons, I would just implement a simple algorithm first as I would like to progress on my project. I can plug in a more complex algorithm later.
I translated the algorithm into Javascript and alter it slightly so that it works for a slightly more complex polygon. Maybe I could just import D3plus’s amazing algorithm.
Algorithm Logic
The logic is to loop through each side of the convex polygon via 2x for-loops and extend out to form the largest possible rectangle. The algorithm is quite simple to implement.
My Changes
The original code assumes that the perpendicular lines will only intersect with just one other point (other than origin). However, this is not true for non-convex polygons. Instead, I store the intersections array and try to calculate for the largest rectangle that is within polygon. However, the introduction of this step complicates the algorithm but also seems to be able to handle a slightly more complex polygon.
For this example, the issue seems to be from the discrete search resulting in non-maximum result. The original algorithm would not be able to handle this example. However, given that this algorithm will not be able to handle non-convex polygon, it may be just luck that made it workable. I will come back to this problem again when my project is in a better stage.
