dtin.cpp

生成tin

#include "stdafx.h"
#include "stdio.h"
#include "dtin.h"
#include "base.h"
#include <math.h>
#define _DTIN_ZERO (1.0e-8)
inline float Distance(const DiscretePoint& p1,
					  const DiscretePoint& p2)
{
	return sqrtf((p1.x - p2.x) * (p1.x - p2.x)
		+ (p1.y - p2.y) * (p1.y - p2.y));
}
inline float CalculateS(const DiscretePoint& P1,
						const DiscretePoint& P2,
						const DiscretePoint& P3)
{
    return fabsf((P1.x - P3.x) * (P2.y - P3.y)
		- (P2.x - P3.x) * (P1.y - P3.y));
}
inline int Direction(const DiscretePoint& P0,
					 const DiscretePoint& P1,
					 const DiscretePoint& P2)
{
	float f = (P0.y-P1.y)*(P2.x-P1.x)
		- (P0.x-P1.x)*(P2.y-P1.y);
	if(f < 0)	return -1;		//左侧
	else if(f == 0)return 0;	//线上
	else return 1;				//右侧
}
inline bool IsPointInRect(const DiscretePoint& P0,
						  const DiscretePoint& P1,
						  const DiscretePoint& P2)
{
	if(((P0.x >= P1.x && P0.x <= P2.x) ||
		(P0.x <= P1.x && P0.x >= P2.x))
		&&((P0.y >= P1.y && P0.y <= P2.y) ||
		(P0.y <= P1.y && P0.x >= P2.y)))
		return true;
	return false;
}
int IsPointInConvex(const DiscretePoint& point,
					const vector<DiscretePoint>& convex)
{
	int n = convex.size();
	int t=(point.y-convex[n-1].y)*(convex[0].x-convex[n-1].x)		
		-(point.x-convex[n-1].x)*(convex[0].y-convex[n-1].y);
	if(t == 0)
	{
		if(IsPointInRect(point,convex[n-1],convex[0]))
		{
			return 0;
		}
		else
		{
			return -1;
		}
	}
	bool Order = (t > 0);
	for(int i=0;i<n-1;i++)
	{
		t=(point.y-convex[i].y)*(convex[i+1].x-convex[i].x)
			-(point.x-convex[i].x)*(convex[i+1].y-convex[i].y);
		if(t == 0)
		{
			if(IsPointInRect(point,convex[n-1],convex[0]))
			{
				return 0;
			}
			else
			{
				return -1;
			}
		}
		else if(Order != (t > 0))
		{
			return -1;
		}
	}
	return 1;
}
bool CircumCircleCenter(DiscretePoint& center,
						const DiscretePoint& p1,
						const DiscretePoint& p2,
						const DiscretePoint& p3)
{
	float f1 = 2.0f*((p2.x-p1.x)*(p1.y-p3.y)-(p3.x-p1.x)*(p1.y-p2.y));
	if(fabsf(f1)<=_DTIN_ZERO)	return false;
	center.x = ((p1.y-p3.y)*((p2.x-p1.x)*(p2.x+p1.x)+(p2.y-p1.y)*(p2.y+p1.y))
			+(p1.y-p2.y)*((p1.x-p3.x)*(p1.x+p3.x)+(p1.y-p3.y)*(p1.y+p3.y)))/f1;
	center.y = ((p1.x-p3.x)*((p2.y-p1.y)*(p2.y+p1.y)+(p2.x-p1.x)*(p2.x+p1.x))
			+(p1.x-p2.x)*((p1.y-p3.y)*(p1.y+p3.y)+(p1.x-p3.x)*(p1.x+p3.x)))/-f1;
	return true;
}
int Find(float x,float y,const vector<DiscretePoint>& point)
{
	for(int i=point.size()-1;i>=0;i--)
	{
		if(point[i].x == x && point[i].y == y)
		{
			return i;
		}
	}
	return -1;
}
void Voronoi(vector<_Polygon>& voronoi,DTriangular& dt)
{
	voronoi.clear();
	vector<bool> bInConvex(dt.m_point.size());
	for(int i=dt.m_point.size()-1;i>=0;i--)
	{
		bInConvex[i] = false;
	}
	for(i=dt.m_convex.size()-1;i>=0;i--)
	{
		bInConvex[dt.m_convex[i].index] = true;
	}
	for(i=dt.m_point.size()-1;i>=0;i--)
	{
		if(!bInConvex[i])
		{
			vector<DiscretePoint> vertex;
			int k;
			for(int j=dt.m_edge.size()-1;j>=0;j--)
			{
				if(dt.m_edge[j].start == i)
				{
					k = dt.m_edge[j].RightTriangle;
					break;
				}
				if(dt.m_edge[j].end == i)
				{
					k = dt.m_edge[j].LeftTriangle;
					break;
				}
			}
			do{				
				vertex.push_back(dt.m_center[k]);
				for(int l=0;l<3;l++)
				{
					int m = dt.m_triangle[k]._Edge[l];
					if(m != j)
					{
						if(dt.m_edge[m].start == i)
						{
							k = dt.m_edge[m].RightTriangle;
							j = m;
							break;
						}
						if(dt.m_edge[m].end == i)
						{
							k = dt.m_edge[m].LeftTriangle;
							j = m;
							break;
						}
					}					
				}
			}while(k != vertex[0].index);
			_Polygon pg;
			pg.m_vertex = vertex;
			voronoi.push_back(pg);
		}
	}
}
void Draw(CDC* pDC,const vector<_Polygon>& vor)
{
	CPen pen;
	pen.CreatePen(PS_DOT,1,RGB(255,0,0));
	CPen* pOldPen = pDC->SelectObject(&pen);
	for(int i=vor.size()-1;i>=0;i--)
	{
		int k = vor[i].m_vertex.size();
		pDC->MoveTo(vor[i].m_vertex[k-1].x,vor[i].m_vertex[k-1].y);
		for(int j=0;j<k;j++)
		{
			pDC->LineTo(vor[i].m_vertex[j].x,vor[i].m_vertex[j].y);
		}
	}
	pDC->SelectObject(pOldPen);
}
void DTriangular::Convex()
{
	int n = m_point.size();
	int xmaxID,ymaxID,xminID,yminID;
	xmaxID = ymaxID = xminID = yminID = 0;
	for(int i = 1;i < n;i++)
	{
		if(m_point[xmaxID].x < m_point[i].x)
		{
			xmaxID = i;
		}
		else if(m_point[xminID].x > m_point[i].x)
		{
			xminID = i;
		}
		if(m_point[ymaxID].y < m_point[i].y)
		{
			ymaxID = i;
		}
		else if(m_point[yminID].y > m_point[i].y)
		{
			yminID = i;
		}
	}
	m_convex.clear();
	m_convex.push_back(m_point[xminID]);
	m_convex.push_back(m_point[ymaxID]);
	m_convex.push_back(m_point[xmaxID]);
	m_convex.push_back(m_point[yminID]);
	vector<TempEdge> OutEdge;
	OutEdge.push_back(TempEdge(xminID,ymaxID));
	OutEdge.push_back(TempEdge(ymaxID,xmaxID));
	OutEdge.push_back(TempEdge(xmaxID,yminID));
	OutEdge.push_back(TempEdge(yminID,xminID));
	if(yminID == xminID)
	{
		m_convex.erase(m_convex.begin()+3);
		OutEdge.erase(OutEdge.begin()+3);
	}	
	if(xmaxID == yminID)
	{
		m_convex.erase(m_convex.begin()+2);
		OutEdge.erase(OutEdge.begin()+2);
	}	
	if(ymaxID == xmaxID)
	{
		m_convex.erase(m_convex.begin()+1);
		OutEdge.erase(OutEdge.begin()+1);
	}	
	if(xminID == ymaxID)
	{
		m_convex.erase(m_convex.begin());
		OutEdge.erase(OutEdge.begin());
	}

	vector<bool> PtOut(n);
	for(i=0;i<n;i++) PtOut[i] = false;
	for(i = 0;i < n;i++)
	{
		if(i != xmaxID && i != xminID && i != ymaxID && i != yminID 
			&& (OutEdge.size() <=2 || IsPointInConvex(m_point[i],m_convex) <= 0))
		{
			PtOut[i] = true;
		}
	}
	for(i=0;i<4;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(PtOut[j]	&& Direction(m_point[j],
				m_point[OutEdge[i].start],m_point[OutEdge[i].end]) >= 0)
			{
				OutEdge[i].m_vertex.push_back(j);
				PtOut[j] = false;
			}
		}
	}
	bool bNewPt = true;	
	while(bNewPt)
	{
		int m = OutEdge.size();
		bNewPt = false;
		for(i=0;i<m;i++)
		{
			float maxs = -1;
			int maxID;
			int l = OutEdge[i].m_vertex.size();
			for(int j=0;j<l;j++)//找加如后使新加入三角形面积最大点
			{
				float s = CalculateS(m_point[OutEdge[i].m_vertex[j]],
					m_point[OutEdge[i].start],m_point[OutEdge[i].end]);
				if(maxs < s)
				{
					maxs = s;
					maxID = OutEdge[i].m_vertex[j];
				}
			}
			if( maxs >= 0 )	//有新加入点
			{
				OutEdge.insert(OutEdge.begin()+i+1,TempEdge(OutEdge[i].start,maxID));
				OutEdge.insert(OutEdge.begin()+i+2,TempEdge(maxID,OutEdge[i].end));
				m_convex.insert(m_convex.begin()+i+1,m_point[maxID]);
				for(int k=0;k<l;k++)
				{
					if(OutEdge[i].m_vertex[k] != maxID)
					{
						if(Direction(m_point[OutEdge[i].m_vertex[k]],
							m_point[OutEdge[i].start],m_point[maxID]) >= 0)
						{
							OutEdge[i+1].m_vertex.push_back(OutEdge[i].m_vertex[k]);
						}
						else if(Direction(m_point[OutEdge[i].m_vertex[k]],
							m_point[maxID],m_point[OutEdge[i].end]) >= 0)
						{
							OutEdge[i+2].m_vertex.push_back(OutEdge[i].m_vertex[k]);
						}
					}
				}
				OutEdge.erase(OutEdge.begin()+i);
				bNewPt = true;
			}
		}
	}
}
void DTriangular::ConvexTriangular()
{
	m_triangle.clear();
	m_center.clear();
	m_radius.clear();
	Triangle t;
	DiscretePoint center;
	float radius;
	vector<DiscretePoint> convex = m_convex;
	int n = convex.size();
	while(n > 3)
	{
		for(int i=0;i<n;i++)
		{
			if(CircumCircleCenter(center,
				convex[i],convex[(i+1)%n],convex[(i+2)%n]))
			{
				bool bSuccess = true;
				radius = Distance(convex[i],center);
				for(int j = (i+3)%n;j != i;j = (j+1)%n)
				{
					float dist = Distance(convex[j],center);
					if((dist - radius) <= _DTIN_ZERO)
					{
						bSuccess = false;
						break;						
					}
				}
				if(bSuccess)
				{					
					t.Node[0] = convex[i].index;
					t.Node[1] = convex[(i+1)%n].index;
					t.Node[2] = convex[(i+2)%n].index;
					m_triangle.push_back(t);
					m_center.push_back(center);
					m_radius.push_back(radius);
					if(convex.begin()+i+1  == convex.end())
					{
						convex.erase(convex.begin());
					}
					else
					{
						convex.erase(convex.begin()+i+1);
					}
					break;
				}
			}
		}
		n = convex.size();
	}
	t.Node[0] = convex[0].index;
	t.Node[1] = convex[1].index;
	t.Node[2] = convex[2].index;
	CircumCircleCenter(center,convex[0],convex[1],convex[2]);
	radius = Distance(center,convex[0]);
	m_triangle.push_back(t);
	m_center.push_back(center);
	m_radius.push_back(radius);
}

int Find(int& s,int& e,const vector<EdgeID>& edge)
{
	if(s > e)	swap(s,e);
	for(int i=edge.size()-1;i>=0;i--)
	{
		if(edge[i].start == s && edge[i].end == e)
		{
			return i;
		}
	}
	return -1;
}
void DTriangular::InsertPoint(const DiscretePoint& point)
{
	Triangle tri;
	DiscretePoint center;
	float radius;
	vector<EdgeID> edge;
	for(int i=m_triangle.size()-1;i>=0;i--)
	{
		if(Distance(point,m_center[i]) < m_radius[i])
		{
			for(int j=0;j<3;j++)
			{
				int s = m_triangle[i].Node[j];
				int e = m_triangle[i].Node[(j+1)%3];
				if(s > e) swap(s,e);
				InsertOrErase(EdgeID(s,e),edge);
			}			
			m_triangle.erase(m_triangle.begin()+i);
			m_center.erase(m_center.begin()+i);
			m_radius.erase(m_radius.begin()+i);
		}
	}
	for(i=edge.size()-1;i>=0;i--)
	{
		tri.Node[0] = point.index;
		tri.Node[1] = edge[i].start;
		tri.Node[2] = edge[i].end;
		CircumCircleCenter(center,m_point[tri.Node[0]],
			m_point[tri.Node[1]],m_point[tri.Node[2]]);
		radius = Distance(center,m_point[tri.Node[0]]);
		m_triangle.push_back(tri);
		m_center.push_back(center);
		m_radius.push_back(radius);
	}
}
void DTriangular::InsertAllPoints()
{
	vector<bool> bInConvex(m_point.size());
	for(int i=m_point.size()-1;i>=0;i--)
	{
		bInConvex[i] = false;
	}
	for(i=m_convex.size()-1;i>=0;i--)
	{
		bInConvex[m_convex[i].index] = true;
	}
	for(i=m_point.size()-1;i>=0;i--)
	{
		if(!bInConvex[i])
		{
			InsertPoint(m_point[i]);
		}
	}
}
void DTriangular::Index()
{
	m_edge.clear();
	Edge e;
	int index = 0;
	for(int i = m_triangle.size()-1;i>=0;i--)
	{
		m_triangle[i].index = i;
		for(int j=0;j<3;j++)
		{
			e.start = m_triangle[i].Node[j];
			e.end = m_triangle[i].Node[(j+1)%3];
			e.index = index;
			if(e.start > e.end)
				swap(e.start,e.end);
			Insert(e,m_edge);
		}
	}
	for(i = m_edge.size()-1;i>=0;i--)
	{
		m_edge[i].index = i;
		m_edge[i].LeftTriangle = -1;
		m_edge[i].RightTriangle = -1;
	}
	for(i = m_triangle.size()-1;i>=0;i--)
	{
		for(int j=0;j<3;j++)
		{
			e.start = m_triangle[i].Node[j];
			e.end = m_triangle[i].Node[(j+1)%3];
			if(e.start > e.end)
				swap(e.start,e.end);
			int k = Find(e,m_edge);
			for(int l=0;l<3;l++)
			{
				if(m_triangle[i].Node[l] != e.start
					&& m_triangle[i].Node[l] != e.end)
					break;
			}
			if(Direction(m_point[m_triangle[i].Node[l]],
				m_point[e.start],m_point[e.end]) == 1)
				m_edge[k].RightTriangle = i;
			else
				m_edge[k].LeftTriangle = i;
		}
	}
	for(i=m_triangle.size()-1;i>=0;i--)
	{
		m_triangle[i]._Edge.clear();
	}
	for(i=m_edge.size()-1;i>=0;i--)
	{
		int k = m_edge[i].LeftTriangle;
		if(m_edge[i].LeftTriangle != -1)
			m_triangle[k]._Edge.push_back(m_edge[i].index);
		k = m_edge[i].RightTriangle;
		if(k != -1)
			m_triangle[k]._Edge.push_back(m_edge[i].index);
	}
	for(i=m_center.size()-1;i>=0;i--)
	{
		m_center[i].index = i;
	}
}
void DTriangular::Draw(CDC* pDC)
{
	CPen pen;
	pen.CreatePen(PS_SOLID,1,RGB(0,0,255));
	CPen* pOldPen = pDC->SelectObject(&pen);
	for(int i=m_edge.size()-1;i>=0;i--)
	{	
		pDC->MoveTo(m_point[m_edge[i].start].x,m_point[m_edge[i].start].y);
		pDC->LineTo(m_point[m_edge[i].end].x,m_point[m_edge[i].end].y);
	//	int x = (m_point[m_edge[i].start].x + m_point[m_edge[i].end].x) / 2;
	//	int y = (m_point[m_edge[i].start].y + m_point[m_edge[i].end].y) / 2;
	//	CString str;
	//	str.Format("%d,%d",m_edge[i].LeftTriangle+1,m_edge[i].RightTriangle+1);
	//	str.Format("%d",m_edge[i].index);
	//	pDC->TextOut(x,y,str);		
	}
	/*
	for(i = m_point.size()-1;i >= 0;i--)
	{
		CRect rect;
		rect.left = m_point[i].x-10;
		rect.right = m_point[i].x+10;
		rect.bottom = m_point[i].y+10;
		rect.top = m_point[i].y-10;
		pDC->Rectangle(&rect);
		CString s;
		s.Format("%d",i+1);
		pDC->TextOut(m_point[i].x-8,m_point[i].y-8,s);
		pDC->SetPixel(m_point[i].x,m_point[i].y,RGB(255,0,0));
	}
	for(i=m_triangle.size()-1;i>=0;i--)
	{
		int x = 0;
		int y = 0;
		for(int j=0;j<3;j++)
		{
			x += m_point[m_triangle[i].Node[j]].x;
			y += m_point[m_triangle[i].Node[j]].y;
		}
		x /= 3,y /= 3;
		CString str;
	//	str.Format("%d",i+1);
		str.Format("%d,%d,%d",m_triangle[i]._Edge[0],
		m_triangle[i]._Edge[1],m_triangle[i]._Edge[2]);
		pDC->TextOut(x,y,str);
	}*/
	pDC->SelectObject(pOldPen);
}
bool DTriangular::LButtonDown(long x,long y)
{
	if(Find((float)x,(float)y,m_point) < 0)
	{
		DiscretePoint point((float)x,(float)y,m_point.size());
		m_point.push_back(point);
		if(m_point.size() > 2)
		{
			if(m_point.size() > 3 
			&& IsPointInConvex(point,m_convex) == 1)
			{
				InsertPoint(point);
			}		
			else
			{	
				Convex();
				ConvexTriangular();
				InsertAllPoints();
			}
			Index();
			return true;
		}
	}
	return false;
}
bool DTriangular::RButtonDown(long x,long y)
{	
	m_point.clear();
	m_convex.clear();
	m_edge.clear();
	m_triangle.clear();
	m_center.clear();
	m_radius.clear();
	return true;
}