Reputation: 9158
As show in the picture I have following structures to store set of closet "Curves" in a "Slice". A "Curve" consist of "Nodes" implemented as a doubly-linked-list.
Here is the psuedo code :
class Slice {
List<Curve*> curves;
}
class Curve {
int objectID;
Node *headNode;
}
class Node {
double x,
double y,
Node *next;
Node *previous
}
I render this stucture using QT paint methods and I want to select the node closest to the mouse point.
What I do is,
a).Get each "Curve" in the "Slice"
b).Go through all nodes in selected curve and calculate the distance from mouse-point to each point and compare.
My questions :
1) if we take number of curve is "c" and average nodes is "n" the algorithm complexity is O(n*c). Is this analysis correct?
2)Is there anyway to improve the algorithm ,make it more faster? Using Binary Tree,HashTable ..etc?
Upvotes: 4
Views: 140
Reputation: 24403
1) Yes your analysis is correct
2) You can get logarithmic complexity by using the nearest neighbor search algorithms.
The simplest of all is perhaps using the k-d tree
Upvotes: 3