evryway/lir

Largest Interior Rectangle implementation in C# for Unity.

lir

Largest Interior Rectangle implementation in C# for Unity.

REQUIREMENTS

Unity.Mathematics is required for int2 and float2x2 (2D integer vectors and float 2x2 matrices, respectively).

The simplest way to get this package is to open the "Package Manager" window in Unity, click the plus icon, select "add package from git URL ..." and then enter "com.unity.mathematics" (without quotes).

USAGE

LargestInteriorRectangle.cs

the LargestInteriorRectangle class contains various static methods for processing Vector2 arrays. The primary methods are:

CalculateInteriorCells(Vector2[] vs, out float[] xs, out float[] ys, out int[,] cells)

This method takes a list of Vector2s representing a simple polygon (ordered counter-clockwise, concave, non-intersecting) and generates three output arrays : the xs (ordered, filtered unique x coordinates for all vertices), the ys (ordered, filtered, unique y coordinates for all vertices) and the 2D cells array representing each cell of the projection of the xs and ys arrays into a 2D rectangle array. Each cell is marked as exterior (0) or interior (1) based on it's position relative to the polygon.

CalculateLargestInteriorRectangle(float[] xs, float ys[], int[,] cells, out Bound2D best)

this method takes the xs, ys and cells arrays created by CalculateInteriorCells and calculates the axis-aligned Largest Interior Rectangle. The bound of this rectangle is output in best.

Along with these methods, there are a variety of other geometry processing methods:

CalculateConcavePolygon (Vector2[] vs)

Sorts a point set into an ordered array (counter-clockwise) representing a concave polygon.

CalculateConvexHull(Vector2[] vs, out Vector2[] hull_vs)

Calculates a convex hull, given a point set.

CalculateConvexPolygonArea(Vector2[] vs)

calculates the area of a convex polygon, given a CCW ordered point array representing that convex polygon.

CalculatePrimaryAxis(Vector2[] vs, out Vector2 axis, out float eigenvalue)

Given a point set in vs, calculates the primary axis, and the corresponding eigenvalue. The primary axis is the line through the point set representing the largest variance.

CalculateEigenValues(float2x2 mat, out float v1, out float v2)

Given a 2x2 matrix, calculates the eigenvalues.

CalculateEigenVector(float 2x2 A, float eigenvalue)

Given a 2x2 matrix and an eigenvalue, calculates an eigenvector.

Bound2D.cs

This class represents a 2D bound. The bound is not required to be axis aligned. The bound is constructed from a centre point, a 2D size and the primary axis (the first element of the 2D size).

Extensions.cs

This class contains some Vector2 extension methods to simplify the code (Rotate for simple 2D rotations, and F3() to make logging more concise).

LargestInteriorRectangleTests.cs

This class contains a selection of tests across the LargestInteriorRectangle methods.

BACKGROUND READING

please see https://www.evryway.com/largest-interior/ for background details.

lir's Issues

Exception using the following points

Hi,

I am getting an System.IndexOutOfRangeException in LargestInteriorRectangle.cs using the following polygon:

496847.2188 | 181705.7188
496847.2188 | 181712.2656
496852.5938 | 181712.2813
496855.8438 | 181712.2813
496855.8438 | 181713.7813
496861.0313 | 181713.7969
496861.125 | 181702.0781
496861.125 | 181701.8281
496858.4688 | 181701.8125
496857.4063 | 181701.8125
496854.0313 | 181701.8125
496854 | 181705.7344
496852.6563 | 181705.7188
496852.7188 | 181701.2188
496849.1875 | 181701.2188
496847.1875 | 181701.2188
496847.1875 | 181704.25
496849.1875 | 181704.25
496849.1875 | 181705.7188
496847.2188 | 181705.7188

Kind Regards

Encountered an Unexpected Output

Input:

new Vector2(108.504409613815f,
  117.952273301153f),
new Vector2(109.625073657792f,
  119.44319897989f),
new Vector2(110.66182151476f,
  120.99365090112f),
new Vector2(111.611498518359f,
  122.598911274979f),
new Vector2(108.702048440185f,
  124.738185726188f),
new Vector2(96.8291239976288f,
  108.590804109221f),
new Vector2(98.6259551665153f,
  109.537436129365f),
new Vector2(100.225651341531f,
  110.496456163888f),
new Vector2(101.770032345062f,
  111.542226021415f),
new Vector2(103.25439886011f,
  112.671563582988f),
  new Vector2(104.674234184659f,
  113.881032445812f),
new Vector2(106.025217975309f,
  115.166952379701f),
new Vector2(107.30323939343f,
  116.525410525468f),

Output: best area : 22.23052 (105.978, 110.631) (5.448, 4.081)

visualize the result

Some cases throwing IndexOfOutRangeException

Hi again,

I think I have found an issue with the algorithm. I believe this is due to multiple vertices along the same line. i.e. the dark blue point on the middle right.

Here are the coordinates for the shape:

-6.012309074, -2.394122601
0.561122477, -2.394122601
0.56188339, -8.094342232
0.562643945, -13.79456139
-6.010787487, -13.79456139
-9.057126045, -13.79471302
-9.05653286, -9.563955307
-6.010194302, -9.563802719
-6.010483265, -8.186531067
-10.22067451, -8.238635063
-10.22199726, -2.395780802
-6.012309074, -2.394122601

Currently I am just checking whether the index is within range and continuing on the loop.

Regards,

Joe

The Current Approach Is Not Robust Enough

Thank you very much for your excellent blog and code, which have inspired me greatly. I have noticed a small issue:

1. The cell internal labeling process is not robust
   Labeling non-inner rectangles separately from the top, bottom, left, and right might yield incorrect results under special circumstances. For example:

   new Vector2(2,0),
   new Vector2(2, 9),
   new Vector2(9, 9),
   new Vector2(9, 1),
   new Vector2(3, 1),
   new Vector2(3, 0),
   new Vector2(10, 0),
   new Vector2(10, 10),
   new Vector2(1, 10),
   new Vector2(1, 0),

The result is: (6.500, 5.000), (7.000, 10.000), (1.000, 0.000)

Perhaps, it would be better to first identify an inner rectangle, then search for suitable rectangles around it (at the front, back, left, and right) to get the results. Here is a Python implementation (I'm sorry, I don't know C#):

def fill_polygon(matrix, startx, starty):
    rows = len(matrix)
    cols = len(matrix[0])

    def dfs(x, y):
        if x < 0 or y < 0 or x >= rows or y >= cols or matrix[x][y] in (1, 2):
            return
        matrix[x][y] = 2
        dfs(x + 1, y)
        dfs(x - 1, y)
        dfs(x, y + 1)
        dfs(x, y - 1)

    dfs(startx, starty)

    return matrix


a = [
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 0],
    [0, 1, 0, 1, 0],
    [0, 0, 1, 0, 0]
]

print(fill_polygon(a, 2, 1))
"""
[
    [0, 0, 0, 0, 0],
    [0, 1, 1, 0, 0],
    [1, 2, 2, 1, 0],
    [0, 1, 2, 1, 0],
    [0, 0, 1, 0, 0]
]
"""

2. The efficiency is quite low when there are too many points, for example, over 1000 points.
   Maybe a simplification algorithm could be used for pre-processing: https://github.com/mourner/simplify-js
   Especially when there are arcs in the graph, using pre-processing could improve both the accuracy of the results and the computational efficiency.

3. When there are too few points, such as with a rhombus formed by 4 points, it is impossible to get a result. In this case, perhaps xs and ys could be expanded to 50 elements each.
   I did a test, and when the number of elements for x and y are both 50, the processing time is less than 10ms.

Availability outside Unity

What would it take to make this algorithm available outside Unity? Ideally it would be a NuGet package one can add to their project.

Although I'm able to reference Unity as a NuGet package, Unity.Mathematics hasn't been packaged yet and can't be easily added.

Instead I tried to look for other packages which may provide alternative implementations of int2 and float2x2 struct types without much luck.

Thanks!