Jeffkillian.com initially started as a Geocities website when I was in 6th grade. Over the years, it has slowly evolved into a place where I can practice and become familiar
with web development as it progresses. I started out coding with Microsoft Frontpage, then moved to Dreamweaver. Initially, there was very little coding, and it was all
WYSIWYG. However, as I learned more, I could make it more interactive.

I incorporate drawings and blog posts to keep those that are interested updated. Through the evolution of the website, I was forced to learn HTML, PHP, CSS, XML, jQuery, javascript, and the handling of MySQL Databases. I've put online some code samples.

I incorporate drawings and blog posts to keep those that are interested updated. Through the evolution of the website, I was forced to learn HTML, PHP, CSS, XML, jQuery, javascript, and the handling of MySQL Databases. I've put online some code samples.

Looking for even

Overlapping Squares

January 2nd, 2012

A friend brought up the question of "How do you determine if two randomly generated squares (or rectangles) are overlapping?" I had to do this in a java class before, but it was a while ago, so I thought I'd revisit it. I'm sure there are some answers online, but I wanted to take a stab at it before I looked at others' solutions.

Previously (in my java class), we had been given the two diagonal corners of the shape, and had to check to see if it overlapped with any other shape (there were lots of squares on our plane). In our solution, there were three possible options. For two shapes to be overlapping, one of them must either contain one, two, or all four corners of the other. Therefore, we had a function with an equation satisfying only those points within square 1, and we tested each corner of square 2 to see if any corner coordinates satisfied. If only one corner did, we knew only one corner was in. If two corners returner, we knew it was partially in. Four meant the entire square was contained within the other. Lastly, if none of this returned true, you pick a corner of square 1, and test whether it is in square 2. If this were true, that would mean square 2 were entirely within square 1.

However, when my friend posed the problem, she did not have the corner coordinates. Rather, the program she was using would generate squares based on a center coordinate. Her eventual goal was to create a randomly generated city block with buildings, and she wanted to ensure no two buildings overlapped. As long as two bases never overlapped, no two buildings would either. For simplicities sake, we assumed that all buildings were square.

If all buildings were square and we only had a center point (and length to the edge from center, aka half the width/height, referred to as "w"), the simplest idea is to draw a circle with radius sqrt(2w*w). This would result in a square perfectly inscribed within a circle, as seen in the image below:

Every time you create a square, you could generate this circle, and check for two things:

1) the circle surrounding your newly created square doesn't overlap edges with any others. You would check this by setting the equations for the two circles equal, and verifying no solutions.

2). The center of your new circle is not contained within any other circle. You would check this by seeing if the center of this new circle satisfies the comparing circle's equation, but using an inequality (less than or equal to instead of equal to) in order to get all circles contained within.

This is not the most efficient way, however, for there is extra space that isn't technically in a square, but we are restricting. You would be less likely to find two closely adjacent squares because the area in the circle that is not in the square would be prohibiting this. Another option proposed was to calculate the points of the corners, and then use the method first described. Because she only needed to generate a city block or so, we weren't too concerned with the time it took to generate. Because she isn't at the project where this needs to be written, our conversation moved onward. However, I'm sure I'll approach this later, as it's a pretty interesting puzzle. I'd like to focus more on optimization of a way in order to minimize resources used.