StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>I've re written my original answer so it covers all cases and hopefully makes a bit more sense: (It's php not C++, but it was easier to write it out like this than to write out sudo-logic. Hopefully it will explain itself a bit better now.)</p> <p>A rectangle (or square in this case) can be represented by it's bottom left and top right coordinate. For this example, $Rectangle[0] is the bottom left coordinate, with $Rectangle[0]['x'] being the x value of the bottom left coordinate and $Rectangle[0]['y'] being the y value of the bottom left coordinate. $Rectangle[1] is the top right coordinate.</p> <p>This could be modified for something that will only deal with squares to hold only one vertex coordinate and the edge length.</p> <p>There are 4 possibilities for movement:<br> 1: No movement happened, the squares are in the same place. In this case all four corner points of the green rectangle will be inside the blue rectangle.<br> 2: Enough movement happened to cause there to be no overlap between the two squares. In this case none of the four corner points of the green rectangle will be inside the blue rectangle.<br> 3: Movement has happened in only one direction (x or y) and not far enough to remove all over lap. In this case 2 of the four corner points of the green rectangle will be inside the blue rectangle.<br> 4: Movement has happened in both x and y directions and not far enough to remove overlap entirely. In this case one of the four corner points of the green rectangle will be inside the blue rectangle.</p> <p>Each case can be handled slightly differently:<br> 1 - You don't need to iterate over any squares.<br> 2 - You need to iterate over all of the squares in the blue rectangle and all of the squares in the green rectangle.<br> 3 - You need to iterate over the squares defined by: </p> <pre><code>function getOnlyOverlapRectangle($FirstRectangle, $SecondRectangle) { $PointOne['x'] = $FirstRectangle[0]['x']; $PointOne['y'] = $FirstRectangle[0]['y']; $PointTwo['x'] = $FirstRectangle[0]['x']; $PointTwo['y'] = $FirstRectangle[1]['y']; $PointThree['x'] = $FirstRectangle[1]['x']; $PointThree['y'] = $FirstRectangle[1]['y']; $PointFour['x'] = $FirstRectangle[1]['x']; $PointFour['y'] = $FirstRectangle[]['y']; //left edge if(checkVertexInside($PointOne,$SecondRectangle) && checkVertexInside($PointTwo,$SecondRectangle)) { $overlapRectangle[0]['x'] = $SecondRectangle[1]['x']; } else { $overlapRectangle[0]['x'] = $FirstRectangle[0]['x']; } //bottom edge if(checkVertexInside($PointOne,$SecondRectangle) && checkVertexInside($PointFour,$SecondRectangle)) { $overlapRectangle[0]['y'] = $SecondRectangle[1]['y']; } else { $overlapRectangle[0]['y'] = $FirstRectangle[0]['y']; } //right edge if(checkVertexInside($PointThree,$SecondRectangle) && checkVertexInside($PointFour,$SecondRectangle)) { $overlapRectangle[1]['x'] = $SecondRectangle[0]['x']; } else { $overlapRectangle[1]['x'] = $FirstRectangle[1]['x']; } //top edge if(checkVertexInside($PointTwo,$SecondRectangle) && checkVertexInside($PointThree,$SecondRectangle)) { $overlapRectangle[1]['y'] = $SecondRectangle[0]['y']; } else { $overlapRectangle[1]['y'] = $FirstRectangle[1]['y']; } return $overlapRectangle; } </code></pre> <p>4 - You need to iterate over the squares defined by: </p> <pre><code>//Gets subset of $FirstRectangle that is outside of $SecondRectangle function getFirstOverlapRectangle($FirstRectangle, $SecondRectangle) { //left edge $Point['x'] = $FirstRectangle[0]['x']; $Point['y'] = $FirstRectangle[1]['y']; if(checkVertexInside($Point,$SecondRectangle)) { $overlapRectangle[0]['x'] = $SecondRectangle[1]['x']; } else { $overlapRectangle[0]['x'] = $FirstRectangle[0]['x']; } //bottom edge if($FirstRectangle[0]['y'] < $SecondRectangle[0]['y'] < $FirstRectangle[1]['y']) { $overlapRectangle[0]['y'] = $SecondRectangle[0]['y']; } else { $overlapRectangle[0]['y'] = $SecondRectangle[1]['y']; } //right edge $overlapRectangle[1]['x'] = min($FirstRectangle[1]['x'],$SecondRectangle[0]['x']); //top edge $overlapRectangle[1]['y'] = $FirstRectangle[1]['y']; return $overlapRectangle; } //Gets second subset of $FirstRectangle that is outside of $SecondRectangle function getSecondOverlapRectangle($FirstRectangle, $SecondRectangle) { //top edge if($FirstRectangle[0]['y'] < $SecondRectangle[0]['y'] < $FirstRectangle[1]['y']) { $overlapRectangle[1]['y'] = $SecondRectangle[0]['y']; } else { $overlapRectangle[1]['y'] = $SecondRectangle[1]['y']; } //bottom edge $overlapRectangle[0]['y'] = $FirstRectangle[0]['y']; //left edge $Point['x'] = $SecondRectangle[1]['x']; $Point['y'] = $SecondRectangle[1]['y']; if(checkVertexInside($Point,$FirstRectangle)) { $overlapRectangle[0]['x'] = $SecondRectangle[1]['x']; } else { $overlapRectangle[0]['x'] = $FirstRectangle[0]['x']; } //right edge $Point['x'] = $FirstRectangle[0]['x']; $Point['y'] = $FirstRectangle[1]['y']; if(checkVertexInside($Point,$SecondRectangle)) { $overlapRectangle[1]['x'] = $FirstRectangle[0]['x']; } else { $overlapRectangle[1]['x'] = $SecondRectangle[1]['x']; } return $overlapRectangle; } </code></pre> <p>So a possible solution would work like this:</p> <p>Work out how many corners of the green rectangle are inside the blue rectangle. Switch on that number:<br> 0: iterate over all green rectangle points and all blue rectangle points<br> 1: iterate over result of getFirstOverlapRectangle and getSecondOverlapRectangle<br> 2: iterate over result of getOnlyOverlapRectangle<br> 3: this shouldn't happen...<br> 4: don't iterate over any squares. </p> <p>Iterating would have to work something like this:</p> <pre><code>for($CurrentXCoord = $OldSquaresOne[0]['x'] + 0.5; $CurrentXCoord < $OldSquaresOne[1]['x']; $CurrentXCoord ++) { for($CurrentYCoord = $OldSquaresOne[0]['y'] + 0.5; $CurrentYCoord < $OldSquaresOne[1]['y']; $CurrentYCoord ++) { //do stuff. } } </code></pre> <p>The +0.5 ensures that you don't go over boundary points twice so you reference the squares inside the blue/green squares by their center coordinate instead of corner coordinate.</p> <p>The checkVertexInside function would be something along the lines of:</p> <pre><code>function checkVertexInside($Point, $Rectangle) { if ( $Point['x'] <= $Rectangle[1]['x'] && $Point['x'] >= $Rectangle[0]['x'] && $Point['y'] <= $Rectangle[1]['y'] && $Point['y'] >= $Rectangle[0]['y'] ) { return true; } return false; } function getRectanglePoint($topFlag,$rightFlag,$Rectangle) { $Point['x'] = $Rectangle[$rightFlag]['x']; $Point['y'] = $Rectangle[$topFlag]['y']; return $Point; } </code></pre>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload