Discussion :

[Benoit_T]

Bonjour à tous,


Je dispose de deux listes triées d'intervalles entiers. Je désire obtenir la liste des intervalles résultant de l'intersection des intervalles des deux listes.

Par exemple, soit les listes A et B:

A = {[0..2], [3..7]}
B = {[1..2], [4..5], [7..8]}

Je cherche à obtenir l'intersection C de A et B dont le résultat serait:

C = {[1..2], [4..5], [7..7]}.

Le problème est que je ne voit pas comment effectuer cette intersection avec une complexité satisfaisante.

J'ai effectué quelques recherches infructueuses sur internet, toute suggestion sera donc la bienvenue.

Cordialement,
Benoît.

[Zavonen]

Code Python :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
A=[(0,2),(3,7)]
B=[(1,2),(4,5),(7,8)]
 
def intersection(I,J):
    """ intersection de deux intervalles"""
    a=max(I[0],J[0])
    b=min(I[1],J[1])
    if a<=b:
        return (a,b)
    else:
        return None
 
def Possibles(I):
    """Intervalles de B pouvant éventuellement avoir une intersection non vide avec I (intervalle de A)"""
    return [J for J in B if (not (J[1]<I[0]))and not(J[0]>J[1])]
 
def Trace(I):
    """Trace de I intervalle de A sur les intervalles de B"""
    return [intersection(I,J) for J in Possibles(I)]
 
def AinterB():
    """La suite cherchée"""
    R=[]
    for I in A:
        R+=Trace(I)
    return [X for X in R if X!=None]
 
if __name__ == "__main__":
    print AinterB()
 
"""résultat:[(1, 2), (4, 5), (7, 7)]"""

[Nemerle]

autre idée:

- tu définis un ensemble de paires (x1,ab1)...(xn,abn) à partir de toutes les extrémités de tes segments de A & B, en posant ab=A ou B en fonction de la classe du segment.
- tu tries par ordre croissant, et tu parcours alors ton ensemble séquentiellement. A partir de (x(i-1),ab(i-1)), (xi,abi),(x(i+1),ab(i+1)) tu sauras quoi faire.



Ca t'évite ainsi de déterminer toutes les paires d'intersection de segments.