|
|
last time, I try to get good use of the LC_SplinePoints for generic curves. Intersection performance was poor.
the reason is due to the brute force algorithm of intersection between two splines, for example, two splines each with 1000 segments, the brute force intersection algorithm searches for intersections between any segment pairs, i.e. 1000x1000 = 1 million times of quadratic-quadratic equation solving, while most of them are separated by bounding boxes of segments.
There are standard sweep-line based algorithms to detect bounding box intersections:
1, keep bounding box xmin, xmax in a priority queue;
2, keep a BST of y-intervals;
3, upon an xmin event, find intersection of y-intervals with the current bounding box;
perform quadratic-quadratic intersection
insert the current y-interval to BST;
4, upon an xmax event, delete the y-interval.
The bounding box intersection will be performed at O(N lg N), but bounding box intersection is much faster than quadratic-quadratic.
for quadratic-quadratic equation solver, a robust algorithm is found in the kde kig:
1, determine degenerated quadratic;
2, if none, use linear combination to create a degenerated quadratic (by solving a cubic equation);
3, separate the degenerated quadratic into two lines
4, find intersection : line - quadratic
|
Locked
