Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>Let me first formulate the problem as I believe it was meant:</p> <ul> <li><p>The rectangle to be found has horizontal (constant y) and vertical (constant x) borders, i.e. no "rotations".</p></li> <li><p>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.</p></li> <li><p>we look for the rectangle with the maximum area among all that satisfy the above conditions.</p></li> </ul> <p>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.</p> <p>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.</p> <p>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.</p> <p>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.</p> <p>We're going to construct all (L,Left)-rectangles and keep track of the largest one that we find on the way.</p> <p>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</p> <pre><code>L.x &lt; T.x &lt; R.x L.x &lt; B.X &lt; R.X B.y &lt; L.y &lt; T.y B.y &lt; R.y &lt; T.Y </code></pre> <p>Image now, that we scan the points in x-ordered fashion, starting after L.</p> <p>At the one hand: before we can find R, the above conditions show that we must first encounter T and B.</p> <p>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.</p> <p>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 &lt;= P[index_X[j]].x whenever i is less than j.</p> <p>Furthermore, let iL be the index of L in the x-sorted array: P[index_X[iL]] = L.</p> <p>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.</p> <pre><code> 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 &lt; N AndAlso (T = Nothing OrElse B = Nothing)) Dim Q As PointF = Pts(indx_X(indx)) If (Q.Y &gt; L.Y) Then ' a candidate for T If (T = Nothing) OrElse (Q.Y &lt; T.Y) Then T = Q End If ElseIf (Q.Y &lt; L.Y) Then ' a candidate for B If (B = Nothing) OrElse (Q.Y &gt; 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 &lt; 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 &gt; 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 &gt; L.Y) Then ' a point with y &gt; 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 &lt; T.Y) Then ' process the rectangle Dim area As Double = (R.X - L.X) * (T.Y - B.Y) If area &gt; 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 &lt; L.Y ' a point with y &lt; 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 &gt; B.Y) Then ' process the rectangle Dim area As Double = (R.X - L.X) * (T.Y - B.Y) If area &gt; 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 </code></pre> <p>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).</p> <p>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.</p>
    singulars
    1. This table or related slice is empty.
    1. POFind a maximum rectangular area given an array of points
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USBert te Velde
    1. USBert te Velde
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POFind a maximum rectangular area given an array of points
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. This table or related slice is empty.
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload