1

私は木のような構造をしています。一緒に接続してツリーを構成するいくつかの線を取得できます。線は始点と終点で構成されています。XML 形式のツリーからのサンプル データを次に示します。

<Skeleton>
   <Line StartX="384" StartY="135"  EndX="385" EndY="129"  /> 
   <Line StartX="384" StartY="137"  EndX="384" EndY="135"  /> 
   <Line StartX="384" StartY="138"  EndX="384" EndY="137"  /> 
   <Line StartX="384" StartY="139"  EndX="384" EndY="138"  /> 
   <Line StartX="383" StartY="144"  EndX="384" EndY="139"  /> 
   <Line StartX="383" StartY="147"  EndX="383" EndY="144"  /> 
    ...
</Skeleton>

ツリーのグラフィカルな表現は次のとおりです。

ここに画像の説明を入力

私がする必要があるのは、画像に示されているように、このツリーのリーフとジャンクションを抽出することです: ここに画像の説明を入力

このタスクを実行するための複雑さと時間に関して最適化されたアルゴリズムを見つけたいです。

4

1 に答える 1

3

  1. データから数学的グラフを生成します (座標は頂点のラベルであり、lineデータのそれぞれがグラフのエッジになります)。

  2. root vertexツリーの を定義します。

  3. リーフはすべての頂点であり、root vertex1 つのエッジのみに接続されています。

  4. ジャンクションは、少なくとも 3 つのエッジに接続されているすべての頂点です (この例では)。
于 2013-08-06T09:17:13.770 に答える