Task 008: Efficient intersections in 2D

Your task is to implement KD-tree data structure for efficient lookup in huge set of planar short line segments. Think hard about optimal tree building (set of line segments is static, you will be able to balance a tree easily) and about the ray-pass algorithm itself. Each ray-pass instance (query) is defined by: ray origin, ray direction and maximal number of intersections. Query results will be returned in form of line segment handles, intersections have to be sorted from the closest one to the farthest one (in the sense of ray direction).

Screenshot

Your algorithms should count various statistics: number of intersections, number of ray-box tests, etc. (see below). These numbers will be used in a result table comparing all the handed-in solutions.

It is recommended to test the algorithms on very large input sets (10⁷ lines or more). Your methods should be universal and robust!

WinForms-based application is ready to test efficiency and correctness of your kd-tree implementation by generating arbitrary number of short lines (deterministic but uneven distribution based on the Lorentz attractor, Paul Bourke page). Your tree-building code is invoked and after this building phase a required set of queries is performed. Results are optionally presented in graphical form, a simple hashcode-based fingerprint is computed for checking correctness of the results. Elapsed time and counter-based statistics are presented as well.

Statistics

Statistics which will be used to assess your solution:

number of atomic geometric tests "ray vs. line segment"
number of bounding-box tests "ray vs. box"
number of "heap-operations"; only operations with the O(log N) complexity are relevant
time spent in tree initialization (building phase) in seconds
total time of all ray-set queries (in seconds)

You are obliged to provide the first three statistics (see the GetStatistics() function)!

Base

You have to use the 008kdtree project from the grcis repository. A WinForms-based application is ready, user can modify size of input set, number of queries, random-seed, etc. Your implementation will be in the KDTree class, which you can find in the KDTree.cs source file. You are free to add any code/data stuctures to this specific file.

You have to implement this simple API:

BuildTree() - builds the new kd-tree from the scratch. Set of line-segments is passed in the segments argument
RayIntersect() - one ray vs. set query. Result set of size K (or smaller if there were not enough intersections) is returned in order from nearest to farthest one
GetStatistics() - retrieves accumulated statistics (ray vs. segment tests, ray vs. box tests, heap operations). Internal counters should be reset by this call

Ray vs. line-segment intersection: use provided function RaySegment2D().
Beware of duplicities: no duplicities in the result list will be tolerated! Watch for cases when one line segment falls into two consecutive tree cells.

Result examples

Data size	Random seed	Query size	HASH	INTERSECTIONS
1000000	7	100	E5DA3BAB292F8020	15138
1000000	12	200	D29B8AF580E85624	31162
5000000	144	200	9B155E1F59FE5FE	33306

Deadline

Due to: 20. 12. 2015

Credits

Base: 25 points (functional code, 100% correct intersections!), bonus points for very good efficiency

Project

Visual Studio project: 008kdtree.

Source file

Modify and submit the file: KDTree.cs

Results

Not yet.