Need help with some pixel calculations

[Darren]

I've got a cool idea for a Quick Drop keyboard shortcut, but I'm having trouble wrapping my head around one key part of it. Can somebody write me a subVI that, given a position value and an array of rects, can calculate the largest rect that can be created with the given position value (as the top/left of the rect) that doesn't overlap any of the rects in the given array?

[Hooovahh]

I think I could do this, but I don't fully understand what you are asking for.  So if you have an XY position, you want to draw the largest rect you can, that doesn't overlap the rects that are given.  Does that mean moving to the left, right, top and bottom, until hitting a rect border, and figuring out which generates the largest area?  Meaning the XY position given might not be at the center of the rect drawn.  It might even be at the edge?  What about cases when the rect to be drawn can extend forever in one direction?

[David_L]

Just spit-balling ideas here (i'm not an algorithm designer, so there are probably better ways).  What if you did something like below where you start at your initial position (X) and go down until you hit an object, then go right until you hit an object then assume your first rectangle (Green box).  Then do the same starting right then down to assume second rectangle (orange box).  Calculate area to get the largest box.  There may be other possible rectangles if you take different paths but this will at least give you a start.  

Is this what you're thinking about or am I interpreting incorrectly?

--David_L, CLA

[Darren]

---

@Hooovahh@Hooovahh wrote:

I think I could do this, but I don't fully understand what you are asking for.  So if you have an XY position, you want to draw the largest rect you can, that doesn't overlap the rects that are given.  Does that mean moving to the left, right, top and bottom, until hitting a rect border, and figuring out which generates the largest area?  Meaning the XY position given might not be at the center of the rect drawn.  It might even be at the edge?  What about cases when the rect to be drawn can extend forever in one direction?

---

The given XY position is always the top-left of the desired rect. I'm hoping that makes it easier, as you only need to go right and down from that spot. Also, if the rect can go forever, we'll just set a max size.

[Darren]

---

@David_LDavid_L wrote:

Is this what you're thinking about or am I interpreting incorrectly?

---

Yup, that's the idea. But when I sat down to write the code, I just couldn't get a toe hold.

[David_L]

Ya it's harder than I thought.  I spent an hour this morning trying to figure it out but then had to get back to work.  My approach was using the "Computational Geometry" palette to find intersections in polygons and basically creating a rectangle of size 1x1, check if intersection if not, increase the rectangle size in one direction and repeat.  The problem is that the geometry palette uses one type of data, the drawing palette uses a different type, a standard VI Server rectangle is a third type and most of my time was spent just manipulating data.  Maybe I'll try again when I need a mental break from real work.

[Blokk]

Actually this is a very interesting problem: https://en.wikipedia.org/wiki/Largest_empty_rectangle

It is a pity I was never good in such optimization math "tricks", but I am sure some people will turn up and give some cool solution 🙂

edit: I have found some interesting articles, but I do not have access to scientific papers from home. I try to download some promising articles tomorrow, and if the published algorithm is not over my skills, I will try to implement it in LabVIEW...

[MarkBalla]

Here is my initial thoughts. assuming left to right and top to bottom are positive.

1. Start at the point and go right
2. Stop at each left and right edge of each box
3. Save the top most edge postion
4. If the top most edge ever goes less than or equal to point's top position then stop and keep the right and top potions
5. Repeat but go down using top bottom edges saving the smallest left position
6. When finished you will have 2 points so take the lowest value of each point to make the smallest allowable rectangle.
7. select the largest rectangle from the 2 boxes if there are 2.

Do you see any holes in this theory?

[Hooovahh]

I'm not above showing half finished, terribly written, broken code.  Here is what I came up with yesterday and assumed I'd get time to finish it today, that doesn't seem to be the case.  It partially works but as you can see from my example code the Red box is too large, and actually crosses over a defined rect due to the second half of the rules not being completed right.

[Blokk]

I also could not finish it today, and I got a bit confused during the implementation of a brute force approach, based on a paper from the 80's. I attach the paper, and my project which I just started, someone might get faster than me. I think one thing which needs to be clarified, is the position of the origo. It might be, that in the paper, I think, the origo is bottom left instead of the native LV top-left position coordinate system...

In the paper look for the section 3: "The algorithms". I started to implement first this "brute force" approach, which always take Ordo(n^2) steps as I understood.

The relevant subVI is the  "maximum_empty_rectangle.vi".