Title: Map points so they fit within a target area in Python

[This tree is resized to fit in the window]

My previous post Recursively draw binary trees in Python shows how to draw a binary tree. It's easy enough to adjust that program's drawing parameter so the tree doesn't fit completely on the window, as shown in the picture on the left above. You can probably use some math, possibly involving limits and other scary techniques, to figure out exactly how big the tree is, at least for special cases like when the angle delta is 45°. Performing that calculation in general, however, sounds hard. For some other programs such as those that draw certain kinds of fractals, that calculation may be impossible.

This example shows how you can map the points in a drawing like a binary tree so they fit nicely into a target area. This is a two-stage process: finding the necessary transformations and then applying those transformations.

Defining the Transformations

First we need to find three transformations that map the points onto a target rectangle. Those transformations will:

Translate (move) the points so they are centered at the origin
Scale the points so they occupy the largest area possible that still has width and height no larger than those of the target rectangle
Translate the points again so they lie within the target rectangle

The following pictures show the process as the points are translated, scaled, and translated to their final positions. [A blob of points]

[Points translated onto the target rectangle]

Finding Transformations

Finding the transformations isn't too hard. The following get_transformations method takes as parameters the rectangle containing the points and the target rectangle where we want to draw the points. It returns the translation and scaling values needed to transform the points.

def get_transformations(point_rect, target_rect): '''Return transformations to map the coordinate area to the rectangle.''' # Translate to center the points at the origin. dx1 = -(point_rect[0] + point_rect[2]) / 2 dy1 = -(point_rect[1] + point_rect[3]) / 2 # Scale. x_scale = (target_rect[2] - target_rect[0]) / (point_rect[2] - point_rect[0]) y_scale = (target_rect[3] - target_rect[1]) / (point_rect[3] - point_rect[1]) scale = min(x_scale, y_scale) # Translate to move the points to the center of the target rectangle. dx2 = (target_rect[0] + target_rect[2]) / 2 dy2 = (target_rect[1] + target_rect[3]) / 2 # Return the transformation information. return dx1, dy1, scale, dx2, dy2

The two input rectangles have the form (xmin, ymin, xmax, ymax).

The center of a rectangle is at the average of the coordinates of its extremes. For example, the X coordinate of the center of the points rectangle is the average of its minimum and maximum X coordinates (point_rect[0] + point_rect[2]) / 2. (And similarly for the Y coordinate.)

The function sets values dx1 and dy1 to the negative of those values. Later, when we add dx1 and dy1 to the points' coordinates, the points are moved so they are centered at the origin. In particular, if there's a point in the center of the points rectangle, that point's new coordinates will be (0, 0).

Next, the function figures out how much to scale the points to make them fit the target rectangle. The x_scale value is the width of the target rectangle divided by the width of the points rectangle. Using that scale factor would make the points rectangle the same width as the target rectangle. The code calculates the y_scale value similarly and then sets scale equal to the smaller of the two scale factors so the points rectangle will be made as large as possible while still fitting within the target rectangle.

The last transformation the function needs to make maps the points from their current location centered at the origin to the center of the target rectangle. The code sets dx2 and dy2 equal to the center of that rectangle so adding those values to the points moves them into the target rectangle. For example, if a point was initially translated to the origin, it is now moved to the center of the target rectangle.

Having calculated all of the transformation values, the function returns them.

Note that this is not the most flexible system for representing transformations. Homogeneous transformations allow you to represent complex transformation, scaling, rotation, skewing, projection, and more with a single matrix. The values used here are good enough for this kind of transformation and they're easier to explain, so that's what we're using for this example.

Finding Point Bounds

The get_transformations function begs the question, "How do you find the points' bounding rectangle?" This example draws a list of line segments, each of which is a list containing two points. Rather than assuming this exact arrangement, the following get_list_of_lists_bounds function takes as a parameter a general list of lists of points. That way you can use it to bound lists of segments, triangles, or any other kind of polygon.

def get_list_of_lists_bounds(list_of_lists): '''Return the coordinate bounds for this list of lists.''' xs = [point[0] for point_list in list_of_lists for point in point_list] ys = [point[1] for point_list in list_of_lists for point in point_list] xmin = min(xs) xmax = max(xs) ymin = min(ys) ymax = max(ys) return (xmin, ymin, xmax, ymax)

This code uses a list comprehension so convert the list of lists into a simple list of X coordinate values. It then does the same to make a list of Y coordinates.

The function uses min and max to find the largest and smallest X and Y coordinates and returns them in a list that defines the points' bounding rectangle.

Applying Transformations

Having found the transformations needed to map the points to a target rectangle, we need a way to actually transform the points. The following function does that for a list of lists of points.

def transform_list_of_lists(list_of_lists, target_rect): '''Transform the list of lists of points to fit the rectangle.''' # The list_of_lists parameter is a list of lists of coordinate pairs. # For example, it might be a list of segments, squares, or larger polygons. # Get the points' coordinate bounds. point_rect = get_list_of_lists_bounds(list_of_lists) # Get the transformations. dx1, dy1, scale, dx2, dy2 = get_transformations(point_rect, target_rect) # Apply the transformations to the points. # Apply the transformations to the points. # Using a list comprehension: new_list_of_lists = [[ ( (point[0] + dx1) * scale + dx2, (point[1] + dy1) * scale + dy2, ) for point in point_list] for point_list in list_of_lists] # Using loops: # new_list_of_lists = [] # for point_list in list_of_lists: # new_point_list = [] # new_list_of_lists.append(new_point_list) # for point in point_list: # x = (point[0] + dx1) * scale + dx2 # y = (point[1] + dy1) * scale + dy2 # new_point_list.append((x, y)) return new_list_of_lists

This function calls get_list_of_lists_bounds to get the points' bounding rectangle. It then calls get_transformations to get the transformation parameters needed to map those bounds onto the target rectangle.

The code then uses a list comprehension to loop apply the transformations to each point's X and Y coordinates. The comprehension packages the results into new points contained in a new list of lists.

If you don't like the comprehension (I admit it's kind of confusing), you can do the same thing with two nested loops.

After it transforms the points, the function returns the new list.

Drawing Trees

The following code shows how the program uses the transformation functions to draw a binary tree that fits nicely on the window. The pieces that are different from the preceding post are highlighted in blue

def draw(self): '''Draw the tree.''' # Clear the canvas. self.canvas.delete(tk.ALL) # Get the tree's parameters. depth = int(self.depth_entry.get()) delta = math.radians(float(self.delta_entry.get())) length = 1 scale = float(self.scale_entry.get()) x = 0 y = 0 # Generate the tree segments. segments = get_binary_tree(depth, delta, length, scale, x, y) # Get the drawing area coordinates and set the target rectangle. tk.Tk.update(self.canvas) canvas_wid = self.canvas.winfo_width() canvas_hgt = self.canvas.winfo_height() margin = 10 rect = (margin, margin, canvas_wid - margin, canvas_hgt - margin) # Transform the points so they fit the target area. segments = transform_list_of_lists(segments, rect) # Draw the segments. for segment in segments: self.canvas.create_line(segment[0], segment[1], fill='blue')

This code first gets the drawing parameters entered on the window by the user. This time we don't need the length parameter because the program will resize the tree to fit the window. You can set length to anything (other than zero) and the resizing will make the tree fit.

We also don't need to set the X and Y coordinates of the tree's root node to special values to position the tree. The transformations will move the tree so it is centered no matter where we initially generate its points, so we may as well start the tree at (0, 0).

After defining the drawing parameters, the function calls get_binary_tree to get the tree's segments. It then gets the drawing canvas's dimensions and uses them to pick a target rectangle. (Feel free to modify the code to draw that rectangle if you want to see how nicely the tree fits.) It calls transform_list_of_lists to make the tree fit the target rectangle and then loops through the segments to draw them.

You can see that the changes to this part of the program are relatively small.

Conclusion

Transforming points in this way is pretty easy so you can use this technique for any program where you can't easily draw the points exactly where you want to display them. Just generate the points in whatever position is convenient and then use transform_list_of_lists to move them where you want to draw.

If your program stores points in some other data structure like a list of points, list of list of lists, or whatever, you'll need to modify the transformation functions accordingly, but hopefully the idea is clear.

Download the example to experiment with it and to see additional details.