python remove rectangles from list in loop by distance

user_12615197 0
Viewed 100

I have an object that represents a rectangle in python that looks like this:

class cords:
    x_start = -1
    x_end = -1
    y_start = -1
    y_end = -1

    def __init__(self, x_start, x_end, y_start, y_end):
        self.x_start = x_start
        self.x_end = x_end
        self.y_start = y_start
        self.y_end = y_end

Now I have a list of cords named new_cords with values like this:

x_start: 508, x_end: 530, y_start: 843, y_end: 869
x_start: 508, x_end: 530, y_start: 843, y_end: 870
x_start: 401, x_end: 451, y_start: 582, y_end: 620
x_start: 467, x_end: 513, y_start: 583, y_end: 621
x_start: 466, x_end: 512, y_start: 634, y_end: 672
x_start: 533, x_end: 585, y_start: 534, y_end: 561
x_start: 528, x_end: 576, y_start: 583, y_end: 622

I want to remove from new_cords rectangles that are at distance of 3 away from each other to reduce similar rectangles.

I wrote this:

for c_out in new_cords:
    for c_in in new_cords:
        if abs(c_out.x_start - c_in.x_start) < 3 or abs(c_out.x_end - c_in.x_end) < 3 or abs(c_out.y_start - c_in.y_start) < 3 or abs(c_out.y_end - c_in.y_end) < 3:
            new_cords.remove(c_out)

But I get exceptions because it deletes values that don't exist and I don't get a correct list.

What is wrong with my algorithm?

EDIT: the algorithm should only delete one of them. E.g, A and B are close, so we should delete A(or B), but not both of them

list python
1 Answers

The task I understand is to remove some of the rectangles in a list so that the remaining rectangles are not too similar.

To maximize the number of rectangles left is actually a graph theory problem.

The following solution is not optimal, but can make the remaining number as large as possible:

def remove_similar(cord_list):
    is_similar = (
        lambda n1, n2: abs(n1.x_start - n2.x_start) < 3
        or abs(n1.x_end - n2.x_end) < 3
        or abs(n1.y_start - n2.y_start) < 3
        or abs(n1.y_end - n2.y_end) < 3
    )

    res = []
    while cord_list:
        c_in = cord_list.pop()
        cord_list = [n for n in cord_list if not is_similar(n, c_in)]
        res.append(c_in)
    return res

To make sure the code is valid, I run 1000 tests on list of 100 rectangles:

import numpy as np


def build_test(size):
    return [cords(*np.random.randint(0, 1000, 4).tolist()) for _ in range(size)]


def check(cord_list):
    assert not any(
        [n1 != n2 and too_close(n1, n2) for n1 in cord_list for n2 in cord_list]
    )
    return len(cord_list)


res_size_mean = 0
for _ in range(1000):
    new_cords = build_test(100)
    res = remove_similar(new_cords)
    res_size_mean += check(res) / 1000

print(res_size_mean)
# 53.591999999999736
user_128272860
Related