Jump to content

  • Log In with Google      Sign In   
  • Create Account


Finding Empty Rectangle


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
2 replies to this topic

#1 pyroExtreme   Members   -  Reputation: 105

Like
0Likes
Like

Posted 01 May 2014 - 06:01 AM

Hi 

 

I'm working on a problem and wondering if anyone can point me in good direction or at some existing source code. 

 

I have a rectangle that contains some points and I'm trying to find the largest empty rectangular area inside it that doesn't contain any of the points with its side parallel to the original rectangle (See below)

 

emptyRect.png

 

Can anyone help, I can't use a brute force approach of scanning the largest rectangle as its going to be 25000x25000 and contain up to 3000 random points.

 

I was thinking some sort of 2D space partitioning, but not really don't anything with that before.

 

I'm not worried about the memory needed for any suggested solution, I just need to be able to find the largest area as fast as possible.

 

Does anyone have any recommendations of where to start.

 

Thanks  



Sponsor:

#2 Álvaro   Crossbones+   -  Reputation: 12365

Like
1Likes
Like

Posted 01 May 2014 - 07:17 AM

I entered `largest empty rectangle algorithm' in Google. The first search result is a 1986 paper that addresses your problem exactly. The second link is a Wikipedia page that gives a lot of information about your exact problem and several variations.

 

How hard did you try to find information on your own?

 

EDIT: Searching a bit more, I found that there is a fast implementation in CGAL: http://doc.cgal.org/latest/Inscribed_areas/classCGAL_1_1Largest__empty__iso__rectangle__2.html


Edited by Álvaro, 01 May 2014 - 07:33 AM.


#3 pyroExtreme   Members   -  Reputation: 105

Like
0Likes
Like

Posted 01 May 2014 - 11:51 AM

Thanks Alvaro, sorry I should have mentioned I did find the 1986 paper myself, read it and understood it up to a certain point then just got lost.

 

Thanks for the CGAL link though, I didn't come across that one in my search. 






Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS