def get_hexagon_points(self, num_points, area):
        sidelength = numpy.sqrt(self._array_of_areas * 2/(3 * numpy.sqrt(3)))
        height = 2 * self._hex_sidelengths
        width = numpy.sqrt(3) * self._hex_sidelengths
        xmin = -width/2
        xmax = width/2

        ymin = -height/2
        ymax = height/2

        hexagon = Hexagon(sidelength, width, height)
        xpoints = numpy.zeros(1, num_points)
        ypoints = numpy.zeros(1, num_points)
        count = 0
        while count < num_points:
            xpt = xmin + (xmax - xmin) * numpy.random.rand()
            ypt = ymin + (ymax - ymin) * numpy.random.rand()
            pt = Point((xpt, ypt))
            if pt.within(hexagon.get_polygon()):
                xpoints[count] = xpt
                ypoints[count] = ypt
                count = count + 1
            else:
                continue

        xpoints = xpoints / width
        ypoints = ypoints/ height

        return xpoints, ypoints

 def GetIntersectionDistance(self, l1, l2):
     # l1 should be just two coordinate positions
     # get its starting coorinate
     pt1 = Point(l1.coords[0])
     x = l1.intersection(l2)
     # intersections can return a lot of things
     d = -1
     if x.wkt == 'GEOMETRYCOLLECTION EMPTY':
         d = -1
         # print "nothing"
     elif re.match('^POINT', x.wkt): 
         # print "point"
         pt2 = Point(x.coords[0])
         d = pt1.distance(pt2)
     elif re.match('^MULTI', x.wkt): 
         # print "mpoint"
         # this will return the minimum distance
         pt2 = Point(x[0].coords[0])
         d = pt1.distance(pt2) 
         for pt2 in x:
             pt2 = Point(pt2)
             if d < pt1.distance(pt2):
                 d = pt1.distance(pt2)
     else:
         print 'dunno what intersection passed me'
     return d

    def is_at_goal(self):
        """Check if the robot is near its goal in both distance and rotation.

        Once the robot is near its goal, it rotates towards the final goal
        pose. Once it reaches this goal pose (within some predetermined
        rotation allowance), it is deemed to be at its goal.

        Returns
        -------
        bool
            True if the robot is at its goal, false otherwise.
        """

        goal_pt = Point(self.goal_pose[0:2])
        approximation_circle = goal_pt.buffer(self.distance_allowance)
        pose_pt = Point(self.robot.pose2D.pose[0:2])
        position_bool = approximation_circle.contains(pose_pt)
        logging.debug('Position is {}'.format(position_bool))

        degrees_to_goal = abs(self.robot.pose2D.pose[2] - self.goal_pose[2])
        orientation_bool = (degrees_to_goal < self.rotation_allowance)
        # <>TODO: Replace with ros goal message check
        if self.robot.publish_to_ROS is True:
            orientation_bool = True
        logging.debug('Orientation is {}'.format(orientation_bool))

        logging.debug('is_at_goal = {}'.format((position_bool and
                                                orientation_bool)))
        return position_bool and orientation_bool

def find_dangles(lines):
    """
    Locate all dangles
    :param lines: list of Shapely LineStrings or MultiLineStrings
    :return: list of dangles
    """
    list_dangles = []
    for i, line in enumerate(lines):
        # each line gets a number
        # go through each line added first to second
        # then second to third and so on
        shply_lines = lines[:i] + lines[i+1:]
        # 0 is start point and -1 is end point
        # run through
        for start_end in [0, -1]:
            # convert line to point
            node = Point(line.coords[start_end])
            # Return True if any element of the iterable is true.
            # https://docs.python.org/2/library/functions.html#any
            # python boolean evaluation comparison
            if any(node.touches(next_line) for next_line in shply_lines):
                continue
            else:
                list_dangles.append(node)
    return list_dangles

def getNosePoints(line,prevPoint):
        start=Point(line.coords[0])
        end=Point(line.coords[-1])
        if start.distance(prevPoint)<end.distance(prevPoint):
            return start
        else:
            return end

    def _populate_shapes(self):
        """ Set values for self._label_shapes, _footprint_shape, and others.
        """
        point = Point(self.position.x, self.position.y)
        point_buffered = point.buffer(self.radius + self.buffer, 3)
        self._point_shape = point.buffer(self.radius, 3)
        
        scale = 10.0
        font = truetype(self.fontfile, int(self.fontsize * scale), encoding='unic')

        x, y = self.position.x, self.position.y
        w, h = font.getsize(self.name)
        w, h = w/scale, h/scale
        
        for placement in placements:
            label_shape = point_label_bounds(x, y, w, h, self.radius, placement)
            mask_shape = label_shape.buffer(self.buffer, 2).union(point_buffered)
            
            self._label_shapes[placement] = label_shape
            self._mask_shapes[placement] = mask_shape
    
        unionize = lambda a, b: a.union(b)
        self._label_footprint = reduce(unionize, self._label_shapes.values())
        self._mask_footprint = reduce(unionize, self._mask_shapes.values())
        
        # number of pixels from the top of the label based on the bottom of a "."
        self._baseline = font.getmask('.').getbbox()[3] / scale

def parse(line):
	import shapefile
	line = line.split(",")
	datetime = line[2].split()
	try:
		#hour = int(time[0])
		#minute = int(time[1])
		#minute -= minute % 10
		time = datetime[1]
		time = time[0:-1] + '0'
		x = float(line[9])
		y = float(line[10])
  	except:
  		print "*********************"
  		print "Invalid Point, line is:", line
  		#print "time is:", time
  		return ("Invalid Point", 1)
	#print "**************************"
	#print "newLine is:", newLine
	sf = shapefile.Reader("../NY_counties_clip/NY_counties_clip")
	shapeRecs = sf.shapeRecords()
	point = Point(x, y)
	county = "Not found"
	for sr in shapeRecs:
		coords = sr.shape.points
		polygon = MultiPoint(coords).convex_hull
		if point.within(polygon):
			county = sr.record[6]
	newLine = (time + "," + county, 1)
	if county == "Not found":
		print "********************"
		print "County not found, point is:", x, y
	return newLine

    def compute_repulsive_ws(self, control_point, obstacle):
        point, _, eta = control_point
        # need to unpack obstacle tuple into polygon and threshold
        obstacle_poly = obstacle[0]
        obstacle_thresh = obstacle[1]

        d2obstacle = point.distance(obstacle_poly)
        # this is straight from book
        if d2obstacle > obstacle_thresh:
            return Point(0, 0)
        else:
            # scalar is length of vector that points away from closest obstacle
            # point
            scalar = eta * ((obstacle_thresh ** -1) - (d2obstacle ** -1)) * (d2obstacle ** -2)
            # construct gradient vector

            # find closest point, you can ignore the details Yinan
            pol_ext = obstacle_poly
            if obstacle_poly.geom_type != "LineString":
                pol_ext = LinearRing(obstacle_poly.exterior.coords)
            d = pol_ext.project(point)
            p = pol_ext.interpolate(d)
            # closest point
            c = Point(list(p.coords)[0])
            dqc = c.distance(point)
            # from book, formula for delta vector
            delta_d_i = Point(((point.x - c.x) / dqc, (point.y - c.y) / dqc))

            return Point((-1 * delta_d_i.x * scalar, -1 * delta_d_i.y * scalar))

def ring(centerx, centery, radius, width):
    """
    a circular ring
    """
    c_out = Point(centerx, centery).buffer(radius)
    c_in = Point(centerx, centery).buffer(radius - width)
    return c_out.difference(c_in)

def find_valid_edges(vertexes, edges, env, polygons):
    valid_edges = []
    for i, p1 in enumerate(vertexes):
        print i
        for p2 in [x for x in vertexes if not x == p1]:
            add = True
            line2 = LineString([p1, p2])
            if env.crosses(line2):
                continue

            xx, yy = line2.xy

            # Midpoint will lie within a shape if the line is composed of two vertices of the polygon
            m = Point(sum(xx)/2., sum(yy)/2.)
            if [x for x in polygons if m.within(x)]:
                continue    # skip this edge if it is within a polygon

            for edge in edges:
                line1 = LineString(edge)

                if add and not line1 == line2 and line1.crosses(line2):
                    add = False
                    break
            if add:
                valid_edges.append([p1, p2])
    return valid_edges

def batch(num_features):
    # Coordinate values in range [0, 50]
    x = partial(random.uniform, 0.0, 50.0)
    # radii in range [0.01, 0.5]
    r = partial(random.uniform, 0.01, 0.5)
    # Poisson-distributed resolution k
    def k(expectation=1):
        #partial(random.randint, 1, 4)
        L = math.exp(-expectation)
        k = 0
        p = 1
        while p > L:
            k = k + 1
            u = random.uniform(0.0, 1.0)
            p = p * u
        return k - 1


    batch = {'index': []}
    for i in xrange(num_features):
        point = Point(x(), x())
        polygon = point.buffer(r(), k())
        batch['index'].append(dict(
            id=str(i+1), 
            bbox=polygon.bounds, 
            geometry=mapping(polygon), 
            properties=dict(title='Feature %d' % (i+1)))
            )
    return batch

   def check(self, latitude, longitude):
      current_point = Point(latitude, longitude)
      cur_ts = datetime.utcnow()

      if current_point.within(self.START_POLY):
         if self.inside_area:
            return False
         else:
            self.inside_area = True
            return self.CHECKPOINT_START

      elif current_point.within(self.SECTOR2_POLY):
         if self.inside_area:
            return False
         else:
            self.inside_area = True
            return self.CHECKPOINT_SECTOR2

      elif current_point.within(self.SECTOR3_POLY):
         if self.inside_area:
            return False
         else:
            self.inside_area = True
            return self.CHECKPOINT_SECTOR3

      else:
         self.inside_area = False

      return False

    def evaluate(self, action, zones, graph):

        scenario = Scenario_Generator(
            self.width,
            self.height,
            self.immobile_objs,
            self.mobile_objs,
            self.manipulatable_obj,
            self.target_obj,
            showRender=False,
        )
        game_objects = scenario.getGameObjects()
        end_position, shape = scenario.evaluate(action)
        radius = shape.radius
        end_position = Point(end_position)
        circular_region_ball = end_position.buffer(radius)
        occupied_zones = []
        for i in xrange(len(zones)):
            if zones[i].intersects(circular_region_ball):
                occupied_zones.append(i)
        if len(occupied_zones) == 0:
            return len(zones)  # set to the maximum length
        min_d = 9999
        for occupied_zone in occupied_zones:
            length = nx.shortest_path_length(graph, source=occupied_zone, target=self.target_zone)

            if length < min_d:
                min_d = length

        return min_d

    def find_edge_nodes(fargs):
        """ Find nodes are near the edge of the hull"""
        cluster, cluster_hull, nodes = fargs
        # There is no hull for this community, it's been deleted.
        if cluster_hull is None:
            log.error("Missing hull, keeping all nodes in cluster %i",
                      cluster)
            return len(nodes), nodes

        characteristic_size = math.sqrt(cluster_hull.area)
        allowed_distance = characteristic_size * args.within
        boundary = cluster_hull.boundary

        output = []
        for node in nodes:
            # check if it is an interior node
            point = Point((node.lon, node.lat))
            keep = False
            if random.random() < args.keep:
                keep = True
            elif point.distance(boundary) < allowed_distance:
                keep = True
            if keep:
                output.append(node)
        return len(nodes), output

    def fill_polygon_with_points(cls, goal=None, polygon=None):
        """
            Fill a shapely polygon with X number of points
        """
        if goal is None:
            raise ValueError("Must specify the number of points (goal) to fill the polygon with")

        if polygon is None or (not isinstance(polygon, Polygon) and not isinstance(polygon, MultiPolygon)):
            raise ValueError("Must specify a polygon to fill points with")

        minx = polygon.bounds[0] 
        maxx = polygon.bounds[2] 
        miny = polygon.bounds[1] 
        maxy = polygon.bounds[3] 

        points = []
        now = time.time()
        while len(points) < goal:
            random_x = random.uniform(minx, maxx)
            random_y = random.uniform(miny, maxy)
            p = Point(random_x, random_y)
            if p.within(polygon):
                points.append(p)

        logger.info("Filling polygon with points took %f seconds" % (time.time() - now))

        return points

def solve(f, R, t, r, g):
    # make the circle
    outerCircle = Point(0, 0).buffer(R, 1 << 12)
    # make the ring
    innerCircle = Point(0, 0).buffer(R - t - f, 1 << 12)
    # make the bars
    bars = []
    leftMin = -r - (2 * r + g) * (int(R / (2 * r + g)) + 1) 
    left = leftMin
    while left < R:
        bars.append(box(left, -R, left + 2 * r + 2 * f, R))
        left += 2 * r + g
    
    bottom = leftMin
    while bottom < R:
        bars.append(box(-R, bottom, R, bottom + 2 * r + 2 * f))
        bottom += 2 * r + g
        
    # get the union
    union = outerCircle.difference(innerCircle)
    for bar in bars:
        union = union.union(bar)
    # intersection with prev shape
    finalPattern = union.intersection(outerCircle)    
    # calc area ratio
    result = finalPattern.area / outerCircle.area
    return '%.6f' % result

 def check_geofence (self, x_utm = None, y_utm = None):
     '''
     method to check to see if a point is within the
     geofence. If x_utm or y_utm is not given, this checks
     the present location.
     
     x_utm = the x utm to check (m)
     y_utm = the y utm to check (m)
     returns true (yes within geofence) or false (no not in geofence)
     '''
     if x_utm is None and y_utm is None:
         x_utm = self.bs['x_utm']
         y_utm = self.bs['y_utm']
         using_present_location = True
     else:
         using_present_location = False
     
     test_point = Point (x_utm, y_utm)
     in_geofence = test_point.within (self.geofence)
     
     # update the been in geofence flag so it flips high if this is
     # the first call of this method inside of the geofence
     if using_present_location and in_geofence:
         self.been_in_geofence = True
     
     return (in_geofence)

def Check_Poly(ev_lat,ev_lon):
  #St_poly = Polygon(((37.80375833333333,-122.26878055555555),
  #  (37.80314722222222,-122.26916388888888),
  #  (37.80622222222222,-122.277425),
  #  (37.80683888888888,-122.277025)))
  '''St_poly = Polygon(((37.80174722222222,-122.27128888888889),
    (37.80349444444444,-122.27603055555555),
    (37.80786944444444,-122.27381666666666),
    (37.806755555555554,-122.26869166666667),
    (37.812374999999996,-122.26591111111111),
    (37.81121388888889,-122.2636),
    (37.806869444444445,-122.26615555555556),
    (37.80575833333333,-122.26838055555555)))'''
  '''poly = Polygon(((37.878160,-122.257492),   # university Ave
    (37.873646,-122.284185),
    (37.870511,-122.309028),
    (37.863800,-122.305111),
    (37.869214,-122.254670)))'''
# dt oakland (larger region)
  poly = Polygon(((37.812594,-122.270164),
    (37.822968,-122.267433),
    (37.821722,-122.259872),
    (37.797118,-122.249193),
    (37.787229,-122.263842),
    (37.794675,-122.289563),
    (37.805828,-122.288179),
    (37.802708,-122.278026)))
  point = Point((ev_lat,ev_lon))
  in_poly = point.within(poly)
  return in_poly

def is_stable(lon, lat):
    """
    Determine if point is located in the US stable tectonic region. Uses the
    same boundary as the US NSHMP and so this function needs to be modified to
    work outside of the US.

    Args:
        lon (float): Lognitude.
        lat (float): Latitude.

    Returns:
        bool: Is the point classified as tectonically stable.

    """
    p = Point((lon, lat))
    pfile = pkg_resources.resource_filename('shakelib.utils', 
            os.path.join('data', 'cratons.geojson'))
    with open(pfile) as f:
        cratons = json.load(f)
    coord_list = cratons['features'][0]['geometry']['coordinates']
    for clist in coord_list:
        poly = Polygon(clist[0])
        if p.within(poly):
            return True
    return False

def ring(lat, lon, R, r, proj, EC=2.5):
    """Creates a ring defined by two circles with radiuses r, R
    centered at x, y

    Args:
        lat, lon:   latitude and longitude
        R: outer radius of the ring in m
        r: inner radius of the ring in m
        proj. projection used
        EC: correction parameter
    """
    if R == r:
        return None

    # get projected coordinates
    (x, y) = proj(lon, lat)

    # error adjust rings
    error_r = EC * projections.proj_error(proj, [lat, lon], r, 0)
    error_R = EC * projections.proj_error(proj, [lat, lon], R, 0)

    r -= math.fabs(error_r)
    R += math.fabs(error_R)

    if R > r:
        outer_circle = Point(x, y).buffer(R)
        inner_circle = Point(x, y).buffer(r)
    else:
        outer_circle = Point(x, y).buffer(r)
        inner_circle = Point(x, y).buffer(R)

    ring = outer_circle.difference(inner_circle)

    return ring