Topic Options

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Printer Friendly Page

This is an open group. Sign in and click the "Join Group" button to become a group member and start posting.

Highlighted
##

Need help with some pixel calculations

02-19-2018 10:14 PM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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?

DNatt, NI

14 REPLIES 14

Highlighted
##

Re: Need help with some pixel calculations

02-20-2018 08:05 AM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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?

Unofficial Forum Rules and Guidelines

Get going with G! - LabVIEW Wiki.

12 Part Blog on Automotive CAN bus. - Hooovahh - LabVIEW Overlord

Re: Need help with some pixel calculations

02-20-2018 09:23 AM - edited 02-20-2018 09:24 AM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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

Highlighted
##

Re: Need help with some pixel calculations

02-20-2018 10:55 AM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

@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.

DNatt, NI

Highlighted
##

Re: Need help with some pixel calculations

02-20-2018 10:56 AM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

@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.

DNatt, NI

Highlighted
##

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.

Re: Need help with some pixel calculations

02-20-2018 11:56 AM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

Highlighted
##

Re: Need help with some pixel calculations

02-20-2018 12:04 PM - edited 02-20-2018 12:09 PM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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...

Highlighted
##

Re: Need help with some pixel calculations

02-21-2018 09:52 AM - edited 02-21-2018 10:13 AM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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

- Start at the point and go right
- Stop at each left and right edge of each box
- Save the top most edge postion
- 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
- Repeat but go down using top bottom edges saving the smallest left position
~~When finished you will have 2 points so take the lowest value of each point to make the smallest allowable~~~~rectangle.~~- select the largest rectangle from the 2 boxes if there are 2.

Do you see any holes in this theory?

Highlighted
##

Re: Need help with some pixel calculations

02-21-2018 10:50 AM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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.

Get going with G! - LabVIEW Wiki.

12 Part Blog on Automotive CAN bus. - Hooovahh - LabVIEW Overlord

Highlighted
##

Re: Need help with some pixel calculations

02-21-2018 11:41 AM

Options

- Mark as New
- Subscribe to RSS Feed
- Permalink
- Email to a Friend
- Report to a Moderator

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".

Download All

Virus scan in progress. Please wait to download attachments.

- Subscribe to RSS Feed
- Mark Topic as New
- Mark Topic as Read
- Float this Topic for Current User
- Printer Friendly Page