www.pudn.com > Poly.rar > SortPoly.cpp
// SortPoly.cpp: implementation of the CSortPoly class.
//
//////////////////////////////////////////////////////////////////////
#include "stdafx.h"
#include "PolyTop.h"
#include "SortPoly.h"
#include "math.h"
#ifdef _DEBUG
#undef THIS_FILE
static char THIS_FILE[]=__FILE__;
#define new DEBUG_NEW
#endif
const float PI = acos(-1);
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
CSortPoly::CSortPoly()
{
InitData();
}
CSortPoly::~CSortPoly()
{
}
/**********************************************************************************
*函数名称： ReadFile
*函数功能： 用来求解由点和线围成的多边形
*参数信息： filepath所读取文件的路径名称
*返回值： 成功：true；失败：false
*作者：
*完成时间： 2006.12.17
***********************************************************************************/
bool CSortPoly::ReadFile(CString filepath)
{
FILE* fp = NULL;
fp = fopen( filepath, "r" );
if ( fp == NULL )
{
AfxMessageBox( "Error Opening File!" );
return false;
}
fscanf( fp, "%d", &m_nNumberOfPoints );
Point pt;
for ( int i = 0; i < m_nNumberOfPoints; ++i )
{
fscanf( fp, "%d %d %d", &(pt.num), &(pt.x), &(pt.y) );
m_vPoints.push_back( pt );
}
fscanf( fp, "%d", &m_nNumberOfLines );
Line ln;
for ( i = 0; i < m_nNumberOfLines; ++i )
{
fscanf( fp, "%d %d %d", &(ln.num), &(ln.start), &(ln.end) );
m_vLines.push_back( ln );
}
int num;
while ( fscanf( fp, "%d", &num) != EOF )
{
m_sOuterPoints.push_back( num );
}
fclose( fp );
CalUsedTimesOfPoints();
return true;
}
/**********************************************************************************
*函数名称： CalUsedTimesOfPoints
*函数功能： 计算与某个点相连的点的所有信息，结果保存在m_vConnectedPoints中。
*参数信息： 无
*返回值： 无
*作者：
*完成时间： 2006.12.17
***********************************************************************************/
void CSortPoly::CalUsedTimesOfPoints()
{
int *num = NULL;
num = new int [ m_nNumberOfPoints ];
memset( num, 0, sizeof( int ) * m_nNumberOfPoints );
lineList::iterator iter = m_vLines.begin();
for ( ; iter < m_vLines.end(); ++iter )
{
num[ (*iter).start - 1]++;
num[ (*iter).end - 1 ]++;
}
ConnectedPoints ut;
for ( int i = 0; i < m_nNumberOfPoints; ++i )
{
ut.num = i+1;
intList templist;
templist.clear();
for ( iter = m_vLines.begin(); iter != m_vLines.end(); ++iter )
{
if ( (*iter).start == ( i + 1 ) )
templist.push_back( (*iter).end );
if ( (*iter).end == ( i + 1 ) )
templist.push_back( (*iter).start );
}
ut.m_sPoints = templist;
m_vConnectedPoints.push_back( ut );
}
delete num;
}
/**********************************************************************************
*函数名称： AngleOfTwoLines
*函数功能： 计算两条直线顺时针方向的夹角
*参数信息： start：起始点；inf：拐点；end：终止点
*返回值： 两条直线之间的夹角（弧度）；10.0f则表示计算错误
*作者：
*完成时间： 2006.12.17
***********************************************************************************/
double CSortPoly::AngleOfTwoLines(Point start, Point inf, Point end)
{
double aa = ( start.x - inf.x ) * ( start.x - inf.x ) + ( start.y - inf.y ) * ( start.y - inf.y );
double bb = ( inf.x - end.x ) * ( inf.x - end.x ) + ( inf.y - end.y ) * ( inf.y - end.y );
double cc = ( start.x - end.x ) * ( start.x - end.x ) + ( start.y - end.y ) * ( start.y - end.y );
double cosValue = ( aa + bb - cc ) / ( 2 * sqrt( aa ) * sqrt( bb ) );
double angle = acos( cosValue );
double coeff1 = 0.0f, coeff2 = 0.0f;
if ( start.y != inf.y )
{
coeff1 = ( double )( inf.x - start.x ) / ( double )( start.y - inf.y );
coeff2 = ( double )( start.x * inf.y - inf.x * start.y ) / ( double )( start.y - inf.y );
if ( start.y > inf.y )
{
if ( end.x + coeff1 * end.y + coeff2 <= 0 )
{
return angle;
}
else
{
return ( PI * 2 - angle );
}
}
else if ( start.y < inf.y )
{
if ( end.x + coeff1 * end.y + coeff2 <= 0 )
{
return ( PI * 2 - angle );
}
else
{
return angle;
}
}
}
else if ( start.y == inf.y )
{
if ( inf.x > start.x )
{
if ( end.y < start.y )
{
return angle;
}
else
{
return ( PI * 2 - angle );
}
}
else if ( inf.x < start.x )
{
if ( end.y < start.y )
{
return ( PI * 2 - angle );
}
else
{
return angle;
}
}
}
return 10.0f;
}
/**********************************************************************************
*函数名称： Recursion
*函数功能： 计算与当前直线顺时针方向夹角最小的下一个点
*参数信息： num1：直线起始点；num2：直线终止点
*返回值： true：表示没有下一个点，多边形封闭；false：有下个点
*作者：
*完成时间： 2006.12.17
***********************************************************************************/
bool CSortPoly::Recursion(int num1, int num2)
{
Point pt1 = m_vPoints[ num1 - 1 ];
Point pt2 = m_vPoints[ num2 - 1 ];
int num3;
intList::iterator iter3 = m_vConnectedPoints[ num2 - 1 ].m_sPoints.begin();
intList::iterator iter3_end = m_vConnectedPoints[ num2 -1 ].m_sPoints.end();
double maxAngle = 2 * PI + 1;
for ( ; iter3 != iter3_end; ++iter3 )
{
Point pt3;
if ( *iter3 == m_nNum1 )
{
continue;
}
pt3.num = *iter3;
pt3.x = m_vPoints[ (*iter3) - 1 ].x;
pt3.y = m_vPoints[ (*iter3) - 1 ].y;
double angle = AngleOfTwoLines( pt1, pt2, pt3 );
if ( angle < maxAngle )
{
maxAngle = angle;
num3 = *iter3;
}
}
//PrintVectot(m_sResult);
//判断num3点是否在向量中
if ( !IsIn(m_sResult,num3) )
{
m_sResult.push_back( num3 );
m_vResult.push_back( num3 );
m_nNum1 = num2;
m_nNum2 = num3;
return false;
}
else
{
intList::iterator iter4 = m_vResult.begin();
for ( ; iter4 != m_vResult.end(); )
{
if ( num3 == *iter4 )
{
break;
}
else
{
m_vResult.erase( iter4 );
iter4 = m_vResult.begin();
}
}
if ( m_vResult.size() != m_sResult.size() )
{
m_sResult.clear();
iter4 = m_vResult.begin();
for ( ; iter4 != m_vResult.end(); ++iter4 )
{
m_sResult.push_back( *iter4 );
}
}
cpList::iterator iter5 = m_vConnectedPoints.begin();
cpList::iterator iter5_end = m_vConnectedPoints.end();
for ( ; m_bOnePolygon && iter5 != iter5_end; ++iter5 )
{
if ( (*iter5).m_sPoints.size() != 2)
{
m_bOnePolygon = false;
break;
}
else
{
continue;
}
}
if ( m_bOnePolygon )
{
m_sPolygons.push_back( m_sResult );
m_vPolygons.push_back( m_vResult );
m_bOnePolygon = false;
}
else if ( m_sResult != m_sOuterPoints )
{
if ( !IsIn(m_sPolygons,m_sResult) )
{
m_sPolygons.push_back( m_sResult );
m_vPolygons.push_back( m_vResult );
}
}
m_sResult.clear();
m_vResult.clear();
return true;
}
return true;
}
bool CSortPoly::IsIn(intList intlist, int num)
{
intList::iterator it;
for(it=intlist.begin();it!=intlist.end();it++)
{
int tt = *it;
if(tt==num)
return true;
}
return false;
}
bool CSortPoly::IsIn(intIntList int2list, intList intlist)
{
intIntList::iterator it;
for(it=int2list.begin();it!=int2list.end();it++)
{
intList ll = *it;
if(EquelList(ll,intlist))
return true;
}
return false;
}
/**********************************************************************************
*函数名称： SortPolygons
*函数功能： 计算多边形信息，结果保存在m_vPolygons中
*参数信息： 无
*返回值： 无
*作者：
*完成时间： 2006.12.17
***********************************************************************************/
void CSortPoly::SortPolygons()
{
pointList::iterator iter1 = m_vPoints.begin();
intIntList::iterator itpoly;
m_sResult.clear();
m_vResult.clear();
for ( ; iter1 != m_vPoints.end(); ++iter1 )
{
m_nNum1 = (*iter1).num;
intList::iterator iter2 = m_vConnectedPoints[ m_nNum1 - 1 ].m_sPoints.begin();
intList::iterator iter2_end = m_vConnectedPoints[ m_nNum1 - 1 ].m_sPoints.end();
for ( ; iter2 != iter2_end; ++iter2 )
{
m_nNum2 = *iter2;
m_sResult.push_back( m_nNum1 );
m_vResult.push_back( m_nNum1 );
m_sResult.push_back( m_nNum2 );
m_vResult.push_back( m_nNum2 );
while ( !Recursion( m_nNum1, m_nNum2 ) )
{
}
m_nNum1 = (*iter1).num;
}
}
PutLineInPolyS(m_vPolygons);
//出去边界多边形
for(itpoly=m_vPolygons.begin();itpoly!=m_vPolygons.end();itpoly++)
{
intList poly = *itpoly;
if(EquelList(poly,m_sOuterPoints))
{
m_vPolygons.erase(itpoly);
break;
}
}
m_flag = 1;
}
void CSortPoly::CheckResult()
{
int num = 0;
char str1[500],str2[500];
intIntList::iterator iter = m_vPolygons.begin();
intList::iterator iter2;
for( ; iter != m_vPolygons.end(); ++iter )
{
num++;
intList ptlist = *iter;
for( iter2 = ptlist.begin(); iter2 != ptlist.end();iter2 ++)
{
int pt = *iter2;
sprintf(str1,"%d",pt);
AfxMessageBox(str1);
}
sprintf(str2,"num ：%d",num);
AfxMessageBox(str2);
}
}
void CSortPoly::PrintVectot(intList ptlist)
{
FILE* fp;
intList::iterator it;
if((fp = fopen("C:\\temp\\vectorint.txt","w"))==0) return;
for(it=ptlist.begin();it!=ptlist.end();it++)
{
int aa = *it;
fprintf(fp,"%d\n",aa);
}
fclose(fp);
}
//判断两容器是否含有相同的元素
bool CSortPoly::EquelList(intList ptlist1, intList ptlist2)
{
if(ptlist1.size()!=ptlist2.size())
return false;
intList::iterator it1;
intList::iterator it2;
for(it1=ptlist1.begin();it1!=ptlist1.end();it1++)
{
int pt1 = *it1;
int flag = 0;
for(it2=ptlist2.begin();it2!=ptlist2.end();it2++)
{
int pt2 = *it2;
if(pt2==pt1)
{
flag = 1;
}
}
if(!flag)
return false;
}
return true;
}
pointList CSortPoly::GetPtList()
{
return m_vPoints;
}
intIntList CSortPoly::GetPolyList()
{
return m_vPolygons;
}
Point CSortPoly::GetPointByNum(int num)
{
Point err;
err.num = -1;
err.x = err.y = 0;
pointList::iterator it;
for(it = m_vPoints.begin();it!=m_vPoints.end();it++)
{
Point pt = *it;
if(pt.num==num)
return pt;
}
return err;
}
void CSortPoly::InitData()
{
m_nNumberOfPoints = 0;
m_nNumberOfLines = 0;
m_bOnePolygon = true;
m_vPoints.clear();
m_vLines.clear();
m_vConnectedPoints.clear();
m_sPolygons.clear();
m_sResult.clear();
m_vResult.clear();
m_sOuterPoints.clear();
m_vPolygons.clear();
m_flag = 0;
}
bool CSortPoly::ReadMlFile(CString fileName)
{
FILE* fp;
char ss[20];
int i,j,lNum,pNum;
listMatchPoint mplist;
listMatchPoint::iterator it;
lineList lineS;
if((fp=fopen(fileName,"r"))==0) return false;
fscanf(fp,"%s",ss);
if(strcmp(ss,"box:")!=0)
{
AfxMessageBox("文件格式不正确!");
return false;
}
//读入图幅大小
fscanf(fp,"%d%d",&m_size.cx,&m_size.cy);
//读入折线点
fscanf(fp,"%s",ss);
if(strcmp(ss,"Point:")!=0)
{
AfxMessageBox("文件格式不正确!");
return false;
}
fscanf(fp,"%d",&pNum);
for(i=0;i=2)
comPt.push_back(code);
}
//将所有交叉的折线段打断,形成只相连不交叉的折线段
DisLine(lineS,comPt);
//判断边界点,形成边界折线
LineAroundBorder(lineS,width,height,borderPt) ;
//数据转换成存储格式
m_vLines = lineS;
m_nNumberOfLines = m_vLines.size();
return true;
}
/**********************************************************************************
*函数名称： DisLine
*函数功能： 将所有交叉的折线段打断,形成只相连不交叉的折线段
*参数信息： lineS 保存折线段 ptlist折线段公共点
*返回值： 无
***********************************************************************************/
bool CSortPoly::DisLine(lineList& lineS,intList ptlist)
{
int i,vex,ewr,nSum; //vex存储公共节点
lineList tempList; //中间变量
Line tempLine;
lineList::iterator itl;
intList::iterator itp;
if(lineS.empty()||ptlist.empty()) return false;
for(itl=lineS.begin();itl!=lineS.end();itl++)
{
//找到每个弧段内的公共节点
Line ll = *itl;
nSum = ll.ptlist.size();
for(i=0;i0 ; j--)
{
for(i=0;iptlist[i+1].left_y)
{
tempPoint = ptlist[i];
ptlist[i] = ptlist[i+1];
ptlist[i+1] = tempPoint;
}
}
else
{
if(ptlist[i].left_yptlist[i+1].left_x)
{
tempPoint = ptlist[i];
ptlist[i] = ptlist[i+1];
ptlist[i+1] = tempPoint;
}
}
else
{
if(ptlist[i].left_x=0;i--)
{
int pt = tempLine.ptlist[i];
if(pt==start||pt==end) continue;
extralist.push_back(pt);
}
}
}
return true;
}
//*************************************************************************