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












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










share|improve this question











$endgroup$

















    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










    share|improve this question











    $endgroup$















      2












      2








      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










      share|improve this question











      $endgroup$




      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







      python python-3.x






      share|improve this question















      share|improve this question













      share|improve this question




      share|improve this question








      edited Dec 15 '18 at 23:01









      Jamal

      30.3k11119227




      30.3k11119227










      asked Dec 15 '18 at 22:55









      pookiepookie

      13014




      13014






















          1 Answer
          1






          active

          oldest

          votes


















          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






          share|improve this answer











          $endgroup$













            Your Answer





            StackExchange.ifUsing("editor", function () {
            return StackExchange.using("mathjaxEditing", function () {
            StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
            StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
            });
            });
            }, "mathjax-editing");

            StackExchange.ifUsing("editor", function () {
            StackExchange.using("externalEditor", function () {
            StackExchange.using("snippets", function () {
            StackExchange.snippets.init();
            });
            });
            }, "code-snippets");

            StackExchange.ready(function() {
            var channelOptions = {
            tags: "".split(" "),
            id: "196"
            };
            initTagRenderer("".split(" "), "".split(" "), channelOptions);

            StackExchange.using("externalEditor", function() {
            // Have to fire editor after snippets, if snippets enabled
            if (StackExchange.settings.snippets.snippetsEnabled) {
            StackExchange.using("snippets", function() {
            createEditor();
            });
            }
            else {
            createEditor();
            }
            });

            function createEditor() {
            StackExchange.prepareEditor({
            heartbeatType: 'answer',
            autoActivateHeartbeat: false,
            convertImagesToLinks: false,
            noModals: true,
            showLowRepImageUploadWarning: true,
            reputationToPostImages: null,
            bindNavPrevention: true,
            postfix: "",
            imageUploader: {
            brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
            contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
            allowUrls: true
            },
            onDemand: true,
            discardSelector: ".discard-answer"
            ,immediatelyShowMarkdownHelp:true
            });


            }
            });














            draft saved

            draft discarded


















            StackExchange.ready(
            function () {
            StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209745%2fgiven-4-vertices-representing-a-quadrilateral-divide-it-into-n-parts%23new-answer', 'question_page');
            }
            );

            Post as a guest















            Required, but never shown

























            1 Answer
            1






            active

            oldest

            votes








            1 Answer
            1






            active

            oldest

            votes









            active

            oldest

            votes






            active

            oldest

            votes









            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






            share|improve this answer











            $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






              share|improve this answer











              $endgroup$
















                3












                3








                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






                share|improve this answer











                $endgroup$



                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







                share|improve this answer














                share|improve this answer



                share|improve this answer








                edited 22 mins ago

























                answered Dec 16 '18 at 12:44









                GraipherGraipher

                25k53687




                25k53687






























                    draft saved

                    draft discarded




















































                    Thanks for contributing an answer to Code Review Stack Exchange!


                    • Please be sure to answer the question. Provide details and share your research!

                    But avoid



                    • Asking for help, clarification, or responding to other answers.

                    • Making statements based on opinion; back them up with references or personal experience.


                    Use MathJax to format equations. MathJax reference.


                    To learn more, see our tips on writing great answers.




                    draft saved


                    draft discarded














                    StackExchange.ready(
                    function () {
                    StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f209745%2fgiven-4-vertices-representing-a-quadrilateral-divide-it-into-n-parts%23new-answer', 'question_page');
                    }
                    );

                    Post as a guest















                    Required, but never shown





















































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown

































                    Required, but never shown














                    Required, but never shown












                    Required, but never shown







                    Required, but never shown







                    Popular posts from this blog

                    How to make a Squid Proxy server?

                    Is this a new Fibonacci Identity?

                    19世紀