def min_bounding_box(p):
    ''' return the minimum-area bounding box (any orientation) of a convex polygon p.'''
    
    def rotate_points(pts, theta):
        R = np.array([[np.cos(theta), -np.sin(theta)],
                      [np.sin(theta),  np.cos(theta)]])
        return np.dot(R, pts.T).T
        
    def bbox_area(pts):
        min_pts = pts.min(axis=0)
        max_pts = pts.max(axis=0)
        return np.product(max_pts - min_pts)
    
    edges = np.diff(np.array(p.boundary), axis=0)
    angles = np.arctan2(edges[:,1], edges[:,0]) # polar angles of each edge in p

    zero_pt = (0,0)
    pts = np.array(p.boundary)
    
    '''Minimum-area bounding box of cvx poly must be aligned with an edge.
    So rotate polygon by negative polar angle, fit axis-aligned bbox, repeat and 
    choose box with minimum area'''
    min_area = np.inf
    for angle in angles: 
        pts_rot = rotate_points(pts, -angle)
        area = bbox_area(pts_rot)
        if area < min_area:
            min_area = bbox_area(pts_rot)
            min_angle = angle
            
    p_rot = affinity.rotate(p, -min_angle, origin=zero_pt, use_radians=True)
    return affinity.rotate(p_rot.envelope, min_angle, origin=zero_pt, use_radians=True), min_angle

def saveR(rectangles, A, cc, n):
    zona = takeZona(n)
    polis =[]
    for r in rectangles:
        polis.append(r[0])

    union = affinity.rotate(cascaded_union(polis), -A, origin=cc)
    dx = union.centroid.x-cc.x
    dy = union.centroid.y-cc.y
    print 'translate : ',dx, dy
    data2save=()
    for r in rectangles:
        rotated=affinity.rotate(r[0], -A, origin=cc)
        translated = affinity.translate(rotated, -dx, -dy)
        #verificar si interseca
        print zona.intersects(translated)
        if zona.intersects(translated):
            data = (n, A, r[1], r[2], "SRID=25831;"+str(translated))
            data2save += (data,)
        #print data
    conn = db.connect(rootData)
    c = conn.cursor()
    c.executemany('''insert into elementsdiv ( name, ang, x, y, geometry ) values ( ?, ?, ?,?, GeomFromEWKT( ? ) )''', data2save )
    conn.commit()
    conn.close()

    return

def getFacets(p1,p2, curve):
    
    if p2.x == p1.x:
        leveling_angle = math.radians(90)
    else:
        leveling_angle = -math.atan((p2.y-p1.y)/(p2.x-p1.x))
    p1p = p1#rotate(p1, leveling_angle, origin=p1, use_radians=True)
    p2p = affinity.rotate(p2, leveling_angle, origin=p1, use_radians=True) # rotate p2 around p1, so they lie on a horizontal line.  Finding the center is easier this way.
    
    l = (p2p.x-p1p.x)/2  # half the distance between the points.
    h = l/math.tan(-curve/2) # compute the distance to the center of the circle
                             # from the line connecting the two points.
    
    cp = shapes.Point(p1p.x + l, p1p.y-h) # the center of the (rotated) circle.
    c = affinity.rotate(cp, -leveling_angle, origin=p1, use_radians=True)  # unrotate the circle to get the center of the original circle.

    # how man line segments to use to approximate the curve.  Bound the angle between consecutive segments to 5 degrees. ALways have at least 10 segments.
    facets = max(10, int(math.ceil(abs(curve)/5)))
    
    points = []
    t = p1
    for i in range(1,facets + 2):  # Generate the segments by rotating p1
                                   # around the center a little bit at a time.
        points.append(t)
        t = affinity.rotate(t, curve/facets, origin=c, use_radians=True)

    return points

def perpendicular_at(line, point, length):
    """
    line: a linestring
    point: a point within the line at which to search for a perpendicular line
    length: length of the line
    """
    point = asPoint(point)
    E = 1e-8
    if line.intersects(point):
        refpoint = point
    else:
        r = 16
        while True:
            refpoint = point.buffer(line.distance(point)+E, resolution=r).exterior.intersection(line)
            if not refpoint.is_empty:
                break
            else:
                r = r * 2
        assert not refpoint.is_empty
    a = line_angle_at(line, refpoint)
    a2 = a + pi/2
    p2 = Point(point.x, point.y + length*0.5)
    p3 = rotate(p2, -math.degrees(a2), origin=point)
    p4 = rotate(p2, (180 - math.degrees(a2)), origin=point)
    l = linestr(p3, p4)
    return l

def generate_patterns(depths):
    cuts_n = list(generate_cuts(depths))
    cuts_e = [rotate(x, 90) for x in cuts_n]
    cuts_s = [rotate(x, 180) for x in cuts_n]
    cuts_w = [rotate(x, 270) for x in cuts_n]
    for cut_n, cut_e, cut_s, cut_w in product(cuts_n, cuts_e, cuts_s, cuts_w):
        poly = cut_n.union(cut_e).union(cut_s).union(cut_w)
        yield poly

def plot_arrow(color, center_line, dist, normalized=False):
    ARROW_LENGTH = 3.0
    origin_p = center_line.interpolate(dist, normalized=normalized)
    normal_line = get_normal_to_line(center_line, dist, normalized=normalized)
    half_arrow = extend_line(normal_line, ARROW_LENGTH - normal_line.length, direction="forward")
    half_arrow = affinity.rotate(half_arrow, -55.0, origin=origin_p)
    plot_line(color, half_arrow)
    half_arrow = affinity.rotate(half_arrow, -70.0, origin=origin_p)
    plot_line(color, half_arrow)

def generate_panels_test(wafer_size, panel_list):
    panels0 = SectorGeneratorTest(wafer_size*sqrt3o2, panel_list)(Point(0,0))
    panels = []
    panels.append(panels0)
    panels.append([rotate(panel, 60, origin=(0,0)) for panel in panels0])
    panels.append([rotate(panel, 120, origin=(0,0)) for panel in panels0])
    panels.append([rotate(panel, 180, origin=(0,0)) for panel in panels0])
    panels.append([rotate(panel, 240, origin=(0,0)) for panel in panels0])
    panels.append([rotate(panel, 300, origin=(0,0)) for panel in panels0])
    return panels

def generate_panels(wafer_size):
    panels0 = SectorGenerator(wafer_size*sqrt3o2)(Point(0,wafer_size*sqrt3o2*2))
    panels = []
    panels.append(panels0)
    panels.append([rotate(panel, 60, origin=(0,0)) for panel in panels0])
    panels.append([rotate(panel, 120, origin=(0,0)) for panel in panels0])
    panels.append([rotate(panel, 180, origin=(0,0)) for panel in panels0])
    panels.append([rotate(panel, 240, origin=(0,0)) for panel in panels0])
    panels.append([rotate(panel, 300, origin=(0,0)) for panel in panels0])
    return panels

def _crop_after_rotation(im, angle, xres, yres, surroundings):
    """Crop image to the bounding box of bite's surroundings.

    Arguments:

    im: PIL.Image, rotated map part
    angle: by which the map has been rotated, in degrees (counterclockwise)
    xres: width of one tile in pixels
    yres: height of one tile in pixels
    surroundings: shapely.geometry.polygon.Polygon
    """

    #before rotation
    x1, y1, x2, y2 = surroundings.bounds
    old_bb_upper_left = Point(x1, y1)
    old_bb_upper_right = Point(x2, y1)
    old_bb_bottom_left = Point(x1, y2)
    old_bb_center = ((x1+x2)/2, (y1+y2)/2)

    #shapely y-axis goes upwards
    shapely_angle = -angle

    #after rotation
    x1, y1, x2, y2 = affinity.rotate(surroundings, shapely_angle, origin=old_bb_center).bounds
    crop_upper_left = Point(x1, y1)
    crop_width = x2 - x1
    crop_height = y2 - y1

    #points where old bounding box of surroundings (i.e. the old image) touches
    #its bounding box after rotation
    tl = None #touch at the left side of the new bounding box
    tt = None #touch at the top side of the new bounding box
    if angle > 0:
        tl = affinity.rotate(old_bb_upper_left, shapely_angle, origin=old_bb_center)
        tt = affinity.rotate(old_bb_upper_right, shapely_angle, origin=old_bb_center)
    else:
        tl = affinity.rotate(old_bb_bottom_left, shapely_angle, origin=old_bb_center)
        tt = affinity.rotate(old_bb_upper_left, shapely_angle, origin=old_bb_center)

    #upper left corner of ther new bounding box
    new_bb_upper_left = Point(tl.x, tt.y)

    #from these we get b: upper left corner of the crop area relative to new_bb_upper_left
    b = (crop_upper_left.x - new_bb_upper_left.x, crop_upper_left.y - new_bb_upper_left.y)

    #crop rectangle in pixels relative to new_bb_upper_left
    crop_box = [int(x) for x in [
        b[0] * xres,
        b[1] * yres,
        (b[0] + crop_width) * xres,
        (b[1] + crop_height) * yres
    ]]
    cropped = im.crop(box=crop_box)
    cropped.load()
    return cropped

def generate_sectors(full_layer, wafer_size):
    sector = Polygon([(0,0)]+list(full_layer.exterior.coords)[:2])
    sector = shift_point(sector, 0, (0,wafer_size*sqrt3o2))
    sector = shift_point(sector, 1, (0,wafer_size*sqrt3o2))
    sectors = [sector]
    sectors.append(rotate(sector, 60, origin=(0,0)))
    sectors.append(rotate(sector, 120, origin=(0,0)))
    sectors.append(rotate(sector, 180, origin=(0,0)))
    sectors.append(rotate(sector, 240, origin=(0,0)))
    sectors.append(rotate(sector, 300, origin=(0,0)))
    return sectors

 def __init__(self, hexagon_size, length=3, width=2):
     v0 = Point((0,0))
     v1 = Point((0,hexagon_size*(length-1)))
     v2 = Point((0,hexagon_size*(length+width-2)))
     v2 = rotate(v2, 120, origin=v1)
     v3 = Point((0,hexagon_size*(width-1)))
     v3 = rotate(v3, 120, origin=v0)
     self._vertices = [(v0.x,v0.y),(v1.x,v1.y),(v2.x,v2.y),(v3.x,v3.y)]
     # create mirrored panel
     v2_mirror = rotate(v2, -240, origin=v1)
     v3_mirror = rotate(v3, -240, origin=v0)
     self._vertices_mirror = [(v2_mirror.x,v2_mirror.y),(v3_mirror.x,v3_mirror.y),(v0.x,v0.y),(v1.x,v1.y)]

def findMinCv(name, polygon):
    bb = polygon.bounds
    ang = 0
    refarea = Bounds(polygon).area
    cc=polygon.centroid
    for p in range(len(polygon.exterior.coords[:])-1):
        angle = getAngle(polygon.exterior.coords[p], polygon.exterior.coords[p+1])
        rPolygon= affinity.rotate(polygon, angle, origin=cc)
        if Bounds(rPolygon).area < refarea:
            ang = angle
            bbx = affinity.rotate(Bounds(rPolygon), (360-angle), origin = cc)
            #bbx = affinity.rotate(Bounds(rPolygon), (angle), origin = cc)
    return (bbx, ang)

def cov_trans_and_rotate(p, obst_cov):
    ''' do cov transform as above, fit minimum bounding box, then rotate so bbox is
    axis-aligned '''
    p_w, W = cov_transform(p, obst_cov)
    bbox, bbox_angle = min_bounding_box(p_w)
       
    p_rw = affinity.rotate(p_w, -bbox_angle, origin=(0,0), use_radians=True)
    bbox_r = affinity.rotate(bbox, -bbox_angle, origin=(0,0), use_radians=True)
    
    theta = -bbox_angle
    R = np.array([[np.cos(theta), -np.sin(theta)],
                  [np.sin(theta),  np.cos(theta)]]) 
    return p_rw, bbox_r, np.dot(R,W)

    def rotate(self, polygon, angle, refpoint=Point()):
        """
        rotate polygon around ref point

        :param polygon:
        :param angle: in degree
        :param point:
        :return:
        """

        if refpoint.is_empty:
            refpoint = polygon.centroid
            return affinity.rotate(polygon, angle, refpoint)
        else:
            return affinity.rotate(polygon, angle, refpoint)

 def __init__(self, x=0, y=0, z=0, 
              N_slits=10, width=.0005, 
              spacing=.002, length=.025, 
              angle=0, angle_units='degrees',
              **kwargs):
     
     positions = spacing * np.array(range(N_slits))
     positions = positions - np.mean(positions)
     
     geometry = MultiPolygon(
                [Polygon([(-length/2.0 + y, -width/2.0 + i + z),
                          (-length/2.0 + y, +width/2.0 + i + z),
                          (+length/2.0 + y, +width/2.0 + i + z),
                          (+length/2.0 + y, -width/2.0 + i + z)]) 
                                                         for i in positions]
     )
     
     if angle_units=='degrees':
         angle = angle
     elif angle_units=='radians':
         angle = angle * 180/np.pi
     else:
         raise IOError('unrecognized angle units')
         
     if angle != 0:
         geometry = rotate(geometry, angle, origin=Point((y, z)))
     
     super(PolygonGratingCollimator, self).__init__(x, geometry, **kwargs)

    def valid_edge(self, state, primitive, plot = True):

        bounding_poly = affinity.rotate(primitive.bounding_poly, state[2], origin = (0.0, 0.0), use_radians = True)
        bounding_poly = affinity.translate(bounding_poly, state[0], state[1])

        #Drawing Primitive-TAKE OUT TODO
        if plot:
            if bounding_poly.intersects(self.world_polys):
                color = 'r'
            else:
                color = 'b'

            fig = plt.figure(2)
            fig.clear()
            plt.ion()
            ax = fig.add_subplot(111, aspect = 'equal')
            for poly in self.world_polys:
                P = PolygonPatch(poly, fc = 'k', zorder = 2)
                ax.add_patch(P)
            P = PolygonPatch(bounding_poly, fc = color, ec = '#999999', alpha = 1, zorder = 1)
            polyPatch = ax.add_patch(P)
            ax.set_xlim(0,50)
            ax.set_ylim(0,50)
            fig.show()
            plt.pause(0.1)
            #pdb.set_trace()
        
        if bounding_poly.intersects(self.world_polys):

            return False
        return True

    def to_shapely(self):
        """Create a shapely half circle rotated by the fan's angle.

        Notes
        =====
        `Motivated by: <https://stackoverflow.com/a/30762727/680232>`_
        """
        # Define the arc (presumably ezdxf uses a similar convention)
        centerx, centery = self.semi_circle_center

        # make a semi-circle first that points to the x-axis, rotate later.
        start_angle = 270  # In degrees

        # number of elements for the semi-circle
        numsegments = 100

        # The coordinates of the arc
        theta = np.radians(np.linspace(start_angle, start_angle+180, numsegments))
        x = centerx + self.radius * np.cos(theta)
        y = centery + self.radius * np.sin(theta)

        arc = geom.LineString(np.column_stack([x, y]))

        rotated = affinity.rotate(arc, self.data.angle,
                                  origin=tuple(self.semi_circle_center))

        df = pd.DataFrame(np.vstack([self.coords[::-1][:2], np.array(rotated)]))
        return geom.Polygon(df.round(2).drop_duplicates().values)

def map_to_polygon(shape,origin,position,rotation,size):
    geom_obj=Polygon(shape)
    geom_obj=affinity.translate(geom_obj, -origin[0],-origin[1],0)
    geom_obj=affinity.scale(geom_obj,size[0],size[1],origin=(0,0))
    geom_obj=affinity.rotate(geom_obj,int(rotation*360),origin=(0,0))
    geom_obj=affinity.translate(geom_obj, position[0],position[1],0)
    return geom_obj

def line_extrapolate_point(l, p, length):
    """
    Return a Point p2 which would extend the line `l` so that it
    would have a length of `length`

    l: a line
    p: a point within that line
    length: the length that a line from p to p2 would have

    """
    p = Point(*_normalize_point(p))
    a = line_angle_at(l, p)
    if a > pi:
        a = a % pi
    p2 = Point(p.x, p.y + length)
    c = l.centroid
    if p.x < c.x:
        if p.y < c.y:
            angle = pi-a
        else:
            angle = a
    elif p.x > c.x:
        if p.y < c.y:
            angle = -a
        else:
            angle = -a
    else:
        if p.y < c.y:
            angle = a + pi
        elif p.y > c.y:
            angle = a % pi
        else:
            angle = 100
    p3 = rotate(p2, math.degrees(angle), origin=p)
    return p3

 def _do_inverse_transform(shape, rotation, mirrored, rotation_origin=(0,0), scale_origin=(0,0)):
     if shape is None or shape.is_empty:
         return shape
     r = shape
     r = affinity.scale(r, xfact=(-1 if mirrored else 1), origin=scale_origin)
     r = affinity.rotate(r, -rotation, origin=rotation_origin)
     return r;