00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031
00032
00033
00034 #ifndef GEOS_INDEXSWEEPLINE_H
00035 #define GEOS_INDEXSWEEPLINE_H
00036
00037 #include <memory>
00038 #include <vector>
00039 #include <geos/platform.h>
00040
00041 using namespace std;
00042
00043 namespace geos {
00044
00045 class SweepLineInterval {
00046 public:
00047 SweepLineInterval(double newMin, double newMax);
00048 SweepLineInterval(double newMin, double newMax, void* newItem);
00049 double getMin();
00050 double getMax();
00051 void* getItem();
00052 private:
00053 double min, max;
00054 void* item;
00055 };
00056
00057 class SweepLineOverlapAction {
00058 public:
00059 virtual void overlap(SweepLineInterval *s0,SweepLineInterval *s1)=0;
00060 };
00061
00062 class indexSweepLineEvent {
00063 public:
00064 enum {
00065 INSERT_EVENT = 1,
00066 DELETE_EVENT
00067 };
00068 indexSweepLineEvent(double x,indexSweepLineEvent *newInsertEvent,SweepLineInterval *newSweepInt);
00069 bool isInsert();
00070 bool isDelete();
00071 indexSweepLineEvent* getInsertEvent();
00072 int getDeleteEventIndex();
00073 void setDeleteEventIndex(int newDeleteEventIndex);
00074 SweepLineInterval* getInterval();
00081 int compareTo(indexSweepLineEvent *pe);
00082 int compareTo(void *o);
00083 private:
00084 double xValue;
00085 int eventType;
00086 indexSweepLineEvent *insertEvent;
00087 int deleteEventIndex;
00088 SweepLineInterval *sweepInt;
00089 };
00090
00091
00092
00093
00094
00095 class SweepLineIndex {
00096 public:
00097 SweepLineIndex();
00098 ~SweepLineIndex();
00099 void add(SweepLineInterval *sweepInt);
00100 void computeOverlaps(SweepLineOverlapAction *action);
00101 private:
00102 vector<indexSweepLineEvent*> *events;
00103 bool indexBuilt;
00104
00105 int nOverlaps;
00111 void buildIndex();
00112 void processOverlaps(int start,int end,SweepLineInterval *s0,SweepLineOverlapAction *action);
00113 };
00114
00115 bool isleLessThen(indexSweepLineEvent *first,indexSweepLineEvent *second);
00116 }
00117
00118 #endif
00119