Das ComputationalGeometry-Paket

zur algorithmischen Geometrie im Zweidimensionalen

q r s u t

Funktionsübersicht

.convex_hull .delaunay .voronoi .random_points .is_distinct .make_distinct

Beschreibung

Das ComputationalGeometry-Paket stellt einige Verfahren der algorithmischen Geometrie bereit, welche jeweils auf eine diskrete Menge an Punkten in der Ebene angewandt werden können. Insbesondere lässt sich die Delaunay-Triangulierung, das Voronoi-Diagramm sowie die konvexe Hülle berechnen. Alle drei Verfahren besitzen dabei eine Komplexität von .

Beispiel

Im folgenden Beispiel werden zunächst 24 Punkte zufällig im Quadrat verteilt. Anschließend wird die zugehörige Delaunay-Triangulierung berechnet und diese graphisch dargestellt.

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

  var A = ComputationalGeometry.random_points(24);
  var F = ComputationalGeometry.delaunay(A);

  Svg.init("plot", 320, 320);
  Svg.resize(0, 100, 0, 100);
  Svg.clear("#f0f0f0");
  for (var s = 0; s < F.length; s++) {
    var i = F[s][0];
    var j = F[s][1];
    var k = F[s][2];
    Svg.triangle(A[i][0], A[i][1], A[j][0], A[j][1], A[k][0], A[k][1], "none", "#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