Timeline for Get Largest Inscribed Rectangle of a Concave Polygon
Current License: CC BY-SA 3.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 21, 2017 at 18:12 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
Image links broken; now fixed.
|
| Nov 2, 2012 at 16:39 | comment | added | Joseph O'Rourke | @Josh: Usually just called difference, or set subtraction, among algorithms called Boolean operations. | |
| Nov 2, 2012 at 15:15 | comment | added | Josh C. | Is there a name for an algorithm which subrtracts R from P? | |
| Aug 31, 2012 at 23:36 | comment | added | Joseph O'Rourke |
@JoshC: 1st question: See my added examples above re thwarting the greedy algorithm. 2nd question: When two adjacent corners are both constrained by edges, there is a continuum of maximal rectangles, from which you could select, say, the maximal area rectangle. 3rd question: You need a Boolean function that returns True iff rectangle $R \subset P$.
|
|
| Aug 31, 2012 at 11:55 | history | edited | Joseph O'Rourke | CC BY-SA 3.0 |
added 480 characters in body
|
| Aug 30, 2012 at 14:43 | vote | accept | Josh C. | ||
| Aug 30, 2012 at 14:43 | comment | added | Josh C. | Also, to ensure that my extension of E does not intersect P by leaving P, is proximity a good check? In other words, if E intersects P more than two times, I should check the proximity of those intersections to the original end points of E. | |
| Aug 30, 2012 at 14:39 | comment | added | Josh C. | Also, I am a bit confused how to describe a function to conclusively maximize my rectangle's value when a corner is constrained by an edge instead of two vertices. Would this be a good approach? Take E and extend it until it intersects with two other edges of P. Then, orthogonal to E at each end find two new points, where each point lies on an edge of P or the edges connecting those points to E or to each other is constrained by a vertex of P. | |
| Aug 30, 2012 at 14:31 | comment | added | Josh C. | At first I didn't understand how the greedy algorithm might be easy to thwart. Now, I'll verture to take a guess: By greedy, we are considering the rectangle which maximizes my value for the first edge. If this is true, I would need to change that to iterate over all edges choosing the rectangle which maximizes my value before subtraction. (By the way, is this problem called Largest Empty Rectangle?) | |
| Aug 30, 2012 at 0:28 | history | answered | Joseph O'Rourke | CC BY-SA 3.0 |