intersection edges 2d analyzer node

Created by: Durman

Addressed problem description

http://algorist.com/problems/Intersection_Detection.html

Solution description

Implementation of finding intersection between set of 2d edges algorithm described in this book based on swiping line approach.

Bentley–Ottmann algorithm.

I decided to code on pure python for simplicity without using any library. Actually in some cases it shows better performance than existing intersect edges node. Performance of this algorithm is (n+m)*log n where n is number of input points and m is number of intersection. So usage of this node is when there are not too much intersection.

AVL tree is being added to Sverchok with this node. Was taken from here. Useful data structure which can be used in many geometric algorithms.

AVL tree visualization

Another highlight of this node is that it can find intersection when point of one node lies on boundary of another edge or when two edges are overlapped each other.

Preflight checklist

• Code changes complete.
• Code documentation complete.
• Documentation for users complete (or not required, if user never sees these changes).
• Manual testing done.
• Unit-tests implemented.
• Ready for merge.