taramath: ComputationalGeometry.voronoi

Beschreibung

Die Funktion besitzt folgende Argumente:

A	Matrix (Liste von Punkten in der Ebene)

Es wird das Voronoi-Diagramm von berechnet. Genauer wird zunächst die Delaunay-Triangulierung von berechnet und davon der duale Graph bestimmt, welcher dem Voronoi-Diagramm entspricht. Es wird vorausgesetzt, dass die Punkte paarweise verschieden sind.

Zurückgegeben wird das Voronoi-Diagramm als Graph, d.h. als Liste von Punkten sowie als Liste der Indize der zugehörigen Kanten. Zudem werden auch die Indize der Voronoi-Zelle (d.h. das Thiessen-Polygon) ausgegeben. Zur genauen Verwendung sei auf die folgenden Beispiele verwiesen.

Beispiel

Im folgenden Beispiel werden zunächst 48 Punkte zufällig im Quadrat verteilt. Anschließend wird das zugehörige Voronoi-Diagramm berechnet und dieses graphisch dargestellt.

Es sei bemerkt, dass nur die beschränkten Voronoi-Zellen dargestellt werden, da sich nur diese direkt aus dem dualen Graphen ergeben. Alle unbeschränkten Voronoi-Zellen lassen sich bestimmen, indem geeignete Mittelsenkrechte gebildet werden.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot"></div>
<script>

  var A = ComputationalGeometry.random_points(48);
  var Q = ComputationalGeometry.voronoi(A);
  var V = Q[0];
  var E = Q[1];

  Svg.init("plot", 320, 320);
  Svg.resize(0, 100, 0, 100);
  Svg.clear("#f0f0f0");
  for (var s = 0; s < E.length; s++) {
    var i = E[s][0];
    var j = E[s][1];
    Svg.line(V[i][0], V[i][1], V[j][0], V[j][1], "#999999");
  };
  for (var i = 0; i < A.length; i++) Svg.dot(A[i][0], A[i][1], "#ff0000");
  Svg.draw();

</script>
</body>
</html>

Vorschau aktualisieren

Beispiel

Im folgenden Beispiel werden zunächst 48 Punkte zufällig im Quadrat verteilt. Anschließend wird das zugehörige Voronoi-Diagramm berechnet und es wird die Voronoi-Zelle (d.h. das Thiessen-Polygon) zum Index graphisch dargestellt.

<!DOCTYPE html>
<html>
<head>
  <script src="taramath.js"></script>
</head>
<body>
<div id="plot"></div>
<script>

  var A = ComputationalGeometry.random_points(48);
  var Q = ComputationalGeometry.voronoi(A);
  var V = Q[0];
  var W = Q[2];

  Svg.init("plot", 320, 320);
  Svg.resize(0, 100, 0, 100);
  Svg.clear("#f0f0f0");
  var r = 0;
  var n = W[r].length;
  for (var k = 0; k < n; k++) {
    var i = W[r][k];
    var j = W[r][(k+1)%n];
    Svg.line(V[i][0], V[i][1], V[j][0], V[j][1], "#999999");
  };
  for (var i = 0; i < A.length; i++) Svg.dot(A[i][0], A[i][1], "#ff0000");
  Svg.draw();

</script>
</body>
</html>

Vorschau aktualisieren

ComputationalGeometry.voronoi

zur Berechnung des Voronoi-Diagramms