ボロノイ図を実装する簡単なアルゴリズムは何ですか?
特に疑似形式のアルゴリズムは見つかりませんでした。ボロノイ図アルゴリズム、チュートリアルなどのリンクをいくつか共有してください。
質問する
91221 次
14 に答える
33
ポイント セットの Delaunay 三角形分割を計算する簡単なアルゴリズムは、エッジの反転です。Delaunay 三角形分割はボロノイ図の双対グラフであるため、線形時間で三角形分割から図を作成できます。
残念ながら、フリッピング アプローチの最悪の場合の実行時間は O(n^2) です。Fortune のライン スイープなど、O(n log n) 時間かかるより優れたアルゴリズムが存在します。ただし、これを実装するのはやや難しいです。あなたが怠け者なら (私のように)、Delaunay 三角形分割の既存の実装を探し、それを使用してから、双対グラフを計算することをお勧めします。
一般に、このトピックに関する優れた本は、de Berg らによるComputational Geometryです。
于 2009-06-10T00:18:30.973 に答える
22
最も簡単ですか？これが強引なアプローチです。出力の各ピクセルについて、すべてのポイントを反復処理し、距離を計算し、最も近いものを使用します。可能な限り遅いですが、非常に単純です。パフォーマンスが重要でない場合は、それで十分です。私は自分自身で興味深い改良に取り組んできましたが、他の誰かが同じ（かなり明白な）アイデアを持っているかどうかをまだ探しています.
于 2012-06-01T10:19:33.047 に答える
10
ウィキペディアのページ ( http://en.wikipedia.org/wiki/Voronoi_diagram ) には、ボロノイ図を実装するためのアルゴリズムへのリンクを含むアルゴリズム セクションがあります。
于 2009-06-10T00:10:31.330 に答える
9
Stephan Fortune / Shane O'Sullivan による C および C++ の 2 次元グラフ用の無料のボロノイ実装があります。
VoronoiDiagramGenerator.cpp
VoronoiDiagramGenerator.h
多くの場所で見つけることができます。すなわちhttp://www.skynet.ie/~sos/masters/
于 2009-06-10T08:55:32.237 に答える
8
これは、quat-treeを使用し、インクリメンタルな構築を可能にするjavascriptの実装です。
于 2011-12-20T15:31:44.353 に答える
6
元の質問はボロノイの実装方法について尋ねていますが、この件に関する情報を検索しているときに次のような投稿を見つけたら、多くの時間を節約できたはずです。
ボロノイ図を実装するための「ほぼ正しい」C++ コードがインターネット上にたくさんあります。シード ポイントが非常に密になると、ほとんどの場合、障害が発生することはめったにありません。オンラインで見つけたコードは、時間を無駄にする前に、完成したプロジェクトで使用すると予想されるポイント数で広範囲にテストすることをお勧めします。
私がオンラインで見つけた最高の実装は、ここからリンクされたMapManager プログラムの一部でした: http://www.skynet.ie/~sos/mapviewer/voronoi.php 10^6 ポイントを注文します。腐敗がどのように忍び寄っているのかを正確に理解することはできませんでした.
昨夜、私はこれを見つけました: http://www.boost.org/doc/libs/1_53_0_beta1/libs/polygon/doc/voronoi_main.htm "Boost.Polygon Voronoi ライブラリ"。それは非常に有望に見えます。これには、精度と優れたパフォーマンスを証明するためのベンチマーク テストが付属しています。ライブラリには、適切なインターフェイスとドキュメントがあります。今までこのライブラリを見つけられなかったことに驚いたので、ここでそれについて書いています。（私は研究の早い段階でこの投稿を読みました。）
于 2014-02-18T10:45:07.220 に答える
6
これは可能な限り最速です。単純なボロノイですが、見栄えがします。スペースをグリッドに分割し、ランダムに配置された各グリッド セルにドットを配置し、グリッドに沿って移動し、3x3 セルをチェックして、隣接するセルとの関係を見つけます。
グラデーションなしの方が高速です。
最も簡単な 3D ボロノイは何かと尋ねるかもしれません。知ることは魅力的です。おそらく 3x3x3 セルとグラデーションのチェック。
http://www.iquilezles.org/www/articles/smoothvoronoi/smoothvoronoi.htm
float voronoi( in vec2 x )
{
ivec2 p = floor( x );
vec2 f = fract( x );
float res = 8.0;
for( int j=-1; j<=1; j++ )
for( int i=-1; i<=1; i++ )
{
ivec2 b = ivec2( i, j );
vec2 r = vec2( b ) - f + random2f( p + b );
float d = dot( r, r );
res = min( res, d );
}
return sqrt( res );
}
これはチェビシェフ距離と同じです。ここから random2f 2d float ノイズを使用できます。
https://www.shadertoy.com/view/Msl3DM
編集：これをCのようなコードに変換しました
これは少し前のことですが、何か知っている人のために、これはクールだと思います。
function rndng ( n: float ): float
{//random number -1, 1
var e = ( n *321.9)%1;
return (e*e*111.0)%2-1;
}
function voronoi( vtx: Vector3 )
{
var px = Mathf.Floor( vtx.x );
var pz = Mathf.Floor( vtx.z );
var fx = Mathf.Abs(vtx.x%1);
var fz = Mathf.Abs(vtx.z%1);
var res = 8.0;
for( var j=-1; j<=1; j++ )
for( var i=-1; i<=1; i++ )
{
var rx = i - fx + nz2d(px+i ,pz + j ) ;
var rz = j - fz + nz2d(px+i ,pz + j ) ;
var d = Vector2.Dot(Vector2(rx,rz),Vector2(rx,rz));
res = Mathf.Min( res, d );
}
return Mathf.Sqrt( res );
}
于 2014-02-11T09:45:12.630 に答える
5
実際には、 https://rosettacode.org/wiki/Voronoi_diagramで利用可能な 25 の異なる言語の実装があります。
Java の例:
import java.awt.Color;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.geom.Ellipse2D;
import java.awt.image.BufferedImage;
import java.io.File;
import java.io.IOException;
import java.util.Random;
import javax.imageio.ImageIO;
import javax.swing.JFrame;
public class Voronoi extends JFrame {
static double p = 3;
static BufferedImage I;
static int px[], py[], color[], cells = 100, size = 1000;
public Voronoi() {
super("Voronoi Diagram");
setBounds(0, 0, size, size);
setDefaultCloseOperation(EXIT_ON_CLOSE);
int n = 0;
Random rand = new Random();
I = new BufferedImage(size, size, BufferedImage.TYPE_INT_RGB);
px = new int[cells];
py = new int[cells];
color = new int[cells];
for (int i = 0; i < cells; i++) {
px[i] = rand.nextInt(size);
py[i] = rand.nextInt(size);
color[i] = rand.nextInt(16777215);
}
for (int x = 0; x < size; x++) {
for (int y = 0; y < size; y++) {
n = 0;
for (byte i = 0; i < cells; i++) {
if (distance(px[i], x, py[i], y) < distance(px[n], x, py[n], y)) {
n = i;
}
}
I.setRGB(x, y, color[n]);
}
}
Graphics2D g = I.createGraphics();
g.setColor(Color.BLACK);
for (int i = 0; i < cells; i++) {
g.fill(new Ellipse2D .Double(px[i] - 2.5, py[i] - 2.5, 5, 5));
}
try {
ImageIO.write(I, "png", new File("voronoi.png"));
} catch (IOException e) {
}
}
public void paint(Graphics g) {
g.drawImage(I, 0, 0, this);
}
static double distance(int x1, int x2, int y1, int y2) {
double d;
d = Math.sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)); // Euclidian
// d = Math.abs(x1 - x2) + Math.abs(y1 - y2); // Manhattan
// d = Math.pow(Math.pow(Math.abs(x1 - x2), p) + Math.pow(Math.abs(y1 - y2), p), (1 / p)); // Minkovski
return d;
}
public static void main(String[] args) {
new Voronoi().setVisible(true);
}
}
于 2017-02-18T21:48:24.770 に答える
1
点集合とドローネ三角形分割が与えられた場合、ボロノイ図を導出するにはどうすればよいですか?
于 2011-10-27T13:12:03.540 に答える
0
Fortune のアルゴリズム/スイープ ライン アルゴリズムに基づいて、Google コードでこの優れた C# ライブラリを見つけました
https://code.google.com/p/fortune-voronoi/
リストを作成するだけです。Vector は、2 つの数値 (座標) を float として渡すことで作成できます。次に、リストを Fortune.ComputeVoronoiGraph() に渡します。
これらのウィキペディアのページから、アルゴリズムの概念をもう少し理解できます。
http://en.wikipedia.org/wiki/Fortune%27s_algorithm
http://en.wikipedia.org/wiki/Sweep_line_algorithm
私が理解できなかったのは、部分的に無限のエッジの線を作成する方法です（座標ジオメトリについてはよくわかりません:-)）。知っている人がいたら、それも教えてください。
于 2015-06-03T15:01:40.767 に答える