4
図に示すように、「スライス」にクローゼット「曲線」のセットを格納するための構造は次のとおりです。 "曲線"は、二重リンクされたリストとして実装された "ノード"で構成されています。ここで
は擬似コードです：
class Slice {
List<Curve*> curves;
}
class Curve {
int objectID;
Node *headNode;
}
class Node {
double x,
double y,
Node *next;
Node *previous
}
私はQTペイントメソッドを使用して、このstuctureをレンダリングし、私は、マウスのポイントに最も近いノードを選択します。私は何をすべきか
、
A）に.get選択カーブ内のすべてのノードを介して「スライス」
B）.GOにおける各「曲線」とマウス点からの距離を計算し、それぞれにポイントして比較する。
私の質問：
1）私たちは、曲線の数は、 "C" 及び平均ノードで取る場合は、アルゴリズムの複雑さはO（N * C）である "N"。 この分析は正しいですか？
2）アルゴリズムを改善するためにとにかく、それをより速くしますか？バイナリツリー、HashTableなどを使用していますか？
ある一つの簡単なトリックは、各曲線の外接円の直径を追跡することです。カーブのマウスポイントまでの距離の任意のポイントがマウスポイントから直径の2倍以上離れている場合は、そのカーブ上の他のノードをスキップできます。 （これまでの最も近いポイントがマウスポイントから3単位で、境界円が10単位のカーブがマウスポイントから25単位の最初のポイントを持つ場合、そのカーブ上の他のノードは無視することができます）。 –