2
\$\begingroup\$

I am attempting to, given two dimensions (width and height) which represent a quadrilateral, partition that quad in to N parts where each part is as proportionally similar to the other as possible.

For example, imagine a sheet of paper. It consists of 4 points A, B, C, D. Now consider that the sheet of paper has the dimensions 800 x 800 and the points:

A: {0, 0}
B: {0, 800}
C: {800, 800}
D: {800, 0}

Plotting that will give you 4 points, or 3 lines with a line plot. Add an additional point E: {0, 0} to close the cell.

To my surprise, I've managed to do this programatically, for N number of cells.

How can I improve this code to make it more readable, pythonic, and as performant as possible?

from math import floor, ceil
import matplotlib.pyplot as plt


class QuadPartitioner:

    @staticmethod
    def get_factors(number):
        '''
        Takes a number and returns a list of factors
        :param number: The number for which to find the factors
        :return: a list of factors for the given number
        '''
        facts = []
        for i in range(1, number + 1):
            if number % i == 0:
                facts.append(i)
        return facts

    @staticmethod
    def get_partitions(N, quad_width, quad_height):

        '''
        Given a width and height, partition the area into N parts
        :param N: The number of partitions to generate
        :param quad_width: The width of the quadrilateral
        :param quad_height: The height of the quadrilateral
        :return: a list of a list of cells where each cell is defined as a list of 5 verticies
        '''

        # We reverse only because my brain feels more comfortable looking at a grid in this way
        factors = list(reversed(QuadPartitioner.get_factors(N)))

        # We need to find the middle of the factors so that we get cells
        # with as close to equal width and heights as possible

        factor_count = len(factors)

        # If even number of factors, we can partition both horizontally and vertically.
        # If not even, we can only partition on the X axis
        if factor_count % 2 == 0:
            split = int(factor_count/2)
            factors = factors[split-1:split+1]
        else:
            factors = []
            split = ceil(factor_count/2)
            factors.append(split)
            factors.append(split)

        # The width and height of an individual cell
        cell_width = quad_width / factors[0]
        cell_height = quad_height / factors[1]

        number_of_cells_in_a_row = factors[0]
        rows = factors[1]
        row_of_cells = []

        # We build just a single row of cells
        # then for each additional row, we just duplicate this row and offset the cells
        for n in range(0, number_of_cells_in_a_row):
                cell_points = []

                for i in range(0, 5):

                    cell_y = 0
                    cell_x = n * cell_width

                    if i == 2 or i == 3:
                        cell_x = n * cell_width + cell_width

                    if i == 1 or i == 2:
                        cell_y = cell_height

                    cell_points.append((cell_x, cell_y))

                row_of_cells.append(cell_points)

        rows_of_cells = [row_of_cells]

        # With that 1 row of cells constructed, we can simply duplicate it and offset it
        # by the height of a cell multiplied by the row number
        for index in range(1, rows):
            new_row_of_cells = [[ (point[0],point[1]+cell_height*index) for point in square] for square in row_of_cells]
            rows_of_cells.append(new_row_of_cells)

        return rows_of_cells


if __name__ == "__main__":

    QP = QuadPartitioner()
    partitions = QP.get_partitions(56, 1980,1080)

    for row_of_cells in partitions:
        for cell in row_of_cells:
            x, y = zip(*cell)
            plt.plot(x, y, marker='o')

    plt.show()

Output:

enter image description here

\$\endgroup\$
3
\$\begingroup\$

First, there is no need for this to be a class at all. Your class has only two static methods, so they might as well be stand-alone functions. In this regard Python is different from e.g. Java, where everything is supposed to be a class.


Your get_factors function can be sped-up significantly by recognizing that if k is a factor of n, then so is l = n / k. This also means you can stop looking for factors once you reach \$\sqrt{n}\$, because if it is a square number, this will be the largest factor not yet checked (and otherwise it is an upper bound). I also used a set instead of a list here so adding a factor multiple times does not matter (only relevant for square numbers, again).

from math import sqrt

def get_factors(n):
    '''
    Takes a number and returns a list of factors
    :param number: The number for which to find the factors
    :return: a list of factors for the given number
    '''
    factors = set()
    for i in range(1, int(sqrt(n)) + 1):
        if n % i == 0:
            factors.add(i)
            factors.add(n // i)
    return list(sorted(factors))  # sorted might be unnecessary

As said, this is significantly faster than your implementation, although this only starts to be relevant for about \$n > 10\$.

enter image description here

(Note the log scale on both axis.)


As for your main function:

First figure out how many rows and columns you will have. For this I would choose the factor that is closest to \$\sqrt{n}\$:

k = min(factors, key=lambda x: abs(sqrt(n) - x))
rows, cols = sorted([k, n //k])   # have more columns than rows

Then you can use numpy.arange to get the x- and y-coordinates of the grid:

x = np.arange(0, quad_width + 1, quad_width / cols)
y = np.arange(0, quad_height + 1, quad_height / rows)

From this you now just have to construct the cells:

def get_cells(x, y):
    for x1, x2 in zip(x, x[1:]):
        for y1, y2 in zip(y, y[1:]):
            yield [x1, x2, x2, x1, x1], [y1, y1, y2, y2, y1]

Putting all of this together:

import numpy as np

def get_partitions(n, width, height):
    factors = get_factors(n)
    k = min(factors, key=lambda x: abs(sqrt(n) - x))
    rows, cols = sorted([k, n //k])   # have more columns than rows

    x = np.arange(0, width + 1, width / cols)
    y = np.arange(0, height + 1, height / rows)

    yield from get_cells(x, y)

if __name__ == "__main__":
    for cell in get_partitions(56, 1980, 1080):
        plt.plot(*cell, marker='o')
    plt.show()

enter image description here

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.