gishur.x.voronoi
Class Skeleton

java.lang.Object
  |
  +--gishur.x.voronoi.Skeleton
All Implemented Interfaces:
java.lang.Cloneable, Cloneable, java.lang.Runnable, TraceExecutor

public class Skeleton
extends java.lang.Object
implements TraceExecutor, Cloneable, java.lang.Runnable

Mit Hilfe dieses Objektes kann man das Skelett eines einfachen Polygons berechnen und beispielsweise den maximal einbeschriebenen Kreis (MIC) berechnen. Bei der Konstruktion wird dieses Objekt mit einem Polygon verknüpft. Mit execute wird der Algorithmus ausgeführt. Es ist auch möglich einzelne Schritte auszugeben, indem man execute einen TraceListener übergibt und in diesem die Ausgabe wie gewünscht durchführt. Dazu bietet diese Klasse noch verschiedene Methoden um Polygonketten und deren Skelette ausgeben zu können.

Version:
1.0
Author:
Thomas Wolf

Field Summary
static int LABEL_TYPE_MERGE_CHAINS
          TraceLabel type for merge-chains-steps.
static int LABEL_TYPE_MERGE_STEP
          TraceLabel type for merge-steps.
static int LABEL_TYPE_MERGE_TRIM
          TraceLabel type for merge-trim-steps.
static double MAX_DISTANCE
          Diese Schranke wird benötigt, damit keine Rechenfehler auftreten.
 
Constructor Summary
Skeleton(XPolygon poly)
          Konstruktor.
 
Method Summary
 int chainCount()
          Liefert die aktuelle Anzahl der Polygonketten.
 void checkEdges()
          Überprüft bei allen Kanten den Typ, d.h.
 java.lang.Object clone()
          Creates a new object of the same class as this object.
 void execute()
          Führt die Konstruktion des Skeletts aus.
 void execute(Tracer tracer)
          Execute the algorithm using the given Tracer.
 SimpleList getChain(int chainnr)
          Liefert die Polygonkette Nr. chainnr.
 ListView getEdges()
          Liefert ein ListView-Objekt mit allen erzeugten Kanten.
 SimpleList getLines(boolean conedges)
          Liefert die Grafikobjekte.
 SimpleList getLines(int chainnr, boolean conedges)
          Liefert die Grafikobjekte der Kette Nummer chainnr.
 int getMaxUsedLevel()
          Returns the maximum level depth of traced algorithm steps.
 SimpleList getPoints()
          Liefert die echten Voronoipunkte.
 SimpleList getPoints(int chainnr)
          Liefert eine Liste mit den echten Voronoipunkten der Kette Nummer chainnr zurück.
 XPoint[] MIC()
          Sucht den größten einbeschrieben Kreis im Polygon.
 void run()
           
 
Methods inherited from class java.lang.Object
equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

LABEL_TYPE_MERGE_CHAINS

public static final int LABEL_TYPE_MERGE_CHAINS
TraceLabel type for merge-chains-steps.

LABEL_TYPE_MERGE_STEP

public static final int LABEL_TYPE_MERGE_STEP
TraceLabel type for merge-steps.

LABEL_TYPE_MERGE_TRIM

public static final int LABEL_TYPE_MERGE_TRIM
TraceLabel type for merge-trim-steps.

MAX_DISTANCE

public static final double MAX_DISTANCE
Diese Schranke wird benötigt, damit keine Rechenfehler auftreten. Sie gibt die maximale Entfernung eines Schnittunktes zum Rand an; d.h. sie sollte eigentlich aus dem Polygonradius ermittelt werden. Polygone dürfen momentan also keinen größeren Radius als 4000 haben...
Constructor Detail

Skeleton

public Skeleton(XPolygon poly)
Konstruktor. Verknüpft das Skelett-Objekt mit einem Polygon.
Parameters:
poly - Polygon, zu dem das Skelett berechnet werden soll.
Method Detail

clone

public java.lang.Object clone()
Creates a new object of the same class as this object.
Specified by:
clone in interface Cloneable
Overrides:
clone in class java.lang.Object
Returns:
a clone of this instance.
Throws:
OutOfMemoryError - if there is not enough memory.
See Also:
Cloneable

execute

public void execute()
Führt die Konstruktion des Skeletts aus. Der Algorithmus stammt von D. T. Lee und benötigt Laufzeit O(n*log n). Das verknüpfte Polygon sollte einfach sein - es erfolgt keine Überprüfung.

run

public void run()
Specified by:
run in interface java.lang.Runnable

execute

public void execute(Tracer tracer)
Execute the algorithm using the given Tracer.
Specified by:
execute in interface TraceExecutor
Parameters:
tracer - the Tracer to use for algorithm recording

getMaxUsedLevel

public int getMaxUsedLevel()
Returns the maximum level depth of traced algorithm steps.
Specified by:
getMaxUsedLevel in interface TraceExecutor
Returns:
the maximum level depth of traced algorithm steps.

getEdges

public ListView getEdges()
Liefert ein ListView-Objekt mit allen erzeugten Kanten.
Returns:
ListView mit allen Kanten des Skeletts

checkEdges

public void checkEdges()
Überprüft bei allen Kanten den Typ, d.h.

getLines

public SimpleList getLines(boolean conedges)
Liefert die Grafikobjekte.
Parameters:
conedges - falls true werden auch Kanten, die zu konkaven Ecken gehören zurückgegeben
Returns:
Liste mit Grafikobjekten der Kanten

getPoints

public SimpleList getPoints()
Liefert die echten Voronoipunkte.
Returns:
Liste mit Punkten

chainCount

public int chainCount()
Liefert die aktuelle Anzahl der Polygonketten.
Returns:
Anzahl der Ketten

getLines

public SimpleList getLines(int chainnr,
                           boolean conedges)
Liefert die Grafikobjekte der Kette Nummer chainnr.
Parameters:
chainnr - Kettennummer
conedges - falls true werden auch Kanten, die zu konkaven Ecken gehören zurückgegeben
Returns:
Liste mit Grafikobjekten der Kanten

getPoints

public SimpleList getPoints(int chainnr)
Liefert eine Liste mit den echten Voronoipunkten der Kette Nummer chainnr zurück.
Parameters:
chainnr - Kettennummer
Returns:
Liste mit Punkten

getChain

public SimpleList getChain(int chainnr)
Liefert die Polygonkette Nr. chainnr.
Returns:
Polygonkette

MIC

public XPoint[] MIC()
Sucht den größten einbeschrieben Kreis im Polygon. Zurückgegeben wird ein Array von Punkten. Der erste Punkt ist der Mittelpunkt des größten einbeschriebenen Kreises. Dieser Punkt ist ein Punkt des Skeletts. Ist der MIC (Maximal Inscribed Circle) nicht eindeutig, so werden die Daten irgendeines MIC's mit Mittelpunkt auf einem Skelettpunkt zurückgegeben. Die anderen Punkte des Arrays sind Kontaktpunkte des MIC's auf dem Polygonrand. Da der Mittelpunkt des zurückgegebenen MIC's auf einem Skelettpunkt (also auf einem Voronoipunkt) liegt, sollte das Array mindestens vier Punkte enthalten.
Die Laufzeit ist Abhängig von der Laufzeit des Algorithmus zur Bestimmung des Skeletts der Klasse Skeleton. Zur Zeit ist der einfachere Algorithmus von D.T. Lee mit einer Laufzeit von O(n) (n=Anzahl der Polygonpunkte) implementiert. Denkbar ist auch lineare Laufzeit (Algorithmus von Chin/Snoeyink/Wang).
Returns:
Array mit XPoint-Objekten wie oben beschrieben