Gegeven is een verzameling S van lijnsegmenten in het vlak; elk lijnsegment heeft twee eindpunten. We zoeken de verzameling van snijpunten tussen de paren segmenten uit S. Implementeer hiervoor een \(\Theta(n \log n)\) algoritme (zie referentie).
Schrijf een Python-functie intersections die als parameter de naam van een bestand krijgt, waarin elke regel de x- en y-coordinaat van een eindpunt gevolgd door x- en y-coordinaat van een tweede eindpunt van een segement bevat, gescheiden door spaties. De functie geeft een lijst van tuples terug, waarbij elk tuple de x- en y-coordinaat van een snijpunt tussen twee segmenten bevat; de lijst is gesorteerd op stijgende x-coordinaat. Coordinaten zijn gegeven als float-getallen met 8 cijfers na de komma.
In onderstaand voorbeeld veronderstellen we dat het bestand test30_1.txt1 zich in de huidige directory bevindt.
>>> intersections("test30_1.txt")
[(0.25530426,0.81170796), (0.31540268,0.83742842), (0.32459944,0.99205727),
(0.36804824,0.28717376), (0.80119944,0.93366464), (0.83226467,0.94716367),
(0.83381037,0.55089911), (0.84853407,0.53428252), (0.90289082,0.47293766)]