Let's say I have an array of objects called Point.
Point object has x and y values.
To make it more difficult, let's say there are no initial boundaries which means the rectangular area we want to find are bounded by Point objects. So, there are at least 4 Point objects.
so if the array only has 4 Point objects: Point(0,0), Point(100,0) Point(0,100) and Point(100,100), we want to return 100*100, the rectangular area.
This is easy part. But think about situation where there are more than 4 Point objects. How do you find the maximum rectangular area?
public int maxArea(Point[] points)
{
int area;
//do algo
return area;
}
EDIT: Just by looking at the min and max of y and x doesn't guarantee because im looking for the rectangular area that are free of Point objects. so there is nothing inside that maximum rectangle area
Approach: For area to be maximum of any rectangle the difference of length and breadth must be minimal. So, in such case the length must be ceil (perimeter / 4) and breadth will be floor(perimeter /4). Hence the maximum area of a rectangle with given perimeter is equal to ceil(perimeter/4) * floor(perimeter/4).
The maximum rectangle that has to be created should be made of continuous bars. For the sake of simplicity, we will assume that the width of each bar is 1. For example, for the following histogram that has 7 bars of the heights {7, 3, 6, 5, 6, 2, 7}, the maximum rectangular area, which is possible, is 15.
We can find length and breadth by assuming Length as ceil(perimeter/4) and Breadth as floor(perimeter/4), this gives the maximum value of the length and breadth of a rectangle by its perimeter. Hence, the area of a rectangle will be, ceil(perimeter/4) * floor(perimeter/4).
Let me first formulate the problem as I believe it was meant:
The rectangle to be found has horizontal (constant y) and vertical (constant x) borders, i.e. no "rotations".
The rectangle has at least one point on the 'internal' ('open') part of each of its edges, i.e. not at a corner. (it may have more than one point on any edge, and ALSO points at its corners.) This rules out the 'infinite' solutions, because all points have finite x,y. It also rules out the cases where we might intend to define the rectangle by only TopLeft and BottomRight points and similar constructs.
we look for the rectangle with the maximum area among all that satisfy the above conditions.
Assuming the above to be a correct (re)formulation of the problem, I believe that it is a two-dimensional optimization problem with potentially many 'local' optima. Any approach of the type "start at something and gradually improve" will only find the local optimum, but not necessarily the global one.
I have not been able to come up with something better than a O(N^2) approach, involving - roughly speaking - N times a local optimization, where each local optimization is O(N). I'll sketch the method with some code snippets (partially pseudo-code or remarks) for the essential part of the local optimization. The remainder is "more of the same" and should not be difficult to fill in.
To cut down on wording without becoming inaccurate, henceforth I will mean by "a point on the edge (of a recctangle)" a point that is on the 'inner' part of the edge, not at a corner. Likewise, by 'rectangle' I will mean an "eligible" reactangle, i.e. one that satisfies the basic conditions: no points inside, and at least one point on each of its edges.
Now, the LOCAL optimization is "defined" by a specific point from the points-set, in combination with a specific "border-type" from {Left, Top, Right, Bottom}. Assume that we have chosen a point L and border-type "Left"; The locally optimal solution is defined as the 'best" (largest area) rectangle that has L on its Left edge.
We're going to construct all (L,Left)-rectangles and keep track of the largest one that we find on the way.
Observe: any (L,Left)-rectangle that has point R on its right border, must have a point T on its Top border and a point B on its bottomm border, where
L.x < T.x < R.x
L.x < B.X < R.X
B.y < L.y < T.y
B.y < R.y < T.Y
Image now, that we scan the points in x-ordered fashion, starting after L.
At the one hand: before we can find R, the above conditions show that we must first encounter T and B.
At the other hand, as soon as we've found R, from all the points with y > L.y that we've encountered in-between, we will by now be bounded by the one with the lowest y. and likewise for the bottom-border.
With N the number of points {P}, Let index_X[] be the array of indices for the x-sorted points, such that P[index_X[i]]x <= P[index_X[j]].x whenever i is less than j.
Furthermore, let iL be the index of L in the x-sorted array: P[index_X[iL]] = L.
In the following code-snippets (VB-syntax; it shouldn't be too difficult to translate in whatever language you use), we first determine "some" T (a top-edge point) and "some" B (a bottom-edge point). Then, we keep scanning, and whenever we find a point R that completes a rectangle, we: (a) calculate the area to update the optimum if it is larger; (b) replace T or B by the found R (depending on whether R is above L or below), and repeat the search for R.
Dim indx As Integer = iL + 1 'first point to consider on the right of L
Dim T As PointF = Nothing
Dim B As PointF = Nothing
' find T,B
While (indx < N AndAlso (T = Nothing OrElse B = Nothing))
Dim Q As PointF = Pts(indx_X(indx))
If (Q.Y > L.Y) Then
' a candidate for T
If (T = Nothing) OrElse (Q.Y < T.Y) Then
T = Q
End If
ElseIf (Q.Y < L.Y) Then
' a candidate for B
If (B = Nothing) OrElse (Q.Y > B.Y) Then
B = Q
End If
Else
Return -1 'Failure for L altogether: Q has exactly the same y-value as L and we didn't find yet both T and B.
End If
indx += 1
End While
If (T = Nothing OrElse B = Nothing) Then
Return -1 'Failure for L: we have exhausted all points on the right without finding both T and B.
End If
' we have "some" T and B, now proceed to find all (L,Left) rectangles
' intialize result (= max area from (L,Left)-rectangles).
Dim result As Double = -1
' the next point to consider
indx += 1
' find successive rectangles, by searching for R, given L (fixed) and T,B (occasionally updated).
While (indx < N)
Dim R As PointF = Pts(indx_X(indx)) 'candidate
If (R.Y = L.Y) Then
' rectangle found, process it.
Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
If area > result Then
result = area
End If
' it all stops here: no further rectangles {L,Left) are possible as they would have this R inside.
Exit While
End If
If (R.Y > L.Y) Then
' a point with y > L.Y:
' if it is above T we can ignore it.
' if is below T, it is the R-bound for the rectangle bounded by L,T,B
If (R.Y < T.Y) Then
' process the rectangle
Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
If area > result Then
result = area
End If
' move on, understanding that for any NEXT rectangle this R must be the upperbound.
T = R
End If
Else 'R.Y < L.Y
' a point with y < L.Y
' if it is below B we can ignore it.
' if it is above B, it is the R-bound for the rectangle bounded by L,T,B
If (R.Y > B.Y) Then
' process the rectangle
Dim area As Double = (R.X - L.X) * (T.Y - B.Y)
If area > result Then
result = area
End If
' move on, understanding that for any NEXT rectangle this R must be the lowerbound.
B = R
End If
End If
indx += 1
End While
Return result
The overall solution is, of course: find for each point P, the optimum among opt(P,Left), opt(P,Right), opt(P,Top), opt(P,Bottom), and then find the maximum over all P. The varieties for Right, Top, Bottom are of course very similar to the opt(Left) that I sketched out above. The pre-sorting (to get indices for x-order and for y-order (for handling the (P,Top) and (P,Bottom)-cases) are O(nLogn), the local optimizations are each O(n) - view the code. So the overall complexity is O(n^2).
Note added - because the original formulation was not absolutely clear to me: IF rectangles can also be bounded by CORNER-points, then the above needs a few minor adjustments (mostly adding equal signs to inequality conditions), but it won't change the algorithm in essence.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With