The Shape of T-SQL

Editor's Note: Send your experts-only T-SQL tips to Itzik Ben-Gan at blackbelt@sqlmag.com. If we use your tip in the magazine, you'll receive $100 and an exclusive T-SQL Black Belt shirt.

Several industries—including cartography, or mapmaking—collect and manipulate geographical data to produce maps or for other purposes. People in these fields sometimes run across interesting problems that require the exercise of geometry and SQL against data that's stored in a database. For example, suppose you have a table containing the coordinates of points of interest such as motels. Given a list of certain locations—for example, highway exits—you might need to find the coordinates of the smallest rectangle that encloses all the input locations. You might then feed these coordinates to a mapping application that uses them to generate the smallest map that includes all the locations. This problem is easy to solve in T-SQL because you're not limited by a list of possible rectangles—rather, you use the locations' coordinates to calculate the rectangle's coordinates. You simply use the MIN() and MAX() functions. However, I recently encountered in the Microsoft SQL Server Programming public newsgroup (news://msnews.microsoft.com/microsoft.public.sqlserver.programming) a problem that has similar requirements but is much more complex than the problem I just mentioned. Let's look at it, then examine one solution I came up with.

The scenario involves center and target locations in a two-dimensional plane. The person who posted the problem didn't specify what those center and target locations were, so let's use the motel example. Suppose that the motel-chain company stores in its database the locations of its motels and highway exits leading to each motel. Center (motel) locations information is stored in a table called Centers and includes the center ID and its x, y coordinates. Target (exit) locations information is stored in a table called Targets and includes an arbitrary location ID, the center ID to which the target location belongs, and the x, y coordinates of the target location. The company's mapping application can generate a map from each combination of four target locations that are positioned in the four corners of a rectangle. You can run the script that Listing 1 shows to create the Centers and Targets tables and populate them with sample data.

Here's the problem you need to solve: For each center, find the coordinates of a rectangle with the smallest area such that the rectangle is formed by four target locations at its corners. In the motels example, this means that for each motel, you need to find the smallest rectangle formed by four highway exits enclosing the motel. The mapping application will use the coordinates of the four exits nearest each motel to generate maps for the motels' clients. You need to generate the smallest possible map that includes the center location, using only target locations that form a rectangle. For simplicity's sake, you can assume that at least one such enclosing rectangle exists for each center and that if more than one "smallest enclosing rectangle" exists, you can return them all. In reality, you'd need to add a factor that takes into account the fact that you probably can't form an exact rectangle from highway exits.

To get a better understanding of the problem, look at Figure 1. I've marked the target locations with an x and the center locations from the sample data as circles with a cross. The figure also contains the smallest enclosing rectangles that you're looking for. The elements that belong to Center 1 appear in red, and the elements that belong to Center 2 appear in gold.

Creating a single query that solves the problem is a difficult task. Such a query would be highly complex and hard to understand and maintain. A better approach is to break the problem into steps and use views to encapsulate the intermediate queries. You could express the first step this way: "For each center, find the coordinates of all rectangles that can be formed from the target locations that belong to the center." In our example, this means "for each motel, find all rectangles that can be formed from the highway exits that belong to it." Note that a valid rectangle must contain four target locations at the four corners. However, returning the coordinates of only the top-left and bottom-right corners in the output is sufficient.

Running the script in Listing 2 creates the VRectangles view, which returns the results of the first step—finding all rectangles that belong to a center—by joining the Targets table to itself. We're interested in the top-left corners from the Targets instance called TL and in the bottom-right corners from the instance called BR. To match each top-left corner in TL with all possible bottom-right corners from BR, the code in Listing 2 uses the following JOIN condition:

TL.centerid = BR.centerid AND TL.X < BR.X AND TL.Y > BR.Y.