indexsweepline.h

一个很好的vc代码

/**********************************************************************
 * $Id: indexSweepline.h,v 1.2 2004/07/19 13:19:31 strk Exp $
 *
 * GEOS - Geometry Engine Open Source
 * http://geos.refractions.net
 *
 * Copyright (C) 2001-2002 Vivid Solutions Inc.
 *
 * This is free software; you can redistribute and/or modify it under
 * the terms of the GNU Lesser General Public Licence as published
 * by the Free Software Foundation. 
 * See the COPYING file for more information.
 *
 **********************************************************************
 * $Log: indexSweepline.h,v $
 * Revision 1.2  2004/07/19 13:19:31  strk
 * Documentation fixes
 *
 * Revision 1.1  2004/07/02 13:20:42  strk
 * Header files moved under geos/ dir.
 *
 * Revision 1.5  2003/11/07 01:23:42  pramsey
 * Add standard CVS headers licence notices and copyrights to all cpp and h
 * files.
 *
 *
 **********************************************************************/


#ifndef GEOS_INDEXSWEEPLINE_H
#define GEOS_INDEXSWEEPLINE_H

#include <memory>
#include <vector>
#include <geos/platform.h>

using namespace std;

namespace geos {

class SweepLineInterval {
public:
	SweepLineInterval(double newMin, double newMax);
	SweepLineInterval(double newMin, double newMax, void* newItem);
	double getMin();
	double getMax();
	void* getItem();
private:
	double min, max;
	void* item;
};

class SweepLineOverlapAction {
public:
	virtual void overlap(SweepLineInterval *s0,SweepLineInterval *s1)=0;
};

class indexSweepLineEvent {
public:
	enum {
		INSERT = 1,
		DELETE
	};
	indexSweepLineEvent(double x,indexSweepLineEvent *newInsertEvent,SweepLineInterval *newSweepInt);
	bool isInsert();
	bool isDelete();
	indexSweepLineEvent* getInsertEvent();
	int getDeleteEventIndex();
	void setDeleteEventIndex(int newDeleteEventIndex);
	SweepLineInterval* getInterval();
	/**
	* ProjectionEvents are ordered first by their x-value, and then by their eventType.
	* It is important that Insert events are sorted before Delete events, so that
	* items whose Insert and Delete events occur at the same x-value will be
	* correctly handled.
	*/
	int compareTo(indexSweepLineEvent *pe);
	int compareTo(void *o);
private:
	double xValue;
	int eventType;
	indexSweepLineEvent *insertEvent; // null if this is an INSERT event
	int deleteEventIndex;
	SweepLineInterval *sweepInt;
};

/*
 * A sweepline implements a sorted index on a set of intervals.
 * It is used to compute all overlaps between the interval in the index.
 */
class SweepLineIndex {
public:
	SweepLineIndex();
	~SweepLineIndex();
	void add(SweepLineInterval *sweepInt);
	void computeOverlaps(SweepLineOverlapAction *action);
private:
    vector<indexSweepLineEvent*> *events;
	bool indexBuilt;
	// statistics information
	int nOverlaps;
	/**
	* Because Delete Events have a link to their corresponding Insert event,
	* it is possible to compute exactly the range of events which must be
	* compared to a given Insert event object.
	*/
	void buildIndex();
	void processOverlaps(int start,int end,SweepLineInterval *s0,SweepLineOverlapAction *action);
};

bool isleLessThen(indexSweepLineEvent *first,indexSweepLineEvent *second);
}

#endif