indexSweepline.h

00001 /**********************************************************************
00002  * $Id: indexSweepline.h,v 1.2.4.1 2006/04/03 11:05:05 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.4.1  2006/04/03 11:05:05  strk
00017  * Back-ported DELETE=>DELETE_ENVENT and INSERT=>INSERT_EVENT
00018  * labels rename for SweepLineEvent classes.
00019  *
00020  * Revision 1.2  2004/07/19 13:19:31  strk
00021  * Documentation fixes
00022  *
00023  * Revision 1.1  2004/07/02 13:20:42  strk
00024  * Header files moved under geos/ dir.
00025  *
00026  * Revision 1.5  2003/11/07 01:23:42  pramsey
00027  * Add standard CVS headers licence notices and copyrights to all cpp and h
00028  * files.
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; // null if this is an INSERT event
00087         int deleteEventIndex;
00088         SweepLineInterval *sweepInt;
00089 };
00090 
00091 /*
00092  * A sweepline implements a sorted index on a set of intervals.
00093  * It is used to compute all overlaps between the interval in the index.
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         // statistics information
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 

Generated on Fri Sep 14 20:01:01 2007 for GEOS by  doxygen 1.5.1