Python: implement a script in a function. Some sug

问题:

first of all, i am quite new in Python (an programming area) but i wish to learn and convert a function developed by jwpat7. Given a set of points derived from a convex hull

hull= [(560023.44957588764,6362057.3904932579), 
      (560023.44957588764,6362060.3904932579), 
      (560024.44957588764,6362063.3904932579), 
      (560026.94957588764,6362068.3904932579), 
      (560028.44957588764,6362069.8904932579), 
      (560034.94957588764,6362071.8904932579), 
      (560036.44957588764,6362071.8904932579), 
      (560037.44957588764,6362070.3904932579), 
      (560037.44957588764,6362064.8904932579), 
      (560036.44957588764,6362063.3904932579), 
      (560034.94957588764,6362061.3904932579), 
      (560026.94957588764,6362057.8904932579), 
      (560025.44957588764,6362057.3904932579), 
      (560023.44957588764,6362057.3904932579)]

this script return a print of all possible area following this post problem. The code develop by jwpat7 is:

import math

def mostfar(j, n, s, c, mx, my): # advance j to extreme point
    xn, yn = hull[j][0], hull[j][1]
    rx, ry = xn*c - yn*s, xn*s + yn*c
    best = mx*rx + my*ry
    while True:
        x, y = rx, ry
        xn, yn = hull[(j+1)%n][0], hull[(j+1)%n][1]
        rx, ry = xn*c - yn*s, xn*s + yn*c
        if mx*rx + my*ry >= best:
            j = (j+1)%n
            best = mx*rx + my*ry
        else:
            return (x, y, j)

n = len(hull)
iL = iR = iP = 1                # indexes left, right, opposite
pi = 4*math.atan(1)
for i in range(n-1):
    dx = hull[i+1][0] - hull[i][0]
    dy = hull[i+1][1] - hull[i][1]
    theta = pi-math.atan2(dy, dx)
    s, c = math.sin(theta), math.cos(theta)
    yC = hull[i][0]*s + hull[i][1]*c    
    xP, yP, iP = mostfar(iP, n, s, c, 0, 1)
    if i==0: iR = iP
    xR, yR, iR = mostfar(iR, n, s, c,  1, 0)
    xL, yL, iL = mostfar(iL, n, s, c, -1, 0)
    area = (yP-yC)*(xR-xL) 
    print '    {:2d} {:2d} {:2d} {:2d} {:9.3f}'.format(i, iL, iP, iR, area)

the result is:

i iL iP iR    Area
 0  6  8  0   203.000
 1  6  8  0   211.875
 2  6  8  0   205.800
 3  6 10  0   206.250
 4  7 12  0   190.362
 5  8  0  1   203.000
 6 10  0  4   201.385
 7  0  1  6   203.000
 8  0  3  6   205.827
 9  0  3  6   205.640
10  0  4  7   187.451
11  0  4  7   189.750
12  1  6  8   203.000

i wish to create a single function with the return of Length, Width, and Area of the smallest rectangle. Ex:

Length, Width, Area = get_minimum_area_rectangle(hull)
print Length, Width, Area
18.036, 10.392, 187.451

my questions are:

1. do i need to create a single function or two function. ex: def mostfar and get_minimum_area_rectangle
2. hull is a list of value. Is it the best format?
   3. followint the one function approach, i have a problem to integrate mostfar inside

Thanks in advance

1) solution: one function following the first solution suggest by Scott Hunter, i have a problem to integrate mostfar() inside get_minimum_area_rectangle(). Any suggestion or help are really appreciate because i can learn.

#!/usr/bin/python
import math

def get_minimum_area_rectangle(hull):
    # get pi greek
    pi = 4*math.atan(1)
    # number of points
    n = len(hull)
     # indexes left, right, opposite
    iL = iR = iP = 1
    # work clockwise direction
    for i in range(n-1):
        # distance on x axis
        dx = hull[i+1][0] - hull[i][0]
        # distance on y axis
        dy = hull[i+1][1] - hull[i][1]
        # get orientation angle of the edge
        theta = pi-math.atan2(dy, dx)
        s, c = math.sin(theta), math.cos(theta)
        yC = hull[i][0]*s + hull[i][1]*c

from here following the above example of jwpat7 i need to use mostfar(). I have a problem to understand how integrate (sorry for the not right term) mostfar in this point

回答1:

Here's an example of how to make it a functor object out of your code and use it -- along with a few changes to some other things I felt were worthwhile. A functor is an entity that serves the role of a function but can be operated upon like an object.

In Python there's less of a distinction between the two since functions are already singleton objects, but sometimes it's useful to create an specialized class for one. In this case it allows the helper function to be made into a private class method instead of it being global or nested which you seem to object to doing.

from math import atan2, cos, pi, sin

class GetMinimumAreaRectangle(object):
    """ functor to find length, width, and area of the smallest rectangular
        area of the given convex hull """
    def __call__(self, hull):
        self.hull = hull
        mostfar = self._mostfar  # local reference
        n = len(hull)
        min_area = 10**100  # huge value
        iL = iR = iP = 1  # indexes left, right, opposite
#        print '    {:>2s} {:>2s} {:>2s} {:>2s} {:>9s}'.format(
#                   'i', 'iL', 'iP', 'iR', 'area')
        for i in xrange(n-1):
            dx = hull[i+1][0] - hull[i][0]  # distance on x axis
            dy = hull[i+1][1] - hull[i][1]  # distance on y axis
            theta = pi-atan2(dy, dx)   # get orientation angle of the edge
            s, c = sin(theta), cos(theta)
            yC = hull[i][0]*s + hull[i][1]*c
            xP, yP, iP = mostfar(iP, n, s, c, 0, 1)
            if i==0: iR = iP
            xR, yR, iR = mostfar(iR, n, s, c,  1, 0)
            xL, yL, iL = mostfar(iL, n, s, c, -1, 0)
            l, w = (yP-yC), (xR-xL)
            area = l*w
#            print '    {:2d} {:2d} {:2d} {:2d} {:9.3f}'.format(i, iL, iP, iR, area)
            if area < min_area:
                min_area, min_length, min_width = area, l, w
        return (min_length, min_width, min_area)

    def _mostfar(self, j, n, s, c, mx, my):
        """ advance j to extreme point """
        hull = self.hull  # local reference
        xn, yn = hull[j][0], hull[j][1]
        rx, ry = xn*c - yn*s, xn*s + yn*c
        best = mx*rx + my*ry
        while True:
            x, y = rx, ry
            xn, yn = hull[(j+1)%n][0], hull[(j+1)%n][1]
            rx, ry = xn*c - yn*s, xn*s + yn*c
            if mx*rx + my*ry >= best:
                j = (j+1)%n
                best = mx*rx + my*ry
            else:
                return (x, y, j)

if __name__ == '__main__':

    hull= [(560023.44957588764, 6362057.3904932579),
           (560023.44957588764, 6362060.3904932579),
           (560024.44957588764, 6362063.3904932579),
           (560026.94957588764, 6362068.3904932579),
           (560028.44957588764, 6362069.8904932579),
           (560034.94957588764, 6362071.8904932579),
           (560036.44957588764, 6362071.8904932579),
           (560037.44957588764, 6362070.3904932579),
           (560037.44957588764, 6362064.8904932579),
           (560036.44957588764, 6362063.3904932579),
           (560034.94957588764, 6362061.3904932579),
           (560026.94957588764, 6362057.8904932579),
           (560025.44957588764, 6362057.3904932579),
           (560023.44957588764, 6362057.3904932579)]

    gmar = GetMinimumAreaRectangle()  # create functor object
    print "dimensions and area of smallest enclosing rectangular area:"
    print "  {:.3f}(L) x {:.3f}(W) = {:.3f} area".format(*gmar(hull))  # use it

Output:

dimensions and area of smallest enclosing rectangular area:
  10.393(L) x 18.037(W) = 187.451 area

回答2:

1. You could use either a single function or two functions, but it's probably cleaner and easier to use two functions. You can leave the mostfar function as-is. Then, just convert the second half of the code into a function by adding a function definition line:

   def get_minimum_area_rectangle(hull):
   

   …and then indenting the rest of the code (starting with n = len(hull)) to form the body of the function. You’ll also want to change the function to return the values you want to get (length, width, and area). This will keep your code modular and clean, and requires very few changes.

2. Using a list of values for hull seems fine for this purpose. The alternative would be to use an array (like a NumPy array), but in this case, you’re going through the data iteratively, one item at a time, and not doing any calculations across many data points simultaneously. So a list should be fine. Accessing items in a list is fast, and it shouldn't be a bottleneck compared with the math you have to do.

回答3:

1. You could certainly do it as a single function: slightly modify mostfar to, instead of print the areas found, track the smallest & the info that goes with it. Or you could have it collect the values it is printing into a lst, which G.E.A.R. could then use to find the minimum.

EDIT: (I'd missed that some of the code was outside of mostfar) I'd wrap the "script" part (the code after mostfar) into a function, and modify THAT as described above. Your "script" would then just invoke that function or, if using the second modification, find the min from the list returned.

1. I don't see any problem w/ your representation of hull.

回答4:

I'm posting another answer showing how to do as I (and others) have suggested, which was just to nest the helper function mostfar() inside the main one that gets called. This is pretty easy to do in Python because nested functions have access to the local variables of their enclosing scope (like hull in the case). I also renamed the function _mostfar() following the convention to indicate something is private, but that's not strictly necessary (ever, and definitely not here).

As you can see most of the code is very similar to that in my other answer although I did simplify a few things unrelated to the nesting the function (so they could probably be integrated into whatever answer you choose).

from math import atan2, cos, pi, sin

def get_minimum_area_rectangle(hull):
    """ find length, width, and area of the smallest rectangular
        area of the given convex hull """

    def _mostfar(j, n, s, c, mx, my):
        """ advance j to extreme point """
        xn, yn = hull[j]
        rx, ry = xn*c - yn*s, xn*s + yn*c
        best = mx*rx + my*ry
        k = j + 1
        while True:
            x, y = rx, ry
            xn, yn = hull[k % n]
            rx, ry = xn*c - yn*s, xn*s + yn*c
            if mx*rx + my*ry < best:
                return (x, y, j)
            else:
                j, k = k % n, j + 1
                best = mx*rx + my*ry

    n = len(hull)
    min_area = 10**100
    iL = iR = iP = 1  # indexes left, right, opposite
#   print '    {:>2s} {:>2s} {:>2s} {:>2s} {:>9s}'.format(
#              'i', 'iL', 'iP', 'iR', 'area')
    for i in xrange(n-1):
        dx = hull[i+1][0] - hull[i][0]  # distance on x axis
        dy = hull[i+1][1] - hull[i][1]  # distance on y axis
        theta = pi-atan2(dy, dx)   # get orientation angle of the edge
        s, c = sin(theta), cos(theta)
        yC = hull[i][0]*s + hull[i][1]*c
        xP, yP, iP = _mostfar(iP, n, s, c, 0, 1)
        if i==0: iR = iP
        xR, yR, iR = _mostfar(iR, n, s, c,  1, 0)
        xL, yL, iL = _mostfar(iL, n, s, c, -1, 0)
        l, w = (yP-yC), (xR-xL)
        area = l*w
#       print '    {:2d} {:2d} {:2d} {:2d} {:9.3f}'.format(i, iL, iP, iR, area)
        if area < min_area:
            min_area, min_length, min_width = area, l, w
    return (min_length, min_width, min_area)

if __name__ == '__main__':

    hull= [(560023.44957588764, 6362057.3904932579),
           (560023.44957588764, 6362060.3904932579),
           (560024.44957588764, 6362063.3904932579),
           (560026.94957588764, 6362068.3904932579),
           (560028.44957588764, 6362069.8904932579),
           (560034.94957588764, 6362071.8904932579),
           (560036.44957588764, 6362071.8904932579),
           (560037.44957588764, 6362070.3904932579),
           (560037.44957588764, 6362064.8904932579),
           (560036.44957588764, 6362063.3904932579),
           (560034.94957588764, 6362061.3904932579),
           (560026.94957588764, 6362057.8904932579),
           (560025.44957588764, 6362057.3904932579),
           (560023.44957588764, 6362057.3904932579)]

    print "dimensions and area of smallest enclosing rectangular area:"
    print "  {:.3f}(L) x {:.3f}(W) = {:.3f} area".format(
             *get_minimum_area_rectangle(hull))