• 
  • News
  • About
  • Contact
  • Location
• 
  • Alumni
  • People
• 
  • Projects
  • Software
  • Gallery
• 
  • Articles
  • Libraries
• 
  • Topics for Student Projects
  • Lectures
  • Computer-Aided Geometric Design
  • - Photorealism
  • - Design and Implementation
  • - Simulation and Animation
  • - Digital Libraries
  • - AK Computer Graphics
• 
  • Dave
  • HEyeWall
  • Davelib
  • Multitouch

> People > people > havemann > VoronoiSitesFromDiagram

Voronoi-Orte aus dem Voronoi-Diagramm bestimmen

Sven Havemann

Das ActiveGML-BrowserPlugin kann man von der GML-Webseite www.generative-modeling.org herunterladen, hier ist auch ein direkter Link auf das Plugin.

Bedienung:

Linke Maustaste auf Pfeil klicken:	Slider-Punkt verändern
Linke Maustaste auf Hintergrund:	Rotieren um (das Objekt hinter dem) Center-Pixel
Rechte Maustaste:	Zooming
Mittlere Maustaste:	Panning

Die folgenden Links starten das Applet: Voronoi-Knoten , Voronoi-Kante , Voronoi-Kante anders parametrisiert. Tip: Der kleine graue Ball in der Mitte ist ein Schalter mit dem man die Hilfslinien aus- und einschalten kann. Er wechselt dabei übrigens die Farbe. Weiterer Tip: Es gibt auch rote Slider-Pfeile.

Hilfslinien an/aus [Version]

---

 
Betrachte einen Knoten v des Voronoi-Diagramms, dort treffen sich >=3
Voronoi-Kanten. Angenommen es sind genau 3, dann treffen sich dort auch 3
Voronoi-Zellen, deren Orte seien A1,A2,A3. Die drei Kanten dazwischen seien
e12,e23,e31.

Jetzt gelten zwei wichtige Eigenschaften: 

(a) A1,A2,A3 haben von v alle den gleichen Abstand r 
(b) Kante e12 ist Mittelsenkrechte von Strecke A1,A2  (usw.)

Angenommen r sei bekannt. Dann läßt sich die Lage von A1,A2,A3 eindeutig
berechnen: Zieh einen Kreis K mit Radius r um v, und zeichne 360 Grad auf
diesem Kreis ein, mit 0 Grad wie normal nach rechts (positive x-Achse). Dann
seien

- w12,w23,w31 die (bekannten) Winkel unter denen e12,e23,e31 von v aus
  ausstrahlen
- w1,w2,w3 die (unbekannten) Winkel unter denen A1,A2,A3 von v aus
  auf K liegen

Wegen (b) muß w12 aber die Winkelhalbierende von Winkel(w1,w2) sein, also
w12=0.5*(w1+w2) (mod 360) usw. In Matrixschreibweise, ohne mod:
  
  (2*w12)   (1 1 0)   (w1)       (w1)   ( 1 -1  1)   (w12)
  (2*w23) = (0 1 1) * (w2)  <=>  (w2) = ( 1  1 -1) * (w23)
  (2*w13)   (1 0 1)   (w3)       (w3)   (-1  1  1)   (w31)

Jetzt ist das Problem daß r natürlich nicht bekannt ist. Das läßt sich aber
lösen wenn man statt eines einzelnen Voronoi-Vertex deren zwei v1,v2
betrachtet, die mit einer Voronoi-Kante verbunden sind. Dann hat man die
beschriebene Konfiguration zweimal, mit zwei Kreisen K1,K2 mit Radien
r1,r2. Seien A1,A2 die Orte der beiden Voronoi-Zellen beiderseits der Kante,
dann müssen r1 und r2 so gewählt werden daß A1 und A2 für beide Kreise
identisch sind, und identisch mit den beiden Schnittpunkten der Kreise. Das ist
nur auf eine Weise möglich, und damit ist in diesem Fall die Lage von vier
Voronoi-Orten eindeutig bestimmt.

Illustrationen anbei:

Applet Nr. 1 dazu (wird oben gemalt)

Diese Bilder (vom 1. Applet) zeigen einen Voronoi-Vertex (rot) mit drei Kanten
(rot) und drei Orten (blau). Die rechten Bilder zeigen den Kreis (blau) und die
Verbindungsstrecken zwischen den Orten. Die Voronoi-Kanten sind gerade die
Mittelsenkrechten dieser Verbindungsstrecken. Beachte daß der Radius
willkürlich gewählt ist, angedeutet durch die Strahlen (grün), die zeigen,
wohin sich die Orte bei wachsendem Radius bewegen würden.

Applet Nr. 2 dazu (wird oben gemalt)
Bonus-Applet Nr. 3: Alternative Parametrisierung (wird ebenfalls oben gemalt)

Diese Bilder (vom 2. Applet) zeigen die Situation mit zwei Voronoi-Knoten die
mit einer Kante verbunden sind. Die rechten Bilder zeigen die beiden Kreise um
die Voronoi-Knoten, die Strahlen (grün) kreuzen sich gerade in den Orten ober-
und unterhalb der Kante.

Das letzte Applet Nr. 3 zeigt im Prinzip das gleiche, nur anders
parametrisiert: Statt der vierten Kante kann man hier die Länge der
Horizontalkante verändern, und der Kreisradius (rechts) ist fixiert. Nach wie
vor hat man aber vier Freiheitsgrade, und die Längenänderung der Kante bei
fixem Radius ist so gut wie das Verändern des Radius. In jedem Fall ist die
Lage der Orte eindeutig bestimmt.

Copyright 2006-2008 Computer Graphics & Knowledge Visualization, TU Graz
All rights reserved.

Collection Listing