学步园

      在GIS中，我们会经常碰到最小外包矩形，MBR。最小外包矩形就是包围图元，并且平行于X轴和Y轴的最小外界矩形。到底这个矩形有什么用，设想一下，一个几何体有很多顶点，我们要判断一个图形是否包含另一个图形，就要一个个点点判断，这样为大大延长处理的时间。那如果是针对矩形的判断将会见的很多。又比如在空间索引中，作为几何体图形的近似可以加快索引处理的时间。在空间查询中，例如要查找离我当前位置周围最近的几个餐厅。如果没有做空间所以，当然也行，暴力法一个个测试，直到找出所有符合条件的餐厅。有了这个MBR作为索引数据的近似，那么查询的速度也会加快，只不过在创建索引的时候要花一些时间而已。

        既然这个MBR如此重要，本人在之前的代码上不断改进，终于拿出一个比较稳定的版本的最小外包矩形的代码。在此奉献给大家，希望各位也能提出代码中的问题。

头文件如下：

#include <math.h>

#include <algorithm>

using namespace std;

class GEOMETRY_API GeoEnvelope
{
public:
	//默认构造函数
	GeoEnvelope();
	//带参数的构造函数
	GeoEnvelope(double minX,double maxX,double minY,double maxY);
	//拷贝构造函数
	GeoEnvelope(const GeoEnvelope& envelope);
	//用两个坐标点初始化
	GeoEnvelope(GeoCoordinate *coord1,GeoCoordinate *coord2);

	virtual ~GeoEnvelope(void);

	//判断两个最小外包矩形是否相交(计算出在内还在外)
	int InterSects(const GeoEnvelope & otherEvp);
	// 判断矩形是否为空
	bool IsNull(void) const;

	// 获取最小外包矩形的宽度
	double GetWidth(void);

	// 获取最小外界矩形的高度
	double GetHeight(void);

	// 获得矩形的中心点坐标
	GeoCoordinate * Center() const;

	//测试是否包含另一个MBR
	bool Contains(const GeoEnvelope &env);

	//判断一个点是否在该矩形中
	bool Contains(const GeoCoordinate &pt);

	//判断一个点是否在矩形内
	bool IsPointInRect(double x,double y);

	//计算两个矩形相交的部分
	GeoEnvelope* Intersection(const GeoEnvelope& env);

	//计算到另一个MBR的距离
	double DistanceTo(GeoEnvelope &env);

	//计算面积
	double Area();

	//计算周长
	double Perimeter();

	//是否包含这个点
	bool Contains(double x, double y) const;

	//静态函数

	//判断p1,p2构成的矩形和q1,q2构成的矩形是否相交
	static bool Intersects(GeoCoordinate &p1, GeoCoordinate &p2, GeoCoordinate &q1, GeoCoordinate &q2);

public:
	double minX;	//最小外包矩形的最小x值
	double maxX;	//最小外包矩形的最大x值
	double minY;	//最小外包矩形的最小y值
	double maxY;	//最小外包矩形的最大y值
};

实现文件如下所示：

#include "GeoEnvelope.h"

GeoEnvelope::GeoEnvelope()
{
	minX = 0;
	minY = -2;
	maxX = 0;
	maxY = -2;
}

//带参数的构造函数
GeoEnvelope::GeoEnvelope(double minX,double maxX,double minY,double maxY)
{
	//先要比较坐标大小，然后再进行判断
	if (minX > maxX)
	{
		this->minX = maxX;
		this->maxX = minX;
	}
	else
	{
		this->minX = minX;
		this->maxX = maxX;
	}

	if (minY > maxY)
	{
		this->minY = maxY;
		this->maxY = minY;
	}
	else
	{
		this->minY = minY;
		this->maxY = maxY;
	}
}

//拷贝构造函数
GeoEnvelope::GeoEnvelope(const GeoEnvelope& envelope)
{
	this->minX = envelope.minX;
	this->maxX = envelope.maxX;
	this->minY = envelope.minY;
	this->maxY = envelope.maxY;
}

//用两个坐标点初始化
GeoEnvelope::GeoEnvelope(GeoCoordinate *coord1,GeoCoordinate *coord2)
{
	if (coord1->x < coord2->x)
	{
		minX = coord1->x;
		maxX = coord2->x;
	}
	else
	{
		minX = coord2->x;
		maxX = coord1->x;
	}

	if (coord1->y < coord2->y)
	{
		minY = coord1->y;
		maxY = coord2->y;
	}
	else
	{
		minY = coord2->y;
		maxY = coord1->y;
	}
}

//析构函数
GeoEnvelope::~GeoEnvelope(void)
{
}

int GeoEnvelope::InterSects(const GeoEnvelope & otherEvp)
{
	//上下左右四个方向
	if (maxX < otherEvp.minX || minX > otherEvp.maxX ||
		maxY < otherEvp.minY || minY > otherEvp.maxY)
	{
		return 0;
	}

	//四个对角方向
	if (maxX < otherEvp.minX && maxY < otherEvp.minY)
	{
		return 0;
	}
	if (maxX < otherEvp.minX && minY > otherEvp.maxY)
	{
		return 0;
	}

	//在矩形内
	if (minX >= otherEvp.minX && maxX <= otherEvp.maxX &&
		minY >= otherEvp.minY && maxY <= otherEvp.maxY)
	{
		return 1;
	}
	
	return 2;	//相交
}

// 判断矩形是否为空
bool GeoEnvelope::IsNull(void) const
{
	if (maxX < minX || maxY < minY)
	{
		return false;
	} 
	return true;
}

// 获取最小外包矩形的宽度
double GeoEnvelope::GetWidth(void)
{
	if (IsNull())
	{
		return 0;
	}
	return fabs(maxX - minX);
}

// 获取最小外界矩形的高度
double GeoEnvelope::GetHeight(void)
{
	if (IsNull())
	{
		return 0;
	}
	return fabs(maxY - minY);
}

// 获得矩形的中心点坐标
GeoCoordinate * GeoEnvelope::Center() const
{
	if (IsNull())
	{
		return NULL;
	}

	return new GeoCoordinate((minX+maxX)/2,
		(minY+maxY)/2);
}

//测试是否包含另一个MBR
bool GeoEnvelope::Contains(const GeoEnvelope &env)
{
	if (IsNull() || env.IsNull())
	{
		return false;
	}
	return env.minX > minX &&
		env.maxX < maxX &&
		env.minY > minY &&
		env.maxY < maxY;
}

//判断一个点是否在该矩形中
bool GeoEnvelope::Contains(const GeoCoordinate &pt)
{
	if (IsNull())
	{
		return false;
	}

	if (pt.x > minX && pt.x < maxX && pt.y > minY && pt.y < maxY)
	{
		return 1;
	}
	return 0;
}

//在矩形外返回0，否则返回1
bool GeoEnvelope::IsPointInRect(double x,double y)
{
	if (IsNull())
	{
		return false;
	}

	if (x > minX && x < maxX && y > minY && y < maxY)
	{
		return 1;
	}
	return 0;
}

//计算两个矩形相交的部分
GeoEnvelope* GeoEnvelope::Intersection(const GeoEnvelope& env)
{
	if (IsNull() || env.IsNull() || ! InterSects(env)) return new GeoEnvelope();

	double intMinX = minX > env.minX ? minX : env.minX;
	double intMinY = minY > env.minY ? minY : env.minY;
	double intMaxX = maxX < env.maxX ? maxX : env.maxX;
	double intMaxY = maxY < env.maxY ? maxY : env.maxY;
	return new GeoEnvelope(intMinX, intMaxX, intMinY, intMaxY);
}

//计算到另一个MBR的距离
double GeoEnvelope::DistanceTo(GeoEnvelope &env)
{
	//如果相交，距离则为0
	if (InterSects(env))
	{
		return 0;
	}
	double dx = 0;
	if (maxX < env.minX)
	{
		dx = env.minX - maxX;
	}
	if (minX > env.maxX)
	{
		dx = minX - env.maxX;
	}

	double dy = 0;
	if (maxY < env.minY)
	{
		dy = env.minY - maxY;
	}
	if (minY > env.maxY)
	{
		dy = minY - env.maxY;
	}

	//如果其中之一为0，则计算水平或者垂直距离
	if (0.0 == dx)
	{
		return dy;
	}
	if (0.0 == dy)
	{
		return dx;
	}
	return sqrt(dx*dx + dy*dy);
}

//计算面积
double GeoEnvelope::Area()
{
	if (IsNull())
	{
		return 0;
	}
	return GetHeight()*GetWidth();
}

//计算周长
double GeoEnvelope::Perimeter()
{
	if (IsNull())
	{
		return 0;
	}
	return GetWidth()*2 + GetHeight()*2;
}

//测试是否包含
bool GeoEnvelope::Contains(double x, double y) const
{
	if (IsNull()) 
		return false;

	return x >= minX &&
		x <= maxX &&
		y >= minY &&
		y <= maxY;
}

//判断p1,p2构成的矩形和q1,q2构成的矩形是否相交
bool GeoEnvelope::Intersects(GeoCoordinate &p1, GeoCoordinate &p2, GeoCoordinate &q1, GeoCoordinate &q2)
{
	double minq = min(q1.x, q2.x);
	double maxq = max(q1.x, q2.x);
	double minp = min(p1.x, p2.x);
	double maxp = max(p1.x, p2.x);

	if( minp > maxq )
		return false;
	if( maxp < minq )
		return false;

	minq = min(q1.y, q2.y);
	maxq = max(q1.y, q2.y);
	minp = min(p1.y, p2.y);
	maxp = max(p1.y, p2.y);

	if( minp > maxq )
		return false;
	if( maxp < minq )
		return false;
	return true;
}

代码经过测试，希望对大家有用。