Angenommen, ich habe n Liniensegmente in der allgemeinen Position. Wie kann ich schnell für jedes meiner n Segmente bestimmen, wie viele der anderen n-1 es schneidet?
Ich kann das naiv in O (n 2 ) Zeit machen. Ich kann alle Schnittpunkte mit einem ziemlich einfachen Sweepline-Algorithmus (Bentley-Ottmann) in der Zeit O ((n + k) log n) finden, wobei k die Anzahl solcher Schnittpunkte ist, und dann die Schnittpunkte, die ich gefunden habe, zu einem Haufen zusammenfassen zählt.
Ich muss die Kreuzungen jedoch nicht finden ; Ich möchte nur wissen, wie viele es sind. Ich sehe nicht, wie man den Sweep-Line-Algorithmus ändert, um schneller zu sein, da er für jeden Schnittpunkt zwei Dinge in einem Baum neu anordnen muss, und ich kann mir keine anderen Techniken vorstellen, die nicht an demselben Problem leiden / p>
Ich bin auch daran interessiert, zu zählen, wie viele totale Kreuzungen es gibt.
Es fällt mir schwer zu glauben, dass Sie Bentley Ottman im allgemeinen Fall besser können. Sie können die Berechnung ein wenig vereinfachen, wenn es Ihnen egal ist, wo sich die Liniensegmente schneiden, aber ich sehe nicht, wie Sie Kreuzungen zählen könnten, ohne sie zu finden.
Im Wesentlichen ist Bentley Ottman eine Möglichkeit, den Suchraum für Kreuzungen zu vereinfachen. Es gibt andere Möglichkeiten, die für bestimmte Anordnungen von Liniensegmenten funktionieren könnten, aber wenn es keine vorhersagbare geometrische Beziehung zwischen Ihren Segmenten gibt, werden Sie nicht in der Lage sein, zuerst eine clevere Methode zum Finden von Kandidatenschnittstellen in Kombination mit einem zu verwenden individuelle Überprüfung jedes Kandidaten.
Sofern Ihre Problemdomäne nicht über bestimmte Funktionen verfügt, die eine nutzbare Unterstruktur bieten könnten, würde ich meinen, dass Sie Bentley Ottman (oder einen ähnlichen umfassenden Algorithmus) für die parallele Ausführung am besten anpassen sollten. (Das Zuschneiden der Liniensegmente in Bänder ist einfach. Das Herausfinden einer optimalen Menge von Bändern wäre ebenfalls interessant.) Natürlich ist das eher eine praktische als eine akademische Übung; der parallele Algorithmus könnte am Ende mehr Arbeit machen; Es nutzt nur Hardware, um die Arbeit in (einem konstanten Faktor) weniger Zeit zu erledigen.
Tags und Links algorithm language-agnostic geometry computational-geometry