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 #ifndef GEOS_INDEXSWEEPLINE_H
00031 #define GEOS_INDEXSWEEPLINE_H
00032
00033 #include <memory>
00034 #include <vector>
00035 #include <geos/platform.h>
00036
00037 using namespace std;
00038
00039 namespace geos {
00040
00041 class SweepLineInterval {
00042 public:
00043 SweepLineInterval(double newMin, double newMax);
00044 SweepLineInterval(double newMin, double newMax, void* newItem);
00045 double getMin();
00046 double getMax();
00047 void* getItem();
00048 private:
00049 double min, max;
00050 void* item;
00051 };
00052
00053 class SweepLineOverlapAction {
00054 public:
00055 virtual void overlap(SweepLineInterval *s0,SweepLineInterval *s1)=0;
00056 };
00057
00058 class indexSweepLineEvent {
00059 public:
00060 enum {
00061 INSERT = 1,
00062 DELETE
00063 };
00064 indexSweepLineEvent(double x,indexSweepLineEvent *newInsertEvent,SweepLineInterval *newSweepInt);
00065 bool isInsert();
00066 bool isDelete();
00067 indexSweepLineEvent* getInsertEvent();
00068 int getDeleteEventIndex();
00069 void setDeleteEventIndex(int newDeleteEventIndex);
00070 SweepLineInterval* getInterval();
00077 int compareTo(indexSweepLineEvent *pe);
00078 int compareTo(void *o);
00079 private:
00080 double xValue;
00081 int eventType;
00082 indexSweepLineEvent *insertEvent;
00083 int deleteEventIndex;
00084 SweepLineInterval *sweepInt;
00085 };
00086
00087
00088
00089
00090
00091 class SweepLineIndex {
00092 public:
00093 SweepLineIndex();
00094 ~SweepLineIndex();
00095 void add(SweepLineInterval *sweepInt);
00096 void computeOverlaps(SweepLineOverlapAction *action);
00097 private:
00098 vector<indexSweepLineEvent*> *events;
00099 bool indexBuilt;
00100
00101 int nOverlaps;
00107 void buildIndex();
00108 void processOverlaps(int start,int end,SweepLineInterval *s0,SweepLineOverlapAction *action);
00109 };
00110
00111 bool isleLessThen(indexSweepLineEvent *first,indexSweepLineEvent *second);
00112 }
00113
00114 #endif
00115