Das Verständnis des Bentley-Ottman Algorithmus

Question

Dies ist der Code:

Initialize event queue EQ = all segment endpoints; 
    Sort EQ by increasing x and y; 
    Initialize sweep line SL to be empty; 
    Initialize output intersection list IL to be empty; 

    While (EQ is nonempty) { 
     Let E = the next event from EQ; 
     If (E is a left endpoint) { 
      Let segE = E's segment; 
      Add segE to SL; 
      Let segA = the segment Above segE in SL; 
      Let segB = the segment Below segE in SL; 
      If (I = Intersect(segE with segA) exists) 
       Insert I into EQ; 
      If (I = Intersect(segE with segB) exists) 
       Insert I into EQ; 
     } 
     Else If (E is a right endpoint) { 
      Let segE = E's segment; 
      Let segA = the segment Above segE in SL; 
      Let segB = the segment Below segE in SL; 
      Delete segE from SL; 
      If (I = Intersect(segA with segB) exists) 
       If (I is not in EQ already) 
        Insert I into EQ; 
     } 
     Else { // E is an intersection event 
      Add E’s intersect point to the output list IL; 
      Let segE1 above segE2 be E's intersecting segments in SL; 
      Swap their positions so that segE2 is now above segE1; 
      Let segA = the segment above segE2 in SL; 
      Let segB = the segment below segE1 in SL; 
      If (I = Intersect(segE2 with segA) exists) 
       If (I is not in EQ already) 
        Insert I into EQ; 
      If (I = Intersect(segE1 with segB) exists) 
       If (I is not in EQ already) 
        Insert I into EQ; 
     } 
     remove E from EQ; 
    } 
    return IL; 
} 

ich ein paar Fragen zum Beispiel im linken Endpunkt Fall habe was ist, wenn a oder b tut existieren? Wenn ein Existieren und sein sollte, sollten wir das zweite nicht oder nicht überprüfen?

SL ist in den ersten Iterationen meist leer, daher werden die meisten Punkte am Anfang ohne Verwendung entfernt. Worauf kommt es an?

Answer 1

Wenn a und b nicht existieren, dann ist natürlich keine Kreuzung mit ihnen möglich. Wenn nur einer existiert, kann nur dieser auf Schnittpunkt überprüft werden.

Ich bin mir nicht sicher, was Sie meinen, wenn Punkte "ohne Verwendung" entfernt werden. Alle Ereignisse in der Ereigniswarteschlange sind wichtig, entweder weil es sich um bevorstehende Überschneidungen handelt, oder weil sie potenzielle bevorstehende Überschneidungen einrichten, indem sie die Überstreichungslinie auf dem neuesten Stand halten.

Endlich ist es Bentley-Ottmann, nicht Bentley-Ottoman.