Topic Re: Need help with some pixel calculations in Quick Drop Enthusiasts
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757258#M946
<P>Actually this is a very interesting problem: <A href="https://en.wikipedia.org/wiki/Largest_empty_rectangle" target="_blank">https://en.wikipedia.org/wiki/Largest_empty_rectangle</A></P>
<P>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 <span class="lia-unicode-emoji" title=":slightly_smiling_face:">ðŸ™‚</span></P>
<P> </P>
<P>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...</P>Tue, 20 Feb 2018 18:09:44 GMTBlokk2018-02-20T18:09:44ZNeed help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3756822#M940
<P>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?</P>Tue, 20 Feb 2018 04:14:16 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3756822#M940Darren2018-02-20T04:14:16ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757060#M941
<P>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?</P>Tue, 20 Feb 2018 14:05:38 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757060#M941Hooovahh2018-02-20T14:05:38ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757129#M942
<P>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. </P>
<P><span class="lia-inline-image-display-wrapper lia-image-align-inline" image-alt="rectangles.png" style="width: 537px;"><img src="https://ni.i.lithium.com/t5/image/serverpage/image-id/223206i83C7478AD21C289A/image-size/large?v=1.0&px=999" title="rectangles.png" alt="rectangles.png" /></span></P>
<P> </P>
<P> </P>
<P>Is this what you're thinking about or am I interpreting incorrectly?</P>
<P> </P>
<P>--David_L, CLA</P>Tue, 20 Feb 2018 15:24:29 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757129#M942David_L2018-02-20T15:24:29ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757205#M943
<BLOCKQUOTE><HR /><LI-USER uid="74523"></LI-USER><LI-USER uid="74523"></LI-USER> wrote:<BR />
<P>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?</P>
<HR /></BLOCKQUOTE>
<P>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.</P>Tue, 20 Feb 2018 16:55:54 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757205#M943Darren2018-02-20T16:55:54ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757206#M944
<BLOCKQUOTE><HR /><LI-USER uid="109654"></LI-USER>David_L wrote:
<P> </P>
<P>Is this what you're thinking about or am I interpreting incorrectly?</P>
<HR /></BLOCKQUOTE>
<P>Yup, that's the idea. But when I sat down to write the code, I just couldn't get a toe hold.</P>Tue, 20 Feb 2018 16:56:58 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757206#M944Darren2018-02-20T16:56:58ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757251#M945
<P>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.</P>Tue, 20 Feb 2018 17:56:09 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757251#M945David_L2018-02-20T17:56:09ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757258#M946
<P>Actually this is a very interesting problem: <A href="https://en.wikipedia.org/wiki/Largest_empty_rectangle" target="_blank">https://en.wikipedia.org/wiki/Largest_empty_rectangle</A></P>
<P>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 <span class="lia-unicode-emoji" title=":slightly_smiling_face:">ðŸ™‚</span></P>
<P> </P>
<P>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...</P>Tue, 20 Feb 2018 18:09:44 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757258#M946Blokk2018-02-20T18:09:44ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757678#M947
<P>Here is my initial thoughts. assuming left to right and top to bottom are positive.</P>
<P> </P>
<OL>
<LI>Start at the point and go right</LI>
<LI>Stop at each left and right edge of each box</LI>
<LI>Save the top most edge postion</LI>
<LI>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</LI>
<LI>Repeat but go down using top bottom edges saving the smallest left position</LI>
<LI><STRIKE>When finished you will have 2 points so take the lowest value of each point to make the smallest allowable</STRIKE> <STRIKE>rectangle.</STRIKE></LI>
<LI>select the largest rectangle from the 2 boxes if there are 2.</LI>
</OL>
<P>Do you see any holes in this theory?</P>Wed, 21 Feb 2018 16:13:56 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757678#M947MarkBalla2018-02-21T16:13:56ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757729#M948
<P>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.</P>Wed, 21 Feb 2018 16:50:30 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757729#M948Hooovahh2018-02-21T16:50:30ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757756#M949
<P>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...</P>
<P> </P>
<P>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.</P>
<P>The relevant subVI is the "maximum_empty_rectangle.vi".</P>Wed, 21 Feb 2018 17:41:11 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757756#M949Blokk2018-02-21T17:41:11ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757914#M950
<P>Thanks for the attempts, guys. I think Hooovahh's is the closest to what I need, I worked with it for a while but couldn't figure out what the issue was with it not working.</P>
<P> </P>
<P>Oh, and I've decided that my cool idea would be better implemented as a right-click plugin, to make the user experience better. But we can continue the conversation here if anybody has a breakthrough.</P>Wed, 21 Feb 2018 21:57:44 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757914#M950Darren2018-02-21T21:57:44ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757958#M951
<P>I think I got it working...I've posted my attempt below (based on Hooovahh's attempt). Let me know if y'all see any problems with it.</P>
<P> </P>
<P>Saved in LabVIEW 2015.</P>Wed, 21 Feb 2018 23:34:52 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3757958#M951Darren2018-02-21T23:34:52ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3758043#M952
<P>Much more difficult than I thought originally,</P>
<P>Here is my version using FP controls to easily test </P>Thu, 22 Feb 2018 06:43:01 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3758043#M952MarkBalla2018-02-22T06:43:01ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3762614#M957
<P>If someone is interested, I implemented a naive search algorithm both in LV and C, based on the <A href="https://www.sciencedirect.com/science/article/pii/0166218X84901240." target="_blank">paper from 1984</A>. Be aware! I am very good in creating Rube Goldbergs! <span class="lia-unicode-emoji" title=":grinning_face_with_smiling_eyes:">ðŸ˜„</span></P>
<P><A href="https://forums.ni.com/t5/Community-Documents/Maximum-Empty-Rectangle-a-LabVIEW-and-C-implementation/ta-p/3762612" target="_blank">https://forums.ni.com/t5/Community-Documents/Maximum-Empty-Rectangle-a-LabVIEW-and-C-implementation/ta-p/3762612</A></P>Sat, 03 Mar 2018 18:25:52 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3762614#M957Blokk2018-03-03T18:25:52ZRe: Need help with some pixel calculations
https://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3937848#M1070
<P>Has anyone been able to extend this to line rather than points?<BR /><BR /><A href="https://forums.ni.com/t5/Community-Documents/Maximum-Empty-Rectangle-a-LabVIEW-and-C-implementation/ta-p/3762612?profile.language=en" target="_blank" rel="noopener">https://forums.ni.com/t5/Community-Documents/Maximum-Empty-Rectangle-a-LabVIEW-and-C-implementation/ta-p/3762612?profile.language=en</A></P>Fri, 14 Jun 2019 20:05:38 GMThttps://forums.ni.com/t5/Quick-Drop-Enthusiasts/Need-help-with-some-pixel-calculations/gpm-p/3937848#M1070acaracciolo2019-06-14T20:05:38Z