indexSweepline.h

00001 /**********************************************************************
00002  * $Id: indexSweepline.h,v 1.2 2004/07/19 13:19:31 strk Exp $
00003  *
00004  * GEOS - Geometry Engine Open Source
00005  * http://geos.refractions.net
00006  *
00007  * Copyright (C) 2001-2002 Vivid Solutions Inc.
00008  *
00009  * This is free software; you can redistribute and/or modify it under
00010  * the terms of the GNU Lesser General Public Licence as published
00011  * by the Free Software Foundation. 
00012  * See the COPYING file for more information.
00013  *
00014  **********************************************************************
00015  * $Log: indexSweepline.h,v $
00016  * Revision 1.2  2004/07/19 13:19:31  strk
00017  * Documentation fixes
00018  *
00019  * Revision 1.1  2004/07/02 13:20:42  strk
00020  * Header files moved under geos/ dir.
00021  *
00022  * Revision 1.5  2003/11/07 01:23:42  pramsey
00023  * Add standard CVS headers licence notices and copyrights to all cpp and h
00024  * files.
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; // null if this is an INSERT event
00083         int deleteEventIndex;
00084         SweepLineInterval *sweepInt;
00085 };
00086 
00087 /*
00088  * A sweepline implements a sorted index on a set of intervals.
00089  * It is used to compute all overlaps between the interval in the index.
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         // statistics information
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 

Generated on Wed Jun 21 21:27:24 2006 for GEOS by  doxygen 1.4.6