Voronoi Diagramme


Processing 2.0

Voronoi Diagramme, benannt nach dem ukrainischen Mathematiker Georgi Feodosjewitsch Woronoi können für verschiedene Problemstellungen Lösungen liefern. Z.B.:

  • Standortsuche für öffentliche Einrichtungen (optimale Erreichbarkeit)
  • Bewertung von Standorten
  • Modellierung von Nähe

Was ist nun so ein Voronoi Diagramm?

131225_122847_1010Gegeben sind eine Menge von Punkten M. Die Voronoi Region eines Punktes enthält nun ausschließlich Punkte, welche genau diesem, und keinem anderen Punkt M am nächsten sind. Es sind Gebiete mit dem gleichen nächsten Nachbarn. Das Diagramm besteht aus Voronoi Knoten, an denen immer genau 3 Voronoi Kanten einander treffen.

Aufgabe: Nimm ein leeres Blatt Papier und  zeichne ungefähr 7 zufällig verteilte Punkte darauf. Konstruiere ein Voronoi Diagramm von Hand.

Anleitung: Verbinde alle benachbarten Punkte mit Hilfslinien. Teile diese Hilfslinien in der Mitte und zeichne eine Normale durch diesen Punkt. Die Normalen stellen die Voronoi Kanten, deren Schnittpunkte die Knoten dar. Siehe auch: HowVoronoiDiagramsWork

Beispiel: Für meine Implementierung des Voronoi Algorithmus verwende ich die Mesh Library von Lee Byron. Der Sketch bietet die Möglichkeit, Voronoi Punkte zu zeichnen und zu verschieben und so mit dem Algorithmus zu experimentieren.

/** Copyright 2013 Thomas Koberger
*/

// https://lernprocessing.wordpress.com/
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

/**
*
* MOUSE
* LEFT                :Create/Drag VoroPoint
*
* KEYS
* s                   : save png
*/

import java.util.Calendar;
import megamu.mesh.*;

//Arraylist and Array um die Punkte zu speichen
ArrayList<Integer> voroPoints;
Voronoi myVoronoi;
float[][] points;

//Punkt, der gerade bewegt wird
int activePoint;

void setup() {
size(800, 800);
voroPoints = new ArrayList<Integer> ();
activePoint=10000;
}

void draw() {
background(255);

//Wenn mindestens 1 Punkt vorhanden ist wird gezeichnet
if (voroPoints.size()>1) {

//getRegions
strokeWeight(1);
stroke(80, 150);
MPolygon[] myRegions = myVoronoi.getRegions();
for (int i=0; i<myRegions.length; i++)
{
// an array of points
float[][] regionCoordinates = myRegions[i].getCoords();
myRegions[i].draw(this); // draw this shape
}
}

// draw Points
fill(255);
strokeWeight(6);
stroke(0);
for (int i=0; i<voroPoints.size(); i+=2) {
point((int)voroPoints.get(i), (int)voroPoints.get(i+1));
}
}

void createVoronoi () {
points = new float[voroPoints.size()/2][2];
for (int i=0; i<voroPoints.size(); i+=2) {

points[i/2][0] =(int) voroPoints.get(i);
points[i/2][1] =(int) voroPoints.get(i+1);
}
myVoronoi = new Voronoi( points );
}

//Abfrage, ob sich an der Mausposition ein Punkt befindet
void mousePressed() {
for (int i=0; i<voroPoints.size(); i+=2) {
int x =(int) voroPoints.get(i);
int y =(int) voroPoints.get(i+1);
if (mouseX<x+5 && mouseX>x-5 && mouseY<y+5 &&mouseY>y-5) activePoint=i;
}
}

//Wenn kein Punkt aktiv ist und gerade bewegt wird, wird ein neuer hinzugefügt
void mouseReleased() {
println("released");
if (activePoint==10000) {
voroPoints.add((int)mouseX);
voroPoints.add((int)mouseY);
createVoronoi();
}
activePoint = 10000;
}

//Punkt wird gezogen
void mouseDragged() {
if (activePoint!=10000) {
voroPoints.set(activePoint, mouseX);
voroPoints.set(activePoint+1, mouseY);
createVoronoi();
}
}

void keyReleased() {
if (key == 's' || key == 'S') saveFrame(timestamp()+"_##.png");
}

//timestamp
String timestamp() {
Calendar now = Calendar.getInstance();
return String.format("%1$ty%1$tm%1$td_%1$tH%1$tM%1$tS", now);
}
Advertisements

2 Kommentare

  1. Pingback: Processing – Über dieses Weblog | processing - tutorial

  2. Pingback: Voronoi und die französiche Revolution | processing - tutorial

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: