Fortune のアルゴリズムにおけるブレークポイントの収束

StackOverflow https://stackoverflow.com//questions/9612065

質問

ボロノイ図を計算するためにフォーチュンのスイープライン アルゴリズムを実装しています。私の主な参考文献は「計算幾何学:de Berg et al. の「アルゴリズムとアプリケーション」では、このトピックに関する内容は非常に明確ですが、私自身が理解するのに苦労していたいくつかの小さいながらも重要な詳細が省略されています。ヘルプを求めて Web を検索しましたが、他の Web サイトでは教科書よりもさらに高度な概要が提供されているか、書籍で提供されているのとまったく同じ疑似コードが提供されています。

今後のサークル イベントを検出するには、ビーチ ライン上の 3 つの円弧によって決定される 1 組のブレークポイントが収束するか発散するかを判断する方法が必要です。決定を下すには、Fortune のアルゴリズムが進行するにつれてブレークポイントがトレースするボロノイ セルのエッジの形状に関する知識が必要になるようです。たとえば、ブレークポイントによってトレースされたエッジの傾きを見つけることができれば、ブレークポイントによって形成された 2 本の線とそれぞれの傾きが交差する場所を計算し、その結果に基づいてそれらが収束するかどうかを判断できます。しかし、斜面に関する情報を取得する方法がわかりません。ブレークポイントの現在の位置だけがわかります。

作業する必要がある唯一の情報は、3 つのサイトの X、Y 位置とスイープラインの現在の Y 座標です (水平スイープラインを使用しています)。

実は、収束を判断するためのアイデアが 1 つあります。2 つのサイトが与えられた場合、それらが定義するビーチラインの 2 つのセクション間のブレークポイントは、スイープ ラインの現在の位置によってのみ支配されます。2 つのブレークポイントの位置を記録し、スイープ ラインを一時的に少し進めて、新しい位置を記録することを考えました。通常のボロノイ図のエッジは曲がらないため、新しいブレークポイントのペア間の距離が古いペア間の距離よりも小さい場合、ブレークポイントは収束します。そうでなければ、それらは発散します。しかし、これは危険 (常に機能するかどうかはわかりません) であり、醜いように思えます。きっともっと良い方法があるはずです。

あらゆるアイデアを歓迎します。特に擬似コード (可能であれば C# のような構文で) を歓迎します。また、ボロノイ図を取得するために使用できる計算幾何学ライブラリがあることは知っていますが、これは個人的な学習課題であるため、アルゴリズムのすべての部分を自分で実装したいと考えています。

役に立ちましたか？

解決

ドレイクさん、ようこそ。私は、ブレークポイントがスイープライン位置の「架空の」増分で円の中心に物理的に収束するかどうかをチェックすることでこれを実装しました。これは実際には少し複雑になります。場合によっては、円の中心がスイープラインの位置にほぼ、または正確に一致する可能性があるため、スイープラインの増分は、現在のスイープラインの位置と、推奨どおりに生成された円の中心との差に比例する必要があります。

言う：

1. currentSweeplineY = 1.0f; circleCenterY = 0.5f (そして私たちは下に向かって移動しています。つまりy 方向に減少します)。

2. Set sweepYIncrement = (circleCenterY - currentSweepLineY) / 10.0f (10.0f の除数は任意に選択されます)。

3. Check new breakpoint positions at new sweepline position.

4. Check distance to circle center.

5. If both distances are less than current distances, the breakpoints converge.

ブレークポイントの位置を複数回計算する必要があるため、おそらく非常にコストがかかることは承知していますが、考えられるすべてのケースに対応できると確信しています。

とにかく、アルゴリズムの他の場所で浮動小数点精度エラーに関する深刻な問題が見つかりました。最初に思ったほど単純ではありません。

他のヒント

だからこれはむしろ恥ずかしいことですが、問題について眠っている後、答えは明白だと思われます。私はこれを書いています。将来の学生が私と同じ質問をしているのを手伝ってくれるためにこれを書いています。

2つのサイト間のボロノイエッジは、サイトを接続する（想像上の）ラインセグメントを垂直に二分割します。接続線セグメントの勾配の垂直を取ってから、2つのエッジでライン交差点テストを実行することによって、エッジの勾配を導き出すことができますが、さらに簡単な方法があります。

3つのサイトがある限り、 Collinear 、次に、サイト間のセグメントを垂直に二区分するエッジもまた、そのエッジが3つのサイトすべてを含む円にも接しています。したがって、Voronoiサイトのトリプルによって定義されたブレークポイントは、3つのサイトによって定義された円の中心が Middle サイトの前に収束します。ここで、「前面」と「後ろ」は座標に依存します。選択したシステムとスイープアライメント。

私の場合は、最小Yから最大Yへ移動している水平方向のスイープスリーンを持っているので、円の中心のY座標が中央のサイトのY座標より大きい場合にはブレークポイントが収束します。そうでなければ発散します。

編集：Kristian D'Amatoは、上記のアルゴリズムがいくつかの収束性の場合を見逃していることを正しく指摘しています。私が使用して終了した最終アルゴリズムは以下のとおりです。もちろん、100％が正しいと確信していませんが、それを試したすべてのケースで働いているようです。 

Given left, middle, right sites
    if they are collinear, return false
    center = ComputeCircleCenterDefinedBy3Points(left, middle, right)
    return IsRightOfLine(left, middle, center) && IsRightOfLine(middle, right, center)

IsRightOfLine(start, end, point)
    ((end.X - start.X) * (point.Y - start.Y) - (end.Y - start.Y) * (point.X - start.X)) <= 0
.

サイトが円の中心を中心に時計回りに並べられた場合、アークは収束しています。円の中心を中心に反時計回りに注文した場合、アークは発散しています。（または実装に応じて）（またはその逆）。CWまたはCCWのテストは、円の中心を見つけるために使用するコードから落ちます。

ここでC＃のC＃は、点A、B、C：の円周方向Dを計算するためのコードコードです。 

        Vector2 ba = b - a;
        Vector2 ca = c - a;     
        float baLength = (ba.x * ba.x) + (ba.y * ba.y);
        float caLength = (ca.x * ca.x) + (ca.y * ca.y); 
        float denominator = 2f * (ba.x * ca.y - ba.y * ca.x);   
        if (denominator <= 0f ) { // Equals 0 for colinear points.  Less than zero if points are ccw and arc is diverging.
            return false;  // Don't use this circle event!
        };
        d.x = a.x + (ca.y * baLength - ba.y * caLength) / denominator ;
        d.y = a.y + (ba.x * caLength - ca.x * baLength) / denominator ;
.

ライセンス： CC-BY-SA と 帰属
所属していません StackOverflow
scroll top