gishur.x
Class XPolygon

java.lang.Object
  |
  +--gishur.x.XObject
        |
        +--gishur.x.XPolyline
              |
              +--gishur.x.XPolygon
All Implemented Interfaces:
AffineXTransformable, AreaIntersectable, java.lang.Cloneable, Cloneable, Intersectable, java.io.Serializable

public class XPolygon
extends XPolyline
implements AreaIntersectable

Ein Polygon.

Version:
1.0
Author:
Thomas Wolf
See Also:
Serialized Form

Field Summary
static byte ORIENTATION_LEFT
          Polygon ist entgegen dem Uhrzeigersinn orientiert.
static byte ORIENTATION_RIGHT
          Polygon ist im Uhrzeigersinn orientiert.
 
Fields inherited from interface gishur.x.AreaIntersectable
POINT_INSIDE, POINT_ON_EDGE, POINT_OUTSIDE
 
Constructor Summary
XPolygon()
          Leerer Konstruktor.
XPolygon(SimpleList L)
          Konstruiert ein Polygon aus der Liste L mit XPoint-, XSegment- und XRay-Objekten.
XPolygon(java.lang.String s)
          Einfacher String-Konstruktor. s muß die Form "...(x1,y1)...(x2,y2).." haben.
XPolygon(XPoint[] points)
          Konstruiert ein XPolygon mit dem Punktarray points.
XPolygon(XPolyline pol)
          Copy-Konstruktor.
 
Method Summary
 XSegment borderSegment(int i)
          Liefert das Randsegment Nummer i.
 double circumference()
          Berechnet den Umfang des Polygons.
 java.lang.Object clone()
          Überschreibt Object.clone(). java.lang.Object#clone
 int closestSegment(XPoint p, int i1, int i2)
          Liefert den Index des Segmentes, das den zu p nächsten Punkt (nicht als source()!)
 boolean contains(double x, double y)
          Liefert true, falls das Objekt den Punkt (x,y) enthält, d.h. der Schnitt mit dem Punkt nicht leer ist.
 XPolygon convexPolygonIntersection(XPolygon polygon)
          Schneidet das Polygon polygon mit diesem Polygon.
Vorbedingungen: Beide Polygon müssen konvex und entgegen Uhrzeigerrichtung (links) orientiert sein.
 int countBorderSegments()
          Liefert die Anzahl der Randsegmente.
 boolean equals(java.lang.Object O)
          Überschreibt Object.equals(Object)
 int findBorderIndex(int pointindex, boolean start)
          Sucht das Randelement, das mit dem Punkt mit Index pointindex beginnt, falls start==true bzw. endet, falls start==false.
 SimpleList getSegmentList()
          Liefert die Segmentliste des Polygons.
 SimpleList getSegmentList(byte orientation)
          Liefert die Segmentliste des Polygons in der Orientierung orientation.
 boolean in(XPoint q)
          Ein Point-in-Polygon Test.
 Area intersection(AreaIntersectable O, boolean is_convex)
          Flächenschnitt mit dem Objekt O.
 Intersection intersection(java.lang.Object O)
          Schneidet dieses Objekt mit dem Objekt O und liefert ein entsprechendes Intersection-Objekt.
 int liesOn(XPoint p)
          Sucht das erste borderSegment, auf dem der Punkt p liegt und liefert dessen Index oder -1, falls der Punkt nicht auf dem Rand liegt. p kann kein source()-Punkt eines Randsegmentes sein!
 XLine line(int i)
          Liefert eine Gerade durch den i-ten und (i+1)-ten Punkt des Polygons.
 byte locate(XPoint q)
          Point-Location.
 XPoint[] MIC()
          Sucht den größten einbeschrieben Kreis im Polygon mit Hilfe der Klasse gishur.x.voronoi.Skeleton.
 byte orientation()
          Berechnet die Orientierung des Polygons und gibt eine Orientierungskonstante zurück.
 SimpleList polygonIntersection(XPolygon pol)
          Schneidet in Zeit O(n*log(n)) das Polygon mit dem Polygon pol und gibt eine Liste mit den Schnittpolygonen zurück.
 int scanFirstIntersectingSegment(int i1, int i2, XBaseline l)
          Sucht in Umlaufrichtung das erste Segment zwischen i1 und i2 (inklusive), das das Linienobjekt l schneidet und gibt dessen Index zurück.
 XSegment segment(int i)
          Liefert das Segment vom i-ten bis zum (i+1)ten Punkt des Polygons.
 void setOrientation(byte orientation)
          Orientiert das Polygon entsprechend der übergebenen Orientierungskonstante.
 SimpleList skeleton()
          Berechnet das Skelett (auch Medial Axis) des einfachen Polygons mit Hilfe der Klasse gishur.x.voronoi.Skeleton.
 XPoint slidePoint(XPoint p, double dist)
          Verschiebt den Punkt p auf dem Polygonrand um dist.
 boolean supportsIntersection(AreaIntersectable O, boolean is_convex)
          Liefert true, falls diese Klasse den Schnitt mit dem übergebenen Gebiet unterstützt.
 boolean supportsIntersection(java.lang.Object O)
          Liefert true, falls diese Klasse den Schnitt mit dem übergebenen Objekt unterstützt.
 java.lang.String toString()
          Überschreibt Object.toString().
 XPolygon vis(XPoint p)
          Berechnet mit Hilfe der Klasse visPolygon das Sichtbarkeitspolygon bezüglich des Punktes p in O(n) Zeit.
 
Methods inherited from class gishur.x.XPolyline
add, add, checkSimplicity, checkSimplicity, clear, closestPoint, convex, copy, copy, cycle, empty, findPoint, findPoint, getMinMaxPoints, indexOf, insert, insert, kinkPoint, length, point, remove, reverse, rotate, rotate, scale, set, set, setPoint, simple, toString, transform_XObject, transform, translate
 
Methods inherited from class gishur.x.XObject
copy, getMutable, inverseTransform_XObject, mutable, restoreMutability, rotate_XObject, scale_XObject, transform_XObject, translate_XObject, translate_XObject
 
Methods inherited from class java.lang.Object
finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait
 
Methods inherited from interface gishur.x.AreaIntersectable
convex
 

Field Detail

ORIENTATION_LEFT

public static final byte ORIENTATION_LEFT
Polygon ist entgegen dem Uhrzeigersinn orientiert.

ORIENTATION_RIGHT

public static final byte ORIENTATION_RIGHT
Polygon ist im Uhrzeigersinn orientiert.
Constructor Detail

XPolygon

public XPolygon()
Leerer Konstruktor. Erzeugt ein leeres Polygon.

XPolygon

public XPolygon(XPoint[] points)
Konstruiert ein XPolygon mit dem Punktarray points. Das Array wird kopiert, die enthaltenen Punkte werden als Referenzen übernommen.
Parameters:
points - Punktliste

XPolygon

public XPolygon(SimpleList L)
Konstruiert ein Polygon aus der Liste L mit XPoint-, XSegment- und XRay-Objekten.
Parameters:
L - Liste mit Punktdaten.
See Also:
XPolyline.set(gishur.x.XPoint[])

XPolygon

public XPolygon(XPolyline pol)
Copy-Konstruktor.
Parameters:
l - Objekt, von dem Daten übernommen werden

XPolygon

public XPolygon(java.lang.String s)
Einfacher String-Konstruktor. s muß die Form "...(x1,y1)...(x2,y2).." haben.
Parameters:
s - String mit Polygondaten
Method Detail

clone

public java.lang.Object clone()
Überschreibt Object.clone(). java.lang.Object#clone
Overrides:
clone in class XPolyline
Following copied from class: gishur.x.XPolyline
See Also:
Object.clone()

toString

public java.lang.String toString()
Überschreibt Object.toString().
Overrides:
toString in class XPolyline
See Also:
Object.toString()

equals

public boolean equals(java.lang.Object O)
Überschreibt Object.equals(Object)
Overrides:
equals in class XPolyline
Parameters:
O - Objekt, mit dem verglichen werden soll
Returns:
true, falls Objekte gleich
See Also:
Object.equals(java.lang.Object)

getSegmentList

public SimpleList getSegmentList()
Liefert die Segmentliste des Polygons.
Overrides:
getSegmentList in class XPolyline
Returns:
Liste mit Segmenten

getSegmentList

public SimpleList getSegmentList(byte orientation)
Liefert die Segmentliste des Polygons in der Orientierung orientation.
Parameters:
orientation - Orientierung der Segmentliste
Returns:
Liste mit Segmenten

line

public XLine line(int i)
Liefert eine Gerade durch den i-ten und (i+1)-ten Punkt des Polygons.
Overrides:
line in class XPolyline
Parameters:
i - Index für die gewünschte Gerade
Returns:
Gerade

segment

public XSegment segment(int i)
Liefert das Segment vom i-ten bis zum (i+1)ten Punkt des Polygons. Segmente werden wie Punkte zyklisch durchnummeriert.
Overrides:
segment in class XPolyline
Parameters:
i - Index
Returns:
Segment mit Startpunkt Nummer i

countBorderSegments

public int countBorderSegments()
Liefert die Anzahl der Randsegmente. Bei einer Polyline sind alle Randsegment normale Segmente, bei abgeleiteten Klassen können Segmente Randpunkte der 'unendlichen' Bounding-Box enthalten.
Overrides:
countBorderSegments in class XPolyline
Returns:
Anzahl der Randelemente

borderSegment

public XSegment borderSegment(int i)
Liefert das Randsegment Nummer i.
Overrides:
borderSegment in class XPolyline
Parameters:
i - Index des gewünschten Randelements
Returns:
Randelement mit Index i

findBorderIndex

public int findBorderIndex(int pointindex,
                           boolean start)
Sucht das Randelement, das mit dem Punkt mit Index pointindex beginnt, falls start==true bzw. endet, falls start==false.
Overrides:
findBorderIndex in class XPolyline
Parameters:
pointindex - Index des Polygonpunktes
start - falls true wird Randelement zurückgegeben, das mit pointindex beginnt; falls false jenes, das mit pointindex endet
Returns:
Index des Randelements oder -1

liesOn

public int liesOn(XPoint p)
Sucht das erste borderSegment, auf dem der Punkt p liegt und liefert dessen Index oder -1, falls der Punkt nicht auf dem Rand liegt. p kann kein source()-Punkt eines Randsegmentes sein!
Overrides:
liesOn in class XPolyline
Parameters:
p - zu suchender Punkt
Returns:
die Nummer des Randelementes, auf dem p liegt oder -1

slidePoint

public XPoint slidePoint(XPoint p,
                         double dist)
Verschiebt den Punkt p auf dem Polygonrand um dist.
Parameters:
p - Ausgangspunkt
dist - Entfernung auf dem Rand
Returns:
verschobener Punkt

closestSegment

public int closestSegment(XPoint p,
                          int i1,
                          int i2)
Liefert den Index des Segmentes, das den zu p nächsten Punkt (nicht als source()!) in Umlaufrichtung zwischen den Segmenten mit Indizes i1 und i2 enthält.
Parameters:
p - Punkt, zu dem nächster Punkt auf dem Rand gesucht wird
i1,i2 - Segmentindizes für das Suchintervall (beide inklusive)

circumference

public double circumference()
Berechnet den Umfang des Polygons.
Overrides:
circumference in class XPolyline
Returns:
Umfang

orientation

public byte orientation()
Berechnet die Orientierung des Polygons und gibt eine Orientierungskonstante zurück. Handelt es sich um ein unbeschränktes Polygon, wird einfach area zurückgegeben.
Returns:
entweder ORIENTATION_LEFT, falls gegen den Uhrzeigersinn orientiert oder ORIENTATION_RIGHT, falls im Uhrzeigersinn orientiert.

setOrientation

public void setOrientation(byte orientation)
Orientiert das Polygon entsprechend der übergebenen Orientierungskonstante.
Parameters:
orientation - Orientierungskonstante für künftige Orientierung

in

public boolean in(XPoint q)
Ein Point-in-Polygon Test. Gibt true zurück, falls der Punkt p innerhalb des Polygons liegt. Auf einer Polygonkante zählt hierbei als außerhalb. Benutzt locatePoint.
Parameters:
p - zu testender Punkt
Returns:
true, falls p innerhalb des Polygons liegt, ansonsten false
See Also:
locate(gishur.x.XPoint)

locate

public byte locate(XPoint q)
Point-Location. Je nach Position des Punktes p wird eine der drei Konstanten zurückgegeben:

Vorbedingungen: Das Polygon muß einfach sein.

Specified by:
locate in interface AreaIntersectable
Parameters:
p - zu lokalisierender Punkt
Returns:
POINT_INSIDE, POINT_OUTSIDE oder POINT_ON_EDGE, je nach Lage des Punktes.

vis

public XPolygon vis(XPoint p)
Berechnet mit Hilfe der Klasse visPolygon das Sichtbarkeitspolygon bezüglich des Punktes p in O(n) Zeit.
Parameters:
p - Sichtpunkt
Returns:
Sichtbarkeitspolygon bezüglich des Punktes p

skeleton

public SimpleList skeleton()
Berechnet das Skelett (auch Medial Axis) des einfachen Polygons mit Hilfe der Klasse gishur.x.voronoi.Skeleton. Das Skelett wird als Liste der Linien und Parabelsegmente und der (echten) Skelettpunkte (also der Voronoipunkte) zurückgegeben. Um andere Repräsentationen zu erhalten, sollte direkt mit dem Skeleton-Objekt gearbeitet werden. Die Laufzeit ist abhängig von der Laufzeit des implementierten Algorithmus in 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:
Liste mit Skelett -linien, -parabelstücken und -punkten.
See Also:
Skeleton

MIC

public XPoint[] MIC()
Sucht den größten einbeschrieben Kreis im Polygon mit Hilfe der Klasse gishur.x.voronoi.Skeleton. 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
See Also:
Skeleton

scanFirstIntersectingSegment

public int scanFirstIntersectingSegment(int i1,
                                        int i2,
                                        XBaseline l)
Sucht in Umlaufrichtung das erste Segment zwischen i1 und i2 (inklusive), das das Linienobjekt l schneidet und gibt dessen Index zurück.
Parameters:
i1,i2 - Indix des Start bzw. Zielsegmentes
l - auf Schnitt zu untersuchendes Linienobjekt
Returns:
Index des ersten Polygonsegmentes, das l schneidet

contains

public boolean contains(double x,
                        double y)
Liefert true, falls das Objekt den Punkt (x,y) enthält, d.h. der Schnitt mit dem Punkt nicht leer ist.
Overrides:
contains in class XPolyline
Parameters:
x,y - Koordinaten des Punktes
Returns:
true, falls Schnitt nicht leer.

supportsIntersection

public boolean supportsIntersection(java.lang.Object O)
Liefert true, falls diese Klasse den Schnitt mit dem übergebenen Objekt unterstützt. Hier sollte wirklich nur dann true zurückgegeben werden, wenn in dieser Klasse eine entsprechende Schnittroutine existiert.
Overrides:
supportsIntersection in class XPolyline
Parameters:
O - zu schneidendes Objekt
Returns:
true, falls Schnittest erfolgen kann

intersection

public Intersection intersection(java.lang.Object O)
Schneidet dieses Objekt mit dem Objekt O und liefert ein entsprechendes Intersection-Objekt. Dieses ist immer !=null, was nicht heißt, daß ein Schnitt existiert. Existiert keine passende Schnittmethode in dieser Klasse, so wird versucht, die Schnittmethode des Objektes O aufzurufen, falls vorhanden. Schlägt alles fehl, so wird ein IntersectionException ausgelöst (der nicht unbedingt abgefangen werden muß, da es ein RuntimeException ist.
Overrides:
intersection in class XPolyline
Parameters:
O - zu schneidendes Objekt
Throws:
IntersectionException - falls der Schnitt nicht durchgeführt werden konnte.

supportsIntersection

public boolean supportsIntersection(AreaIntersectable O,
                                    boolean is_convex)
Liefert true, falls diese Klasse den Schnitt mit dem übergebenen Gebiet unterstützt. Hier sollte wirklich nur dann true zurückgegeben werden, wenn in dieser Klasse eine entsprechende Schnittroutine existiert.
Specified by:
supportsIntersection in interface AreaIntersectable
Parameters:
O - zu schneidendes Objekt
is_convex - falls true, ist das Objekt O konvex
Returns:
true, falls Schnittest erfolgen kann

intersection

public Area intersection(AreaIntersectable O,
                         boolean is_convex)
Flächenschnitt mit dem Objekt O. Diese Methode sollte am Besten nur von einem Area-Objekt aufgerufen werden. Kann der Schnitt nicht berechnet werden, sollte ein IntersectionException ausgelöst werden (dies sollte aber in Übereinstimmung mit supportsAreaIntersection geschehen). Es kann sein, das Schnitte falsch berechnet werden und kein Exception ausgelöst wird, obwohl supportsAreaIntersection false liefert. Der Aufruf von supportsAreaIntersection sollte also vorausgehen.
Specified by:
intersection in interface AreaIntersectable
Parameters:
O - zu schneidendes Objekt
is_convex - falls true, ist das Objekt O konvex
Throws:
IntersectionException - falls der Schnitt nicht durchgeführt werden konnte.

convexPolygonIntersection

public XPolygon convexPolygonIntersection(XPolygon polygon)
Schneidet das Polygon polygon mit diesem Polygon.
Vorbedingungen: Beide Polygon müssen konvex und entgegen Uhrzeigerrichtung (links) orientiert sein.
Parameters:
polygon - zweites Polygon
Returns:
konvexes Schnittpolygon

polygonIntersection

public SimpleList polygonIntersection(XPolygon pol)
Schneidet in Zeit O(n*log(n)) das Polygon mit dem Polygon pol und gibt eine Liste mit den Schnittpolygonen zurück. Vorbedingungen: Beide Polygon müssen einfach sein.
Parameters:
poly - zu schneidendes Polygon
Returns:
Liste mit Schnittpolygonen