9

ボロノイ図を計算するためにフォーチュンのスイープライン アルゴリズムを実装しています。私の主な参考文献は、de Berg 氏らによる「Computational Geometry: Algorithms and Applications」です。トピックのカバー範囲は非常に明確ですが、私が自分で解決するのに苦労しているいくつかの小さいながらも重要な詳細を見逃しています。Web でヘルプを検索しましたが、他の Web サイトでは、教科書よりもさらに高度な概要が提供されているか、本で提供されているのとまったく同じ擬似コードが提供されています。

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

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

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

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

4

3 に答える 3

7

ですから、これはかなり恥ずかしいことですが、この問題について熟考した後では、答えは明らかなように思えます。私はこれを書いて、将来私と同じ質問をする学生を助けることを願っています.

2 つのサイト間のボロノイ エッジは、サイトを結ぶ (仮想の) 線分を垂直に二等分します。接続線セグメントの勾配の垂線を取り、2 つのエッジで線交差テストを実行することで、エッジの勾配を導き出すことができますが、さらに簡単な方法があります。

3 つのサイトが同一線上にない限り、サイト間のセグメントを垂直に二等分するエッジは、3 つのサイトすべてを含むエッジを持つ円にも接します。したがって、ボロノイ サイトのトリプルによって定義されるブレークポイントは、3 つのサイトによって定義される円の中心が中央のサイトの前にある場合に収束します。「前」と「後ろ」は、選択した座標系とスイープラインの配置によって異なります。 .

私の場合、最小 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
于 2012-03-08T16:11:29.953 に答える
2

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

言う：

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.

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

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

于 2013-06-17T08:51:27.653 に答える
2

サイトが円の中心を中心に時計回りに並べられている場合、円弧は収束しています。それらが円の中心を中心に反時計回りに並べられている場合、円弧は発散しています。(またはその逆、実装によって異なります)。cw または ccw のテストは、円の中心を見つけるために使用するコードから外れています。

点 a、b、c の外心 d を計算するための C# コードのスニペットを次に示します。

        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 ;
于 2015-01-10T23:03:25.230 に答える