intersection de deux ensembles d'intervalles

Version imprimable

09/07/2010, 14h33
Benoit_T

intersection de deux ensembles d'intervalles

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.

Code:

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)]"""

13/07/2010, 10h09
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.