|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--gishur.core.Sweep | +--gishur.x.SegmentIntersectionSweep
SegmentIntersectionSweep realisiert einen Plane-Sweep-Algorithmus zum Bestimmen von
Schnittpunkten von n Segmenten in O(n*log(n)) Zeit mit Hilfe der Sweep-Basisklasse.
Mit segmentIntersection wird der Algorithmus auf die übergebene Segmentliste
angewandt und gibt die Punktliste zurück.
Mittels setOutputMode kann das Ausgabeformat beeinflußt werden, mit
setIntersectionMode kann festgelegt werden, welche Schnittpunkte erkannt werden
sollen. Das genaue Verhalten ist den folgenden Tabellen zu entnehmen:
Übersicht des Verhaltens bei verschiedenen Schnittmodi:
Konstante | erkannte Schnitte |
ALL_INTERSECTIONS | alle Schnitte der Segmente |
REAL_INTERSECTIONS | Nur 'echte' Schnitte, d.h keine Schnittpunkte, die auf die Enden eines Segmentes fallen. |
WITHOUT_TARGETS | Nur Schnittpunkte, die kein Endpunkt eines Segmentes sind. |
Konstante | Ausgabeformat |
POINTS | eine Liste mit den Schnittpunkten (keine doppelten Punkte) |
POINTS_AND_SEGMENTS | eine Liste mit den Schnittpunkten als Schlüssel und einem XSegment-Array mit allen daran beteiligten Segmenten als Wert. |
This algorithm supports recording via a Tracer
. In order to
visualize the recorded data, here is the list and meaning of the recorded
objects and levels.
Recorded Labels | |||
Labelname | Label Type | Level | Meaning |
Reached event point | LABEL_TYPE_EVENT_LEFT |
0 | Reached the event 'left endpoint'. |
Reached event point | LABEL_TYPE_EVENT_RIGHT |
0 | Reached the event 'right endpoint'. |
Reached event point | LABEL_TYPE_EVENT_INTER |
0 | Reached the event 'intersection point'. |
After event point | LABEL_TYPE_AFTER_LEFT |
1 | Situation after computation of the event 'left endpoint'. |
After event point | LABEL_TYPE_AFTER_RIGHT |
1 | Situation after computation of the event 'right endpoint'. |
After event point | LABEL_TYPE_AFTER_INTER |
1 | Situation after computation of the event 'intersection point'. |
Recorded Objects | ||
Objectname | Types | Meaning |
event_point | gishur.x.XPoint |
The event points, where the sweepline stops. |
sss | gishur.core.BinarySearchTree |
The sweep status structure. |
points | gishur.core.List |
All reported intersection points. |
insert_seg | gishur.x.XSegment |
The segment to be inserted to the sss. |
remove_seg | gishur.x.XSegment |
The segment to be removed from the sss. |
swap_seg1 | gishur.x.XSegment |
The first segment to be swapped in the sss. |
swap_seg2 | gishur.x.XSegment |
The second segment to be swapped in the sss. |
cut_1 | gishur.x.XPoint |
The first cutpoint (or null ). |
cut_2 | gishur.x.XPoint |
The second cutpoint (or null ). |
Field Summary | |
static byte |
ALL_INTERSECTIONS
Schnittmodus: Alle Schnittpunkte werden berechnet |
static byte |
INTERSECTION
Ereignis-ID: Schnittpunkt erreicht |
static int |
LABEL_TYPE_AFTER_INTER
TraceLabel type for events. |
static int |
LABEL_TYPE_AFTER_LEFT
TraceLabel type for events. |
static int |
LABEL_TYPE_AFTER_RIGHT
TraceLabel type for events. |
static int |
LABEL_TYPE_EVENT_INTER
TraceLabel type for events. |
static int |
LABEL_TYPE_EVENT_LEFT
TraceLabel type for events. |
static int |
LABEL_TYPE_EVENT_RIGHT
TraceLabel type for events. |
static byte |
LEFT_ENDPOINT
Ereignis-ID: linker Endpunkt erreicht |
static byte |
POINTS
Ausgabemodus: Nur Schnittpunkte werden ausgegeben |
static byte |
POINTS_AND_SEGMENTS
Ausgabemodus: Schnittpunkte und beteiligte Segmente werden ausgegeben |
static byte |
REAL_INTERSECTIONS
Schnittmodus: Nur echte Schnitte werden berechnet |
static byte |
RIGHT_ENDPOINT
Ereignis-ID: rechter Endpunkt erreicht |
static byte |
WITHOUT_TARGETS
Schnittmodus: Nur Schnittpunkte, die nicht an den Segment-Target-Punkten liegen, werden ausgegeben |
Constructor Summary | |
SegmentIntersectionSweep()
|
Method Summary | |
byte |
intersectionMode()
Liefert den gesetzten Schnittmodus. |
byte |
outputMode()
Liefert den gesetzten Ausgabemodus. |
void |
processEvent(SweepEvent e)
Verarbeitet das SweepEvent e. |
List |
segmentIntersection(SimpleList L)
Führt einen Plane-Sweep durch, um alle Schnittpunkte der in der Liste L übergebenen Segmente zu bestimmen. |
List |
segmentIntersection(SimpleList L,
Tracer tracer)
Wie segmentIntersection(gishur.core.SimpleList) , nur mit Aufzeichnen des Algorithmus mittels
eines Tracer Objektes. |
void |
setIntersectionMode(byte mode)
Setzt den Schnittmodus auf die übergebene Konstante. |
void |
setOutputMode(byte mode)
Setzt den Ausgabemodus auf die übergebene Konstante. |
Methods inherited from class gishur.core.Sweep |
createEventStructure, createEventStructure, createSSS, createSSS, execute, insertEvent, setSweepListener, sss |
Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
public static final int LABEL_TYPE_EVENT_LEFT
TraceLabel
type for events.public static final int LABEL_TYPE_EVENT_INTER
TraceLabel
type for events.public static final int LABEL_TYPE_EVENT_RIGHT
TraceLabel
type for events.public static final int LABEL_TYPE_AFTER_LEFT
TraceLabel
type for events.public static final int LABEL_TYPE_AFTER_INTER
TraceLabel
type for events.public static final int LABEL_TYPE_AFTER_RIGHT
TraceLabel
type for events.public static final byte LEFT_ENDPOINT
public static final byte INTERSECTION
public static final byte RIGHT_ENDPOINT
public static final byte POINTS
public static final byte POINTS_AND_SEGMENTS
public static final byte ALL_INTERSECTIONS
public static final byte REAL_INTERSECTIONS
public static final byte WITHOUT_TARGETS
Constructor Detail |
public SegmentIntersectionSweep()
Method Detail |
public byte outputMode()
public void setOutputMode(byte mode)
mode
- neuer Ausgabemodus (eine Konstante aus {POINTS, POINTS_AND_SEGMENTS})public byte intersectionMode()
public void setIntersectionMode(byte mode)
neuer
- Schnittmodus (eine Konstante aus {ALL_INTERSECTIONS, ALL_INTERSECTIONS,
WITHOUT_TARGETS}public List segmentIntersection(SimpleList L)
Konstante | erkannte Schnitte |
ALL_INTERSECTIONS | alle Schnitte der Segmente |
REAL_INTERSECTIONS | Nur 'echte' Schnitte, d.h keine Schnittpunkte, die auf die Enden eines Segmentes fallen. |
WITHOUT_TARGETS | Nur Schnittpunkte, die kein Endpunkt eines Segmentes sind. |
Konstante | Ausgabeformat |
POINTS | eine Liste mit den Schnittpunkten (keine doppelten Punkte) |
POINTS_AND_SEGMENTS | eine Liste mit den Schnittpunkten als Schlüssel und einem XSegment-Array mit allen daran beteiligten Segmenten als Wert. |
L
- Segmentliste (Liste mit XSegment-Objekten)PointComparitor.X_ORDER
public List segmentIntersection(SimpleList L, Tracer tracer)
segmentIntersection(gishur.core.SimpleList)
, nur mit Aufzeichnen des Algorithmus mittels
eines Tracer
Objektes.L
- Segmentliste (Liste mit XSegment-Objekten)tracer
- das Tracer
-Objekt zum Aufzeichnen des Algorithmus.segmentIntersection(SimpleList)
public void processEvent(SweepEvent e)
processEvent
in class Sweep
e
- SweepEvent
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |