segment overlaps with start and end coordinates

[miac09]

Hi,

I have posted an example code to report overlaps between segments in two lists based on their start and end coordinates. The problem is that the while loop is breaking after 'True' and won't iterate through the lists. So, in the example lists it will only return (True, 0, (3015, 3701), 0, (3045, 3800)) and fails to also return other true overlaps in the list (e.g. (100,200) (150,300)).

I have tried introducing for loops at different points, using the itertools etc. but, can't seem to get around it- I know i'm probably missing something silly.

Anyway, thanks for any help!
M

lista = [(3015, 3701), (4011, 5890), (10,40), (150,300)]
listb = [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)]			

def overlap(lista, listb):
	a=0
	b=0
	found=False
	while a<len(lista) and b<len(listb):
		
		result=check(lista[a],listb[b])
		
		if result <0:
			a +=1
			continue
		if result > 0:
			b +=1
			continue
		found=True
		yield (found, a, lista[a],b,listb[b])
	yield found

def check ((astart, aend), (bstart, bend)):
	if aend <= bstart:
		return -1
	if bend <= astart:
		return 1
	return 0
			
for a,b in zip(lista,listb):
	result1=overlap(lista,listb)
	for res in result1:
		print res

[woooee]

At some point you will have to use a list to store multiple values. This is something along the lines of what I think you want.

lista = [(3015, 3701), (4011, 5890), (10,40), (150,300)]
listb = [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)]
     
def overlap(lista, listb):
    a=0
    b=0
    found_list = []
    while a<len(lista) and b<len(listb):
     
        result=check(lista[a],listb[b])
     
        if result <0:
            found_list.append((lista[a], listb[b]))
            a +=1
        elif result > 0:
            found_list.append((lista[a], listb[b]))
            b +=1
        else:     ## no result found in check()
            a += 1

    return found_list
     
def check ((astart, aend), (bstart, bend)):
    if aend <= bstart:
        return -1
    if bend <= astart:
        return 1
    return 0
     
result1=overlap(lista,listb)
for res in result1:
    print res

An alternate solution that compares every tuple in lista to every tuple in listb:

lista = [(3015, 3701), (4011, 5890), (10,40), (150,300)]
listb = [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)]
     
def overlap(lista, listb):
    found_a_less = []
    found_b_less = []
    for tup_a in lista:
        for tup_b in listb:     
            found_a_less, found_b_less=check(tup_a, tup_b, \
                                       found_a_less, found_b_less)

    return found_a_less, found_b_less
     
def check ((astart, aend), (bstart, bend), found_a, found_b):
    if aend <= bstart:
        found_a.append((aend, bstart))
    if bend <= astart:
        found_b.append((bend, astart))
    return found_a, found_b
     

result_a, result_b=overlap(lista,listb)
for res in result_a:
    print res
print "-"*50
for res in result_b:
    print res

[TrustyTony]

Worth to sort combined list first for iteration.

For small ranges of integers there would be possibility for set solution (with little work this could produce ranges instead of individual integers).

lista = [(3015, 3701), (4011, 5890), (10,40), (150,300)]
listb = [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)]

sets_a = set(value for a,b in lista for value in range(a,b+1))
sets_b = set(value for a,b in listb for value in range(a,b+1))

print(sets_a.intersection(sets_b))

both = sorted(lista+listb)
print('Both', both)
print([(c,b) for (a,b), (c,d) in zip(both, both[1:]) if c <= b])

[miac09]

Thanks all for the replies!

pyTony: I have a couple of questions regarding specific lines of your code (below):

There seems to be several print statements -

print(sets_a.intersection(sets_b)) #instead of printing the actual intersection coordinates as sets, can the original coordinates that overlap be printed using intersection ?

both = sorted(lista+listb)

print('Both', both) #What does this statement do ?

print([(c,b) for (a,b), (c,d) in zip(both, both[1:]) if c <= b]) #how is c and d defined ?

Thank you for the help!
M

[miac09]

Also, I should post what the result should look like for identifying coordinates that overlap :

input: lista = [(3015, 3701), (4011, 5890), (10,40), (150,300)]
listb = [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)]

output:
(3015, 3701), (3045, 3800)
(150,300), (100,200)
(10,40), (20,145)....etc....

[TrustyTony]

There is gap between your specification and my results by purpose as it is DaniWeb policy to help people to learn, which means letting people finish things by themself.

d goes one forward of c in both because it starts from both's second pair of ranges.

set to range can be converted by sorting the set and removing values inside ranges or by observing that start of range is value which has not one smaller value in set and end of range is value which has not one bigger number in set.

[woooee]

There is gap between your specification and my results by purpose as it is DaniWeb policy to help people to learn, which means letting people finish things by (themselves)

+1 So no one is posting complete code, take what has been posted onward.

The way you have described it: for these lists:

lista = [(3015, 3701), (4011, 5890), (10,40), (150,300)]
listb = [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)]

aend < bstart = 3701 < 4500
                5890 < None
                  40 < 3045, 100, 4500 
                 300 < 3045, 4500

And similarly for the bend < astart test.

This code has not been thoroughly tested.

lista = [(3015, 3701), (4011, 5890), (10,40), (150,300)]
listb = [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)]
   
def overlap(lista, listb):
    found_a_less = []
    for tup_a in lista:
        holding = [tup_a]
        for tup_b in listb:
            result=check(tup_a, tup_b)
            if result:
                holding.append(tup_b)

        found_a_less.append(holding)
    return found_a_less
     
def check ((astart, aend), (bstart, bend)):
    if aend <= bstart:
        return 1
#    if bend <= astart:
#        found_b.append((bend, astart))
    return 0
     
result=overlap(lista,listb)
for tup in result:
    print tup[0]
    for ctr in range(1, len(tup)):
        print "   ", tup[ctr]
    
result=overlap(listb,lista)
for tup in result:
    print tup[0]
    for ctr in range(1, len(tup)):
        print "   ", tup[ctr]

[miac09]

Thank you both for your helpful suggestions, although honestly when all of the code suggestions that you both made are run , the outputs are so all over the board that I think I'm more confused than when I first started!

I'll keep trying to sort it out on my own.
-M

[miac09]

Thank you for your additional post (above) - I was able to follow the logic of this suggestion much better and made some minor revisions to produce the desired output. Here's the final solution for other users.

Thanks again!
-M

lista = [(3015, 3701), (4011, 5890), (10,40), (150,300)]
listb = [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)]

def overlap(lista, listb):
found_a_less = []
for tup_a in lista:
holding = [tup_a]
for tup_b in listb:
result=check(tup_a, tup_b)
if result:
holding.append(tup_b)

found_a_less.append(holding)
return found_a_less

def check ((astart, aend), (bstart, bend)):
if (aend >= bstart) and (bend >= astart):
return 1
return 0

result=overlap(lista,listb)
for tup in result:
for ctr in range(1, len(tup)):
print tup[0], tup[ctr]

[TrustyTony]

Code must be between the beginning and end tags:

lista = [(3015, 3701), (4011, 5890), (10,40), (150,300)]
listb = [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)]
   
def overlap(lista, listb):
    found_a_less = []
    for tup_a in lista:
        holding = [tup_a]
        for tup_b in listb:
            result=check(tup_a, tup_b)
            if result:
                holding.append(tup_b)

        found_a_less.append(holding)
    return found_a_less
     
def check ((astart, aend), (bstart, bend)):
    if (aend >= bstart) and (bend >= astart):
        return 1
    return 0
     
result=overlap(lista,listb)
for tup in result:
    for ctr in range(1, len(tup)):
        print tup[0], tup[ctr]

[woooee]

And no one came up with a one line solution? We must be loosing our edge.

print [(a, b) for a in [(3015, 3701), (4011, 5890), (10,40), (150,300)] for b in [(3045, 3800), (1,2), (100,200), (4500,6000), (20,145)] if a[1] < b[0]]

[TrustyTony]

No we just, consentrate hiding the answer enough, to let OP to finish it himself, after we can give oneliners (better to save sorted lista+listb like my earlier code though):

print([((a,b), (c,d)) for (a,b), (c,d) in zip(sorted(lista+listb), sorted(lista+listb)[1:]) if b < c])