Given 4 vertices representing a quadrilateral, divide it into N parts

Question

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:

Answer 1

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\$.

(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()