Turn on suggestions

Auto-suggest helps you quickly narrow down your search results by suggesting possible matches as you type.

Showing results for

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

Darren

Proven Zealot

02-19-2018 10:14 PM

Options

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report to a Moderator

Hooovahh

Proven Zealot

02-20-2018 08:05 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- 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.

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

David_L

Active Participant

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- 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

02-20-2018 10:55 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- 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.

02-20-2018 10:56 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- 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.

David_L

Active Participant

02-20-2018 11:56 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- Report to a Moderator

Blokk

Trusted Enthusiast

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- 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...

MarkBalla

Active Participant

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

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- 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?

Hooovahh

Proven Zealot

02-21-2018 10:50 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- 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.

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

Blokk

Trusted Enthusiast

02-21-2018 11:41 AM

- Mark as New
- Bookmark
- Subscribe
- Mute
- Subscribe to RSS Feed
- Permalink
- 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".