import math


def extrapolate_lines(lines, img_shape, min_slope=0.3):
    """Aggregate detectes lines into two lanes by extrapolation

    Args:
        lines (list<list<tuple>>): detected lines
        img_shape (tuple<int>): image shape
        min_slope (float, optional): minimum slope to consider the edge as being part of the lane

    Returns:
        list<tuple>: list of extrapolated lanes
    """

    extrapolated_lines = []

    # Store slopes
    left_slopes, right_slopes = [], []
    left_intercepts, right_intercepts = [], []
    ymin = img_shape[0]
    for line in lines:
        for x1, y1, x2, y2 in line:
            slope = (y2 - y1) / (x2 - x1)
            intercept = y2 - slope * x2
            # Reduce noise for outliers
            if min_slope < abs(slope) < math.inf:
                # Check if left lane
                if slope < 0:
                    # Double check to avoid noise from other part of the image
                    if max(x1, x2) < img_shape[1] / 2:
                        left_slopes.append(slope)
                        left_intercepts.append(intercept)
                else:
                    if min(x1, x2) > img_shape[1] / 2:
                        right_slopes.append(slope)
                        right_intercepts.append(intercept)
                ymin = min(ymin, y1, y2)

    if len(left_slopes) > 0:
        # Average slope and intercept
        left_slope = sum(left_slopes) / len(left_slopes)
        left_intercept = sum(left_intercepts) / len(left_intercepts)
        # Add the extrapolated lane
        left = (int((img_shape[0] - left_intercept) / left_slope), img_shape[0],
                int((ymin - left_intercept) / left_slope), int(ymin))
        extrapolated_lines.append(left)

    if len(right_slopes) > 0:
        right_slope = sum(right_slopes) / len(right_slopes)
        right_intercept = sum(right_intercepts) / len(right_intercepts)
        right = (int((img_shape[0] - right_intercept) / right_slope), img_shape[0],
                 int((ymin - right_intercept) / right_slope), int(ymin))
        extrapolated_lines.append(right)

    return extrapolated_lines