How to merge lines after HoughLinesP?

Question

My task is to find coordinates of lines (startX, startY, endX, endY) and rectangles (4 lines). Here is input file:

I use the next code:

img = cv.imread(image_src)
gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
ret, thresh1 = cv.threshold(gray,127,255,cv.THRESH_BINARY)

edges = cv.Canny(thresh1,50,150,apertureSize = 3)

minLineLength = 100
maxLineGap = 10
lines = cv.HoughLinesP(edges,1,np.pi/180,10,minLineLength,maxLineGap)
print(len(lines))
for line in lines:
    cv.line(img,(line[0][0],line[0][1]),(line[0][2],line[0][3]),(0,0,255),6)

I get the next results:

From the last image you can see big amount of small red lines.

Questions:

1. What is the best way to merge small lines?
2. Why there are a lot of small portions that are not detected by HoughLinesP?

Answer 1

The rewritten Python code from banderlog013 still has issues regarding orientation handling and merging of line segments. The folowing code addresses these issues and can be used directly with the output from HoughLinesP from OpenCV.

class HoughBundler:     
    def __init__(self,min_distance=5,min_angle=2):
        self.min_distance = min_distance
        self.min_angle = min_angle
    
    def get_orientation(self, line):
        orientation = math.atan2(abs((line[3] - line[1])), abs((line[2] - line[0])))
        return math.degrees(orientation)

    def check_is_line_different(self, line_1, groups, min_distance_to_merge, min_angle_to_merge):
        for group in groups:
            for line_2 in group:
                if self.get_distance(line_2, line_1) < min_distance_to_merge:
                    orientation_1 = self.get_orientation(line_1)
                    orientation_2 = self.get_orientation(line_2)
                    if abs(orientation_1 - orientation_2) < min_angle_to_merge:
                        group.append(line_1)
                        return False
        return True

    def distance_point_to_line(self, point, line):
        px, py = point
        x1, y1, x2, y2 = line

        def line_magnitude(x1, y1, x2, y2):
            line_magnitude = math.sqrt(math.pow((x2 - x1), 2) + math.pow((y2 - y1), 2))
            return line_magnitude

        lmag = line_magnitude(x1, y1, x2, y2)
        if lmag < 0.00000001:
            distance_point_to_line = 9999
            return distance_point_to_line

        u1 = (((px - x1) * (x2 - x1)) + ((py - y1) * (y2 - y1)))
        u = u1 / (lmag * lmag)

        if (u < 0.00001) or (u > 1):
            #// closest point does not fall within the line segment, take the shorter distance
            #// to an endpoint
            ix = line_magnitude(px, py, x1, y1)
            iy = line_magnitude(px, py, x2, y2)
            if ix > iy:
                distance_point_to_line = iy
            else:
                distance_point_to_line = ix
        else:
            # Intersecting point is on the line, use the formula
            ix = x1 + u * (x2 - x1)
            iy = y1 + u * (y2 - y1)
            distance_point_to_line = line_magnitude(px, py, ix, iy)

        return distance_point_to_line

    def get_distance(self, a_line, b_line):
        dist1 = self.distance_point_to_line(a_line[:2], b_line)
        dist2 = self.distance_point_to_line(a_line[2:], b_line)
        dist3 = self.distance_point_to_line(b_line[:2], a_line)
        dist4 = self.distance_point_to_line(b_line[2:], a_line)

        return min(dist1, dist2, dist3, dist4)

    def merge_lines_into_groups(self, lines):
        groups = []  # all lines groups are here
        # first line will create new group every time
        groups.append([lines[0]])
        # if line is different from existing gropus, create a new group
        for line_new in lines[1:]:
            if self.check_is_line_different(line_new, groups, self.min_distance, self.min_angle):
                groups.append([line_new])

        return groups

    def merge_line_segments(self, lines):
        orientation = self.get_orientation(lines[0])
      
        if(len(lines) == 1):
            return np.block([[lines[0][:2], lines[0][2:]]])

        points = []
        for line in lines:
            points.append(line[:2])
            points.append(line[2:])
        if 45 < orientation <= 90:
            #sort by y
            points = sorted(points, key=lambda point: point[1])
        else:
            #sort by x
            points = sorted(points, key=lambda point: point[0])

        return np.block([[points[0],points[-1]]])

    def process_lines(self, lines):
        lines_horizontal  = []
        lines_vertical  = []
  
        for line_i in [l[0] for l in lines]:
            orientation = self.get_orientation(line_i)
            # if vertical
            if 45 < orientation <= 90:
                lines_vertical.append(line_i)
            else:
                lines_horizontal.append(line_i)

        lines_vertical  = sorted(lines_vertical , key=lambda line: line[1])
        lines_horizontal  = sorted(lines_horizontal , key=lambda line: line[0])
        merged_lines_all = []

        # for each cluster in vertical and horizantal lines leave only one line
        for i in [lines_horizontal, lines_vertical]:
            if len(i) > 0:
                groups = self.merge_lines_into_groups(i)
                merged_lines = []
                for group in groups:
                    merged_lines.append(self.merge_line_segments(group))
                merged_lines_all.extend(merged_lines)
                    
        return np.asarray(merged_lines_all)

# Usage:
lines = cv.HoughLinesP(edges, 1, np.pi / 180, 50, None, 50, 10)
bundler = HoughBundler(min_distance=10,min_angle=5)
lines = bundler.process_lines(lines)

Answer 2

Rewritten code above, it is 30% faster, shorter and, IMHO, more understandable:

class HoughBundler:
    '''Clasterize and merge each cluster of cv.HoughLinesP() output
    a = HoughBundler()
    foo = a.process_lines(houghP_lines, binary_image)
    '''

    def get_orientation(self, line):
        '''get orientation of a line, using its length
        https://en.wikipedia.org/wiki/Atan2
        '''
        orientation = math.atan2(abs((line[0] - line[2])), abs((line[1] - line[3])))
        return math.degrees(orientation)

    def checker(self, line_new, groups, min_distance_to_merge, min_angle_to_merge):
        '''Check if line have enough distance and angle to be count as similar
        '''
        for group in groups:
            # walk through existing line groups
            for line_old in group:
                # check distance
                if self.get_distance(line_old, line_new) < min_distance_to_merge:
                    # check the angle between lines
                    orientation_new = self.get_orientation(line_new)
                    orientation_old = self.get_orientation(line_old)
                    # if all is ok -- line is similar to others in group
                    if abs(orientation_new - orientation_old) < min_angle_to_merge:
                        group.append(line_new)
                        return False
        # if it is totally different line
        return True

    def DistancePointLine(self, point, line):
        """Get distance between point and line
        http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/source.vba
        """
        px, py = point
        x1, y1, x2, y2 = line

        def lineMagnitude(x1, y1, x2, y2):
            'Get line (aka vector) length'
            lineMagnitude = math.sqrt(math.pow((x2 - x1), 2) + math.pow((y2 - y1), 2))
            return lineMagnitude

        LineMag = lineMagnitude(x1, y1, x2, y2)
        if LineMag < 0.00000001:
            DistancePointLine = 9999
            return DistancePointLine

        u1 = (((px - x1) * (x2 - x1)) + ((py - y1) * (y2 - y1)))
        u = u1 / (LineMag * LineMag)

        if (u < 0.00001) or (u > 1):
            #// closest point does not fall within the line segment, take the shorter distance
            #// to an endpoint
            ix = lineMagnitude(px, py, x1, y1)
            iy = lineMagnitude(px, py, x2, y2)
            if ix > iy:
                DistancePointLine = iy
            else:
                DistancePointLine = ix
        else:
            # Intersecting point is on the line, use the formula
            ix = x1 + u * (x2 - x1)
            iy = y1 + u * (y2 - y1)
            DistancePointLine = lineMagnitude(px, py, ix, iy)

        return DistancePointLine

    def get_distance(self, a_line, b_line):
        """Get all possible distances between each dot of two lines and second line
        return the shortest
        """
        dist1 = self.DistancePointLine(a_line[:2], b_line)
        dist2 = self.DistancePointLine(a_line[2:], b_line)
        dist3 = self.DistancePointLine(b_line[:2], a_line)
        dist4 = self.DistancePointLine(b_line[2:], a_line)

        return min(dist1, dist2, dist3, dist4)

    def merge_lines_pipeline_2(self, lines):
        'Clusterize (group) lines'
        groups = []  # all lines groups are here
        # Parameters to play with
        min_distance_to_merge = 30
        min_angle_to_merge = 30
        # first line will create new group every time
        groups.append([lines[0]])
        # if line is different from existing gropus, create a new group
        for line_new in lines[1:]:
            if self.checker(line_new, groups, min_distance_to_merge, min_angle_to_merge):
                groups.append([line_new])

        return groups

    def merge_lines_segments1(self, lines):
        """Sort lines cluster and return first and last coordinates
        """
        orientation = self.get_orientation(lines[0])

        # special case
        if(len(lines) == 1):
            return [lines[0][:2], lines[0][2:]]

        # [[1,2,3,4],[]] to [[1,2],[3,4],[],[]]
        points = []
        for line in lines:
            points.append(line[:2])
            points.append(line[2:])
        # if vertical
        if 45 < orientation < 135:
            #sort by y
            points = sorted(points, key=lambda point: point[1])
        else:
            #sort by x
            points = sorted(points, key=lambda point: point[0])

        # return first and last point in sorted group
        # [[x,y],[x,y]]
        return [points[0], points[-1]]

    def process_lines(self, lines, img):
        '''Main function for lines from cv.HoughLinesP() output merging
        for OpenCV 3
        lines -- cv.HoughLinesP() output
        img -- binary image
        '''
        lines_x = []
        lines_y = []
        # for every line of cv.HoughLinesP()
        for line_i in [l[0] for l in lines]:
                orientation = self.get_orientation(line_i)
                # if vertical
                if 45 < orientation < 135:
                    lines_y.append(line_i)
                else:
                    lines_x.append(line_i)

        lines_y = sorted(lines_y, key=lambda line: line[1])
        lines_x = sorted(lines_x, key=lambda line: line[0])
        merged_lines_all = []

        # for each cluster in vertical and horizantal lines leave only one line
        for i in [lines_x, lines_y]:
                if len(i) > 0:
                    groups = self.merge_lines_pipeline_2(i)
                    merged_lines = []
                    for group in groups:
                        merged_lines.append(self.merge_lines_segments1(group))

                    merged_lines_all.extend(merged_lines)

        return merged_lines_all

The part with distance calculation could be changed to

def distance_to_line(self, point, line):
    """Get distance between point and line
    https://stackoverflow.com/questions/40970478/python-3-5-2-distance-from-a-point-to-a-line
    """
    px, py = point
    x1, y1, x2, y2 = line
    x_diff = x2 - x1
    y_diff = y2 - y1
    num = abs(y_diff * px - x_diff * py + x2 * y1 - y2 * x1)
    den = math.sqrt(y_diff**2 + x_diff**2)
    return num / den

def get_distance(self, a_line, b_line):
    """Get all possible distances between each dot of two lines and second line
    return the shortest
    """
    dist1 = self.distance_to_line(a_line[:2], b_line)
    dist2 = self.distance_to_line(a_line[2:], b_line)
    dist3 = self.distance_to_line(b_line[:2], a_line)
    dist4 = self.distance_to_line(b_line[2:], a_line)

    return min(dist1, dist2, dist3, dist4)

But you'll get slightly different lines at the end.

Answer 3

I have finally completed the pipeline:

1. fixed incorrect parameters (as were suggested by Dan)
2. developed my own 'merging line segments' algorithm. I had bad results when I implemented TAVARES and PADILHA algorithm (as were suggested by Andrew).
3. I have skipped Canny and got better results (as were suggested by Alexander)

Please find the code and results:

def get_lines(lines_in):
    if cv.__version__ < '3.0':
        return lines_in[0]
    return [l[0] for l in lines_in]


def process_lines(image_src):
    img = mpimg.imread(image_src)
    gray = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
    
    ret, thresh1 = cv.threshold(gray,127,255,cv.THRESH_BINARY)
    
    thresh1 = cv.bitwise_not(thresh1)
    
    edges = cv.Canny(thresh1, threshold1=50, threshold2=200, apertureSize = 3)

    lines = cv.HoughLinesP(thresh1, rho=1, theta=np.pi/180, threshold=50,
                            minLineLength=50, maxLineGap=30)

    # l[0] - line; l[1] - angle
    for line in get_lines(lines):
        leftx, boty, rightx, topy = line
        cv.line(img, (leftx, boty), (rightx,topy), (0,0,255), 6) 
        
    # merge lines
        
    #------------------
    # prepare
    _lines = []
    for _line in get_lines(lines):
        _lines.append([(_line[0], _line[1]),(_line[2], _line[3])])
        
    # sort
    _lines_x = []
    _lines_y = []
    for line_i in _lines:
        orientation_i = math.atan2((line_i[0][1]-line_i[1][1]),(line_i[0][0]-line_i[1][0]))
        if (abs(math.degrees(orientation_i)) > 45) and abs(math.degrees(orientation_i)) < (90+45):
            _lines_y.append(line_i)
        else:
            _lines_x.append(line_i)
            
    _lines_x = sorted(_lines_x, key=lambda _line: _line[0][0])
    _lines_y = sorted(_lines_y, key=lambda _line: _line[0][1])
        
    merged_lines_x = merge_lines_pipeline_2(_lines_x)
    merged_lines_y = merge_lines_pipeline_2(_lines_y)
    
    merged_lines_all = []
    merged_lines_all.extend(merged_lines_x)
    merged_lines_all.extend(merged_lines_y)
    print("process groups lines", len(_lines), len(merged_lines_all))
    img_merged_lines = mpimg.imread(image_src)
    for line in merged_lines_all:
        cv.line(img_merged_lines, (line[0][0], line[0][1]), (line[1][0],line[1][1]), (0,0,255), 6)

    
    cv.imwrite('prediction/lines_gray.jpg',gray)
    cv.imwrite('prediction/lines_thresh.jpg',thresh1)
    cv.imwrite('prediction/lines_edges.jpg',edges)
    cv.imwrite('prediction/lines_lines.jpg',img)
    cv.imwrite('prediction/merged_lines.jpg',img_merged_lines)
    
    return merged_lines_all

def merge_lines_pipeline_2(lines):
    super_lines_final = []
    super_lines = []
    min_distance_to_merge = 30
    min_angle_to_merge = 30
    
    for line in lines:
        create_new_group = True
        group_updated = False

        for group in super_lines:
            for line2 in group:
                if get_distance(line2, line) < min_distance_to_merge:
                    # check the angle between lines       
                    orientation_i = math.atan2((line[0][1]-line[1][1]),(line[0][0]-line[1][0]))
                    orientation_j = math.atan2((line2[0][1]-line2[1][1]),(line2[0][0]-line2[1][0]))

                    if int(abs(abs(math.degrees(orientation_i)) - abs(math.degrees(orientation_j)))) < min_angle_to_merge: 
                        #print("angles", orientation_i, orientation_j)
                        #print(int(abs(orientation_i - orientation_j)))
                        group.append(line)

                        create_new_group = False
                        group_updated = True
                        break
            
            if group_updated:
                break

        if (create_new_group):
            new_group = []
            new_group.append(line)

            for idx, line2 in enumerate(lines):
                # check the distance between lines
                if get_distance(line2, line) < min_distance_to_merge:
                    # check the angle between lines       
                    orientation_i = math.atan2((line[0][1]-line[1][1]),(line[0][0]-line[1][0]))
                    orientation_j = math.atan2((line2[0][1]-line2[1][1]),(line2[0][0]-line2[1][0]))

                    if int(abs(abs(math.degrees(orientation_i)) - abs(math.degrees(orientation_j)))) < min_angle_to_merge: 
                        #print("angles", orientation_i, orientation_j)
                        #print(int(abs(orientation_i - orientation_j)))

                        new_group.append(line2)

                        # remove line from lines list
                        #lines[idx] = False
            # append new group
            super_lines.append(new_group)
        
    
    for group in super_lines:
        super_lines_final.append(merge_lines_segments1(group))
    
    return super_lines_final

def merge_lines_segments1(lines, use_log=False):
    if(len(lines) == 1):
        return lines[0]
    
    line_i = lines[0]
    
    # orientation
    orientation_i = math.atan2((line_i[0][1]-line_i[1][1]),(line_i[0][0]-line_i[1][0]))
    
    points = []
    for line in lines:
        points.append(line[0])
        points.append(line[1])
        
    if (abs(math.degrees(orientation_i)) > 45) and abs(math.degrees(orientation_i)) < (90+45):
        
        #sort by y
        points = sorted(points, key=lambda point: point[1])
        
        if use_log:
            print("use y")
    else:
        
        #sort by x
        points = sorted(points, key=lambda point: point[0])
        
        if use_log:
            print("use x")
    
    return [points[0], points[len(points)-1]]

# https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.distance.cdist.html
# https://stackoverflow.com/questions/32702075/what-would-be-the-fastest-way-to-find-the-maximum-of-all-possible-distances-betw
def lines_close(line1, line2):
    dist1 = math.hypot(line1[0][0] - line2[0][0], line1[0][0] - line2[0][1])
    dist2 = math.hypot(line1[0][2] - line2[0][0], line1[0][3] - line2[0][1])
    dist3 = math.hypot(line1[0][0] - line2[0][2], line1[0][0] - line2[0][3])
    dist4 = math.hypot(line1[0][2] - line2[0][2], line1[0][3] - line2[0][3])
    
    if (min(dist1,dist2,dist3,dist4) < 100):
        return True
    else:
        return False
    
def lineMagnitude (x1, y1, x2, y2):
    lineMagnitude = math.sqrt(math.pow((x2 - x1), 2)+ math.pow((y2 - y1), 2))
    return lineMagnitude
 
#Calc minimum distance from a point and a line segment (i.e. consecutive vertices in a polyline).
# https://nodedangles.wordpress.com/2010/05/16/measuring-distance-from-a-point-to-a-line-segment/
# http://paulbourke.net/geometry/pointlineplane/
def DistancePointLine(px, py, x1, y1, x2, y2):
    #http://local.wasp.uwa.edu.au/~pbourke/geometry/pointline/source.vba
    LineMag = lineMagnitude(x1, y1, x2, y2)
 
    if LineMag < 0.00000001:
        DistancePointLine = 9999
        return DistancePointLine
 
    u1 = (((px - x1) * (x2 - x1)) + ((py - y1) * (y2 - y1)))
    u = u1 / (LineMag * LineMag)
 
    if (u < 0.00001) or (u > 1):
        #// closest point does not fall within the line segment, take the shorter distance
        #// to an endpoint
        ix = lineMagnitude(px, py, x1, y1)
        iy = lineMagnitude(px, py, x2, y2)
        if ix > iy:
            DistancePointLine = iy
        else:
            DistancePointLine = ix
    else:
        # Intersecting point is on the line, use the formula
        ix = x1 + u * (x2 - x1)
        iy = y1 + u * (y2 - y1)
        DistancePointLine = lineMagnitude(px, py, ix, iy)
 
    return DistancePointLine

def get_distance(line1, line2):
    dist1 = DistancePointLine(line1[0][0], line1[0][1], 
                              line2[0][0], line2[0][1], line2[1][0], line2[1][1])
    dist2 = DistancePointLine(line1[1][0], line1[1][1], 
                              line2[0][0], line2[0][1], line2[1][0], line2[1][1])
    dist3 = DistancePointLine(line2[0][0], line2[0][1], 
                              line1[0][0], line1[0][1], line1[1][0], line1[1][1])
    dist4 = DistancePointLine(line2[1][0], line2[1][1], 
                              line1[0][0], line1[0][1], line1[1][0], line1[1][1])
    
    
    return min(dist1,dist2,dist3,dist4)

There are still 572 lines. After my "merging line segments" we have only 89 lines

Answer 4

this is my attempt to solve this problem. I think it can work in various situation. This is the idea:

1. Convert line to polar coordinate form (r, alpha), like Hough Transform.
2. For each line in the list, compare it with the other line in the list.
3. If the 2 lines are close to each other (their r and alpha are close), they are the same line, but they might be overlap or not. If they are not overlap, treat them as separated lines. Alg to check if 2 lines are overlap: How to determine if two 2D line segments are overlap?

Pseudo running:

• line1 isn't in any line group yet, so create a new group with line1 coordinate (*)

• line1 is tested with line2....lineN

  line1 and line2 are not close, skip

  line1 and line3 are not close, skip ....

• line1 (AB) and line 7 (CD) are close. Ok, they are overlap? yes -> they are the same line, merge them into 1 line (AD for example). Update the line group (*) with this new coordinate. ....

• line1 and lineN are not close, skip and repeat the above process with line2 vs (line3....lineN), except lines which are already merged.

'''python

import numpy as np
def check_overlap(line1, line2):
    combination = np.array([line1,
                            line2,
                            [line1[0], line1[1], line2[0], line2[1]],
                            [line1[0], line1[1], line2[2], line2[3]],
                            [line1[2], line1[3], line2[0], line2[1]],
                            [line1[2], line1[3], line2[2], line2[3]]])
    distance = np.sqrt((combination[:,0] - combination[:,2])**2 + (combination[:,1] - combination[:,3])**2)
    max = np.amax(distance)
    overlap = distance[0] + distance[1] - max 
    endpoint = combination[np.argmax(distance)]
    return (overlap >= 0), endpoint #replace 0 with the value of distance between 2 collinear lines

def mergeLine(line_list):
    #convert (x1, y1, x2, y2) formm to (r, alpha) form
    A = line_list[:,1] - line_list[:,3]
    B = line_list[:,2] - line_list[:,0]
    C = line_list[:,0]*line_list[:,3] - line_list[:,2]*line_list[:,1]
    r = np.divide(np.abs(C), np.sqrt(A*A+B*B))
    alpha = (np.arctan2(-B,-A) + math.pi) % (2*math.pi) - math.pi
    r_alpha = np.column_stack((r, alpha))

    #prepare some variables to keep track of lines looping
    r_bin_size = 10 #maximum distance to treat 2 lines as one
    alpha_bin_size = 0.15 #maximum angle (radian) to treat 2 lines as one
    merged = np.zeros(len(r_alpha), dtype=np.uint8)
    line_group = np.empty((0,4), dtype=np.int32)
    group_count = 0

    for line_index in range(len(r_alpha)): 
        if merged[line_index] == 0: #if line hasn't been merged yet
            merged[line_index] = 1
            line_group = np.append(line_group, [line_list[line_index]], axis=0)
            for line_index2 in range(line_index+1,len(r_alpha)):
                if merged[line_index2] == 0:
                    #calculate the differences between 2 lines by r and alpha
                    dr = abs(r_alpha[line_index,0] - r_alpha[line_index2,0])
                    dalpha = abs(r_alpha[line_index,1] - r_alpha[line_index2,1])
                    if (dr<r_bin_size) and (dalpha<alpha_bin_size): #if they are close, they are the same line, so check if they are overlap
                        overlap, endpoints = check_overlap(line_group[group_count], line_list[line_index2])
                        if overlap:
                            line_group[group_count] = endpoints
                            merged[line_index2] = 1
            group_count += 1
    return line_group

'''

Answer 5

I wrote a simple algorithm that takes the center of gravity of two lines and projections to the predicted line when merging two lines. The algorithm returns None when merging thresholds exceed. Just convert lines returned by HoughLinesP to Line objects and call merge_lines(line1, line2) in LineMerger

import numpy as np
import math

class Line:
    def __init__(self, x1, y1, x2, y2):
        if x1 < x2:
            self.x1 = x1
            self.x2 = x2
            self.y1 = y1
            self.y2 = y2
        else:
            self.x1 = x2
            self.x2 = x1
            self.y1 = y2
            self.y2 = y1
        dx = self.x2 - self.x1
        if dx == 0:
            dx = 0.000000000000000001
        dy = self.y2 - self.y1
        m = dy / dx
        self.theta = np.arctan(m)
        if self.theta < 0:
            self.theta = 2 * np.pi + self.theta
        self.rho = np.abs(m * self.x1 - self.y1) / np.sqrt(1 + m * m)
        self.length = math.sqrt(dx * dx + dy * dy)

    def point1(self):
        return self.x1, self.y1

    def point2(self):
        return self.x2, self.y2


class LineMerger:
    def __init__(self):
        self.THETA_THRESHOLD = np.pi / 36
        self.MAX_DISTANCE = 5
        pass

    def merge_lines(self, line1, line2):
        theta_r = (line1.theta * line1.length + line2.theta * line2.length) / (line1.length + line2.length)
        if np.average([abs(theta_r - line1.theta), abs(theta_r - line2.theta)]) < self.THETA_THRESHOLD:
            # get gradients
            m = math.tan(theta_r)
            if m == 0:
                m = 0.00000000000001
            md = 1 / m
            # find center of gravity
            cx = ((line1.x1 + line1.x2) * line1.length + (line2.x1 + line2.x2) * line2.length) * 0.5 / (
                    line1.length + line2.length)
            cy = ((line1.y1 + line1.y2) * line1.length + (line2.y1 + line2.y2) * line2.length) * 0.5 / (
                    line1.length + line2.length)
            # find projection points
            # x, y, d
            r0 = self.get_projection_point(line1.point1(), (cx, cy), m, md)
            r1 = self.get_projection_point(line1.point2(), (cx, cy), m, md)
            r2 = self.get_projection_point(line2.point1(), (cx, cy), m, md)
            r3 = self.get_projection_point(line2.point2(), (cx, cy), m, md)
            l0 = self.get_distance(r0[:2], r2[:2])
            l1 = self.get_distance(r0[:2], r3[:2])
            l2 = self.get_distance(r1[:2], r2[:2])
            l3 = self.get_distance(r1[:2], r3[:2])
            l4 = line1.length
            l5 = line2.length
            max_len_index = np.argmax([l0, l1, l2, l3, l4, l5])
            max_len = np.max([l0, l1, l2, l3, l4, l5])
            if max_len - (line1.length + line2.length) < self.MAX_DISTANCE:
                point1 = None
                point2 = None
                if max_len_index == 0:
                    point1, point2 = r0[:2], r2[:2]
                elif max_len_index == 1:
                    point1, point2 = r0[:2], r3[:2]
                elif max_len_index == 2:
                    point1, point2 = r1[:2], r2[:2]
                elif max_len_index == 3:
                    point1, point2 = r1[:2], r3[:2]
                elif max_len_index == 4:
                    point1, point2 = r0[:2], r1[:2]
                elif max_len_index == 5:
                    point1, point2 = r2[:2], r3[:2]
                if point1 and point2:
                    x1, y1 = point1
                    x2, y2 = point2
                    return int(x1), int(y1), int(x2), int(y2)
        return None

    @staticmethod
    def get_projection_point(external_point, center_point, m, md):
        x0, y0 = external_point
        cx, cy = center_point
        c = cy - m * cx
        cd = y0 + md * x0
        mm1 = (m * m + 1)
        x = m * (cd - c) / mm1
        y = (m * m * cd + c) / mm1
        xd = x - x0
        yd = y - y0
        d = math.sqrt(xd * xd + yd * yd)
        return x, y, d

    @staticmethod
    def get_distance(point1, point2):
        x1, y1 = point1
        x2, y2 = point2
        dx = x1 - x2
        dy = y1 - y2
        return math.sqrt(dx * dx + dy * dy)

Convert to Line

def convert_lines(lines_p) -> [Line]:
    lines = []
    for line in lines_p:
        ln = line[0]
        lines.append(Line(ln[0], ln[1], ln[2], ln[3]))
    return lines