ref:https://github.com/johnhany/SegmentsIntersection/
http://johnhany.net/2013/11/sweep-algorithm-for-segments-intersection/
license: contact johnhany@163.com
/* * Author: John Hany * Website: http://johnhany.net/ * Source code updates: https://github.com/johnhany/SegmentsIntersection * If you have any advice, you could contact me at: johnhany@163.com * * ------------Sweep Algorithm For Segments Intersection------------- * * The program updates two structures during the whole algorithm: * -Link list "POrder{}" saves all the points and intersection points (ordered list) * -Binary tree "tree{}" saves the event points being scanned at present (scan tree) * * The ordered list is arranged by Y axis decreasingly. * The program scans from start of the list "POrder" to the end. * When detecting a new intersection point, it will be inserted into the ordered list. * For the lines that are being scanned, their upper points, lower points * parameters(k and b) and intersection points are saved in the "POrder" node. * * The scan tree is arranged by X axis increasingly. * For each node in scan tree, (scan->left->id->x) < (scan->id->x) < (scan->right->id->x). * The "id" value in "tree" node is a pointer towards certain node in ordered list. * * ------------------------------------------------------------------- * * When scanning the "POrder" list, the program does such three things: * * (1).For an upper point, add a new "scan" node in the scan tree, pointing to the point. * Get its left and right neighbors in the scan tree. * Then check intersection between it and its two neighbors. * If there is any intersection point, add it into the ordered list, * and they will be processed in the future. * * (2).For a lower point, search for its upper point in the scan tree and * get left and right neighbors of the upper point. * Delete the upper point from the tree, then check intersection between the two neighbors. * If there is any intersection point, add it into the ordered list to be processed in the future. * * (3).For an intersection point, get the left neighbor of the left line and * right neighbor of the right line. * Switch the order of two lines of the same intersection point in the scan tree. * Check intersection between its left line(the new right line) and its right neighbor * Check intersection between its right line(the new left line) and its left neighbor. * */
