Repository files navigation

SweepIntersectorLib is an implementation in pure Python of a sweep line algorithm for line-segment intersection, based on the algorithm described in the paper:

Mehlhorn, K., Näher, S.(1994).
Implementation of a sweep line algorithmfor the Straight Line Segment Intersection Problem (MPI-I-94-160).Saarbrücken: Max-Planck-Institut für Informatik.

Given a list of line segments in 2D, the algorithm finds all their pairwise intersections. In contrast to the classicalBentely-Ottmann algorithm, segments are allowed to be vertical, several segments may intersect in the same point, endpoints of segments my lie on other segments or may be common with their endpoints.

The demo uses thematplotlib library to visualize the results.Install it first:

pip install matplotlib

Then run the demo:

cd /path/to/sweep_intersectorpython demo.py

The whole work is done by the methodfindIntersections() of the classSweepIntersector:

intSector=SweepIntersector()isectDic=intSector.findIntersections(segList)

The segment listsegList is a Pythonlist of tuples(vs,ve), wherevs is the start point andve the end point of a segment. The pointsvs andve are given as tuples(x,y)? wherexandy? are their coordinates in the 2D plane.

The method returns a dictionaryisectDic with itemsseg:isects for all segments that had intersections. The key of the dictionary,seg, is a tuple(vs,ve) identical to the one in the input list and the valueisects is a list of all intersections of the segmentseg. These are given as tuples(x,y), where againx andy are their coordinates in the 2D plane. This list includes the start and end pointsvs andve and is ordered fromvs tove.

fromSweepIntersectorLib.SweepIntersectorimportSweepIntersectorsegList= []segList.append( ((1.0,1.0),(5.0,6.0)) )segList.append( ((1.0,4.0),(4.0,0.0)) )segList.append( ((1.5,5.0),(3.0,1.0)) )    ...isector=SweepIntersector()isectDic=isector.findIntersections(segList)forseg,isectsinisectDic.items():forpinisects[1:-1]:# here without end pointsplotInterxectionPoint(p)