Wie erstelle ich eine Kreuzungsfunktion?

Question

Ich mache ein 1-dimensionales Intervall, wo ich prüfen muss, ob Selbst ein anderes Objekt schneidet. Hier

ist das, was ich bisher:

def __init__(self, lbound, rbound): 
    """ 
    Constructs a new interval given its lower and upper bounds. 
    """ 

    self._lbound = lbound 
    self._rbound = rbound 

Und das ist meine Funktion:

def intersects(self, other): 
    """ 
    Returns True if self intersects other and False othewise. 
    """ 

    s1 = set([self._lbound, self._rbound]) 
    s2 = set([other._lbound, other._rbound]) 
    if s1.intersection(s2) and s2.intersection(s1): 
     return True 

Das Problem ist, diese Funktion nur die halbe Antwort gibt ich will, was ein besseren Weg zu überprüfen, ob Selbst andere schneidet?

Answer 1

Sie wollen wahrscheinlich etwas Ähnliches statt:

def intersects(self, other): 
    return (other._lbound < self._lbound < other._rbound or 
      other._lbound < self._rbound < other._rbound or 
      self._lbound < other._lbound < self._rbound or 
      self._lbound < other._rbound < self._rbound) 

Answer 2

Sie können sicherlich dieses Prädikat mit Ungleichheiten implementieren. Der Nachteil dieses Ansatzes ist die schlechte Lesbarkeit und die hohe Wahrscheinlichkeit, einen Fehler zu machen. Ich empfehle Ihnen, dieses Problem in zwei Unterprobleme zu zerlegen:

1. Schneiden von zwei Intervallen.
2. Prüfen, ob ein Intervall leer ist.

Ich nehme an, dass Sie öffnen Intervalle verwenden. Wenn nicht, passen Sie den Code entsprechend an.

Constructing den Code

Lassen Sie uns zunächst für die Darstellung von Intervallen eine Klasse:

class Interval(object): 
    def __init__(self, lhs, rhs): 
     self.lhs = lhs 
     self.rhs = rhs 

Ein leeres Intervall als ein mit lhs >= rhs vertreten sein (was auch Sinn vom mathematischen Standpunkt aus macht) . Lassen Sie uns ein Prädikat hinzufügen, die überprüft, ob ein Intervall leer ist:

def is_empty(self): 
     return self.lhs >= self.rhs 

Lassen Sie uns unsere Aufmerksamkeit auf Kreuzungen drehen. Ein Schnittpunkt von zwei Intervallen ist ein Intervall (möglicherweise leer). Die linken und rechten Endpunkte können mit min und max wie folgt berechnet werden:

def intersect(self, other): 
     return Interval(max([self.lhs, other.lhs]), min([self.rhs, other.rhs])) 

Als letzten Schritt wollen wir __repr__ so hinzufügen, dass wir das Intervall der Lage zu print und sehen seine Endpunkte:

def __repr__(self): 
     return 'Interval(%r, %r)' % (self.lhs, self.rhs) 

Überprüfung für nicht leere Kreuzungen

Der Vorgang, den Sie ausführen sind versuchen, kann wie folgt ausgedrückt werden:

a.intersect(b).is_empty() 

wobei a und b zwei Interval s sind.

Full Source

Ich schließe die volle Quelle für Ihre Bequemlichkeit.

class Interval(object): 
    def __init__(self, lhs, rhs): 
     self.lhs = lhs 
     self.rhs = rhs 

    def is_empty(self): 
     return self.lhs >= self.rhs 

    def intersect(self, other): 
     return Interval(max([self.lhs, other.lhs]), min([self.rhs, other.rhs])) 

    def __repr__(self): 
     return 'Interval(%r, %r)' % (self.lhs, self.rhs)