gishur.x
Class SegmentIntersectionSweep

java.lang.Object
  |
  +--gishur.core.Sweep
        |
        +--gishur.x.SegmentIntersectionSweep
All Implemented Interfaces:
java.util.EventListener, SweepListener

public class SegmentIntersectionSweep
extends Sweep

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.
Übersicht des Verhaltens bei verschiedenen Ausgabemodi:
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).

Version:
1.1
Author:
Thomas Wolf

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

LABEL_TYPE_EVENT_LEFT

public static final int LABEL_TYPE_EVENT_LEFT
TraceLabel type for events.

LABEL_TYPE_EVENT_INTER

public static final int LABEL_TYPE_EVENT_INTER
TraceLabel type for events.

LABEL_TYPE_EVENT_RIGHT

public static final int LABEL_TYPE_EVENT_RIGHT
TraceLabel type for events.

LABEL_TYPE_AFTER_LEFT

public static final int LABEL_TYPE_AFTER_LEFT
TraceLabel type for events.

LABEL_TYPE_AFTER_INTER

public static final int LABEL_TYPE_AFTER_INTER
TraceLabel type for events.

LABEL_TYPE_AFTER_RIGHT

public static final int LABEL_TYPE_AFTER_RIGHT
TraceLabel type for events.

LEFT_ENDPOINT

public static final byte LEFT_ENDPOINT
Ereignis-ID: linker Endpunkt erreicht

INTERSECTION

public static final byte INTERSECTION
Ereignis-ID: Schnittpunkt erreicht

RIGHT_ENDPOINT

public static final byte RIGHT_ENDPOINT
Ereignis-ID: rechter Endpunkt erreicht

POINTS

public static final byte POINTS
Ausgabemodus: Nur Schnittpunkte werden ausgegeben

POINTS_AND_SEGMENTS

public static final byte POINTS_AND_SEGMENTS
Ausgabemodus: Schnittpunkte und beteiligte Segmente werden ausgegeben

ALL_INTERSECTIONS

public static final byte ALL_INTERSECTIONS
Schnittmodus: Alle Schnittpunkte werden berechnet

REAL_INTERSECTIONS

public static final byte REAL_INTERSECTIONS
Schnittmodus: Nur echte Schnitte werden berechnet

WITHOUT_TARGETS

public static final byte WITHOUT_TARGETS
Schnittmodus: Nur Schnittpunkte, die nicht an den Segment-Target-Punkten liegen, werden ausgegeben
Constructor Detail

SegmentIntersectionSweep

public SegmentIntersectionSweep()
Method Detail

outputMode

public byte outputMode()
Liefert den gesetzten Ausgabemodus.
Returns:
Ausgabemodus (eine Konstante aus {POINTS, POINTS_AND_SEGMENTS})

setOutputMode

public void setOutputMode(byte mode)
Setzt den Ausgabemodus auf die übergebene Konstante.
Parameters:
mode - neuer Ausgabemodus (eine Konstante aus {POINTS, POINTS_AND_SEGMENTS})

intersectionMode

public byte intersectionMode()
Liefert den gesetzten Schnittmodus.
Returns:
Schnittmodus (eine Konstante aus {ALL_INTERSECTIONS, ALL_INTERSECTIONS, WITHOUT_TARGETS}

setIntersectionMode

public void setIntersectionMode(byte mode)
Setzt den Schnittmodus auf die übergebene Konstante.
Parameters:
neuer - Schnittmodus (eine Konstante aus {ALL_INTERSECTIONS, ALL_INTERSECTIONS, WITHOUT_TARGETS}

segmentIntersection

public List segmentIntersection(SimpleList L)
Führt einen Plane-Sweep durch, um alle Schnittpunkte der in der Liste L übergebenen Segmente zu bestimmen. Die Ausgabeliste enthält alle Schnittpunkte sortiert nach X-Koordinaten (PointComparitor.X_ORDER).
Ü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.
Übersicht des Verhaltens bei verschiedenen Ausgabemodi:
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.
Parameters:
L - Segmentliste (Liste mit XSegment-Objekten)
Returns:
Liste mit den Schnittpunkten
See Also:
PointComparitor.X_ORDER

segmentIntersection

public List segmentIntersection(SimpleList L,
                                Tracer tracer)
Wie segmentIntersection(gishur.core.SimpleList), nur mit Aufzeichnen des Algorithmus mittels eines Tracer Objektes.
Parameters:
L - Segmentliste (Liste mit XSegment-Objekten)
tracer - das Tracer-Objekt zum Aufzeichnen des Algorithmus.
See Also:
segmentIntersection(SimpleList)

processEvent

public void processEvent(SweepEvent e)
Verarbeitet das SweepEvent e.
Overrides:
processEvent in class Sweep
Parameters:
e - SweepEvent