Merging vertical lines that coincide

I have a list of lines and I need to merge those who are similar (for example my machine vision script will return 3 small vertical line instead of one long vertical line).

I came up with this.
I'm not pleased with it, what do you think?

```
import math

class Point():
def __init__(self, x, y):
"""
Represent a point in a plan
- x : x (on the width axis, 0 is at the left)
- y : y (on the height axis, 0 is on the top)
"""
self.x = int(x)
self.y = int(y)

def __str__(self):
return '(Point : x=%s, y=%s)' %(self.x, self.y)

class Line():
def __init__(self, a, b):
"""
Represent a plan
- a : viewanalyser.Point, start of the line
- b : viewanalyser.Point, end of the line
"""
self.a = a
self.b = b

def __str__(self):
return 'Line with points : a=%s, b=%s' %(self.a, self.b)

def find_vLinesToMerge(vLines, tolerance):

"""
Find vertical lines that can be merged (meaning they have the same x,
there is a tolerance, for ecample if tolerance = 20 then 2 vertical lines
spaced for less than 20 pixel on the x absciss are considered to be mergeable
-vLines : list(Lines) : MUST BE VERTICAL LINES ONLY
-tolerance : (int) : tolerance for detecting similar vertical lines
"""

toMerge = []
alreadyFlaggedForMerge = set()
for i in range(len(vLines)):
if i in alreadyFlaggedForMerge:
continue
toMergeInThisRun = set()
for j, line in enumerate(vLines):
if math.fabs(vLines[i].a.x - line.a.x)<tolerance:
alreadyFlaggedForMerge.add(i)
alreadyFlaggedForMerge.add(j)
toMergeInThisRun.add(i)
toMergeInThisRun.add(j)
toMerge.append(toMergeInThisRun)

return toMerge

vertical_lines = []
vertical_lines.append(Line(Point(1, 7), Point(1, 13)))#---------------------a / index[0]
verti

This codes looks pretty good. I have refactored your code to better use some of the nice things that Python provides, and to help illustrate the following points. Refactored code is below. Changes made include:

1. pep8:

I changed the code to more closely conform to pep8. This is important when sharing code as the consistent style makes it much easier for other programmers to read your code. There are various tools available to assist in making the code pep8 compliant. I use PyCharm which will show pep8 violations right in the editor.

1. Converted Point and Line into namedtuples:

Converting these objects to named tuples makes them immutable. This allows them to be keys in dicts and too be added to sets. This has many benefits.

1. Iterate on list of lines, instead of index:

Since the lines are now immutable, they can be added directly to a set, and the index of the line in the list is no longer needed for this.

1. Iterate inner loop only on unconsidered pairs:

Start the inner loop from the current line only, which removes about half of the comparisons.

1. Turn the test data into a structure that can test the results:

In the test data structure, each line is a key to dict which references the expected output group for that line segment. This works because the line is now immutable.

1. Test the results using an assert, instead of print:

This allows the programmer to simply look for pass/fail status and not need to examine print output to verify the code is working.

1. (An update from Comments) Pull line_v1 out of inner loop:

Seeded to_merge_in_this_run = {v_line1} with single element set literal instead instead of an empty set. This allowed the removal of already_flagged_for_merge.add(v_line1) as unneeded.

Code:

import math
from collections import namedtuple

Point = namedtuple('Point', 'x y')
Line = namedtuple('Line', 'a b')

def find_v_lines_to_merge(v_lines, tolerance):

    """
    Find vertical lines that can be merged (meaning they have the same x,
    there is a tolerance, for example if tolerance = 20 then 2 vertical
    lines spaced for less than 20 pixel on the x axis are considered to
    be merge-able.
        -vLines : list(Lines) : MUST BE VERTICAL LINES ONLY
        -tolerance : (int) : tolerance for detecting similar vertical lines
    """

    to_merge = []
    already_flagged_for_merge = set()
    for i, v_line1 in enumerate(v_lines):
        if v_line1 not in already_flagged_for_merge:
            to_merge_in_this_run = {v_line1}
            for v_line2 in v_lines[i+1:]:
                if math.fabs(v_line1.a.x - v_line2.a.x) < tolerance:
                    already_flagged_for_merge.add(v_line2)
                    to_merge_in_this_run.add(v_line2)
            to_merge.append(to_merge_in_this_run)

    return to_merge

Test Harness:

test_data = dict((
    (Line(Point(1, 7), Point(1, 13)), 'a'),
    (Line(Point(1, 14), Point(1, 27)), 'a'),
    (Line(Point(1, 28), Point(1, 35)), 'a'),
    (Line(Point(50, 1), Point(50, 5)), 'b'),
    (Line(Point(80, 7), Point(80, 13)), 'c'),
    (Line(Point(1, 36), Point(1, 55)), 'a'),
    (Line(Point(50, 6), Point(50, 13)), 'b'),
    (Line(Point(100, 7), Point(100, 13)), 'd'),
    (Line(Point(100, 14), Point(100, 200)), 'd'),
    (Line(Point(100, 201), Point(100, 500)), 'd'),
    (Line(Point(80, 14), Point(80, 200)), 'c'),
    (Line(Point(1000, 7), Point(1000, 13)), 'e'),
))

# get the test data
test_data_list = test_data.keys()

# shuffle it to a random order
from random import shuffle
shuffle(test_data_list)

# merge the lines
merged_lines = find_v_lines_to_merge(test_data_list, 20)

# verify that the merged lines all match as expected
for merged_line in merged_lines:

    # get the set of line names for each segment in this merge
    line_names = set([test_data[segment] for segment in merged_line])

    # assert there is one and only one name
    assert len(line_names) == 1

StackExchange Code Review Q#154814, answer score: 2