line.cpp

一个折线不重复相交的程序, 一家日本公司的程序员上机题

#include "StdAfx.h"
#include ".\line.h"

CLine* g_line;
CLine::CLine(void)
{
	::_tcscpy( m_TxT, "当前直线可以正常绘制" );
	m_posWidth = 50;
}

CLine::~CLine(void)
{
}

void CLine::InsertPos( )
{
	InsertPos( m_nowpos );
}

void CLine::InsertPos( POINT pos )
{
	list< POINT >::iterator cell;
	for( cell = m_PosList.begin(); cell!=m_PosList.end(); cell++ )
	{
		if( cell == m_PosList.begin() )
			continue;

		list< POINT >::iterator cellTemp, cellEndTest;

		cellEndTest = m_PosList.end();
		cellEndTest--;
		if( cell == cellEndTest )
			break;

		cellTemp = cell;
		cellTemp--;

        Line line1;
		line1.pos_1 = (*cellTemp);
		line1.pos_2 = (*cell);

		if( this->CheckLine( line1, m_mouseline ) )
		{
			_tcscpy( m_TxT, "当前直线由于相交而不能进行绘制" );
			return;
		}
		else
		{
			_tcscpy( m_TxT, "当前直线可以正常绘制" );
		}
	}

	//把该点画入主线中
	m_PosList.push_back( pos );	

	POINT pos1; //左边
	POINT pos2; //右边

	if( m_PosList.size() < 2 )
	{
		return;
	}
	else
	{
	//设置两条辅线
	cell = m_PosList.end();	
	list< POINT >::iterator l1, l2, l3;
	POINT p1, p2, p3;
	l3 = (cell);cell--; p3 = (*l3); //最近点
	l2 = (cell);cell--; p2 = (*l2); //前1个点
	l1 = (cell);        p1 = (*l1); //前2个点

	//
	double k1;  //第一个点到第二个点的直线斜率
	double k2;  //第二个点到第三个点的直线斜率

	k1 = ((double)( p1.y - p2.y )) / ((double)( p1.x - p2.x ));
	k2 = ((double)( p2.y - p3.y )) / ((double)( p2.x - p3.x ));

	//针对k1这条直线的b1
	double b1 = p2.y - k1 * p2.x;

	//针对k2这条直线的b2
	double b2 = p3.y - k2 * p3.x;

	//角平分线
    double K = ((double)( k1 + k2 )) /2;        
	double B = p2.y - K * p2.x;

    //左线段
                

	//右线段


	//第一个点的辅助线开始位置
	if( m_PosList.begin() == l1 )
	{
        double k = (double)(1/k1);          

        POINT pos;		
		pos = (*m_PosList.begin());

        double b;
		b = pos.y - pos.x * k;

        double ang = atan( k );
		int tx, ty;
		tx = m_posWidth * cos( ang );
		ty = m_posWidth * sin( ang );
        
		if( k <= 0 )
		{
        //line1
		pos1.x = pos.x - tx;
		pos1.y = pos.y + ty;

		//line2
		pos2.x = pos.x + tx;
		pos2.y = pos.y - ty;
		}
		else
		{
        //line1
		pos2.x = pos.x - tx;
		pos2.y = pos.y + ty;

		//line2
		pos1.x = pos.x + tx;
		pos1.y = pos.y - ty;
		}
	}
	else
	{
		/*
		double ang = 3.1415926f/4;
    	pos1 = pos2 = (*l1);
	    pos1.x = pos1.x - m_posWidth*sin(ang);
	    pos1.y = pos1.y - m_posWidth*cos(ang);

    	pos2.x = pos2.x + m_posWidth*sin(ang);
	    pos2.y = pos2.y + m_posWidth*cos(ang);				
		

		//由于目前有2条直线
		//左线
		{
			//求上一个终点
			list< POINT >::iterator cell;
			cell = m_PosPart_Left.end();
			cell--;

			POINT p1 = (*cell);

			//斜率为k 的直线1
			double lb = p1.y - k1 * p1.x;

			//斜率为k 的直线2
			double ang = atan( k2 );
			double lb2 = b2 + m_posWidth/cos(ang);

			pos1.x = ((double)( lb2 - lb ))/((double)( k1 - k2 ));
			pos1.y = pos1.x * k1 + lb;		

		if( k2 >= 0 )
		{
		double ang = atan( k2 );
    	pos1 = pos2 = (*l1);
	    pos1.x = pos1.x - m_posWidth*sin(ang);
	    pos1.y = pos1.y - m_posWidth*cos(ang);

    	pos2.x = pos2.x + m_posWidth*sin(ang);
	    pos2.y = pos2.y + m_posWidth*cos(ang);		
		}
		else
		{
		double ang = atan( k2 );
    	pos1 = pos2 = (*l1);
	    pos1.x = pos1.x + m_posWidth*sin(ang);
	    pos1.y = pos1.y + m_posWidth*cos(ang);

    	pos2.x = pos2.x - m_posWidth*sin(ang);
	    pos2.y = pos2.y - m_posWidth*cos(ang);	
		}

/*
        double k = k1;          

        POINT pos;		
		list< POINT >::iterator cell;
		cell = m_PosPart_Left.end();
		cell--;

		pos = (*cell);

        double b;
		b = pos.y - pos.x * k;

        double ang = atan( k );
		int tx, ty;
		tx = m_posWidth * cos( ang );
		ty = m_posWidth * sin( ang );
        
		if( k <= 0 )
		{
        //line1
		pos1.x = pos.x - tx;
		pos1.y = pos.y + ty;

		//line2
		pos2.x = pos.x + tx;
		pos2.y = pos.y - ty;
		}
		else
		{
        //line1
		pos2.x = pos.x - tx;
		pos2.y = pos.y + ty;

		//line2
		pos1.x = pos.x + tx;
		pos1.y = pos.y - ty;
		}

		}		
*/
	}

//	m_PosPart_Left.push_back( pos1 );
//	m_PosPart_Right.push_back( pos2 );

	}

}

void CLine::InsertPos( int x, int y )
{
	POINT pos;
	pos.x = x;
	pos.y = y;

	InsertPos( pos );
}

void CLine::SetNowPos( POINT pos )
{
	m_nowpos = pos;
}

void CLine::SetNowPos( int x, int y )
{
	m_nowpos.x = x;
	m_nowpos.y = y;
}

void CLine::SetMousePos( POINT pos )
{
	m_mousepos = pos;
}

void CLine::SetMousePos( int x, int y )
{
	m_mousepos.x = x;
	m_mousepos.y = y;
}

void CLine::DrawLine( HDC hdc )
{
	//绘制主线
	if( m_PosList.size() < 1 )
		return;

	POINT pos;

	list< POINT >::iterator cell, cellbegin, cellend;
	for( cell = m_PosList.begin(); cell != m_PosList.end(); cell++ )
	{
		cellend   = cell;
		cellbegin = cellend;
		cellbegin--;

		POINT posBegin;
		POINT posEnd;
		posBegin = POINT( *cellbegin );
        posEnd   = POINT( *cellend   );

		MoveToEx( hdc, posBegin.x, posBegin.y, &pos );
		LineTo(   hdc, posEnd.x, posEnd.y );

		//作线段相交检测
		m_mouseline.pos_1.x = posEnd.x;
		m_mouseline.pos_1.y = posEnd.y;
	}

	cell = m_PosList.end();
	cell--;

	MoveToEx(     hdc, (*cell).x, (*cell).y, &pos );
	LineTo(       hdc, m_mousepos.x, m_mousepos.y );

	m_mouseline.pos_2.x = m_mousepos.x;
	m_mouseline.pos_2.y = m_mousepos.y;

	//绘制辅线
	list< POINT >::iterator cellpart;
	for( cellpart = m_PosPart_Left.begin(); cellpart != m_PosPart_Left.end(); cellpart++ )
	{
		cellend   = cellpart;
		cellbegin = cellend;
		cellbegin--;

		POINT posBegin;
		POINT posEnd;
		posBegin = POINT( *cellbegin );
        posEnd   = POINT( *cellend   );

		MoveToEx( hdc, posBegin.x, posBegin.y, &pos );
		LineTo(   hdc, posEnd.x, posEnd.y );
	}

	for( cellpart = m_PosPart_Right.begin(); cellpart != m_PosPart_Right.end(); cellpart++ )
	{
		cellend   = cellpart;
		cellbegin = cellend;
		cellbegin--;

		POINT posBegin;
		POINT posEnd;
		posBegin = POINT( *cellbegin );
        posEnd   = POINT( *cellend   );

		MoveToEx( hdc, posBegin.x, posBegin.y, &pos );
		LineTo(   hdc, posEnd.x, posEnd.y );
	}

	TextOut( hdc, 10, 10, m_TxT, strlen( m_TxT ) );
	
	::ReleaseDC( NULL, hdc );
//	::DeleteDC( hdc );
}

void CLine::GetStartPos( POINT& pos )
{
	list< POINT >::iterator cell;
	cell = m_PosList.begin();

	pos = (POINT)(*cell);
}

void CLine::GetEndPos( POINT& pos )
{
	list< POINT >::iterator cell;
	cell = m_PosList.end();
	cell--;

	pos = (POINT)(*cell);
}

//判断直线相交
BOOL CLine::CheckLine( Line line1, Line line2 )
{
	line1.pos_1.y = -line1.pos_1.y;
	line1.pos_2.y = -line1.pos_2.y;
	line2.pos_1.y = -line2.pos_1.y;
	line2.pos_2.y = -line2.pos_2.y;
	
    double k1, k2;
	double b1, b2;

	k1 = ((double)(line1.pos_2.y - line1.pos_1.y))/(line1.pos_2.x - line1.pos_1.x );
	b1 = line1.pos_1.y - line1.pos_1.x * k1;

	k2 = ((double)(line2.pos_2.y - line2.pos_1.y))/(line2.pos_2.x - line2.pos_1.x );
	b2 = line2.pos_1.y - line2.pos_1.x * k2;

    if(( k1 == k2 )&&( b1 != b2 ))
		return TRUE;

    double tx, ty;
    tx = (b1 - b2)/(k2 - k1);
	ty = k1*tx + b1;

	if((( tx < line1.pos_1.x )&&( tx < line1.pos_2.x ))||(( tx > line1.pos_1.x )&&( tx > line1.pos_2.x )))
		return FALSE;

	if((( tx < line2.pos_1.x )&&( tx < line2.pos_2.x ))||(( tx > line2.pos_1.x )&&( tx > line2.pos_2.x )))
		return FALSE;

	if((( ty < line1.pos_1.y )&&( ty < line1.pos_2.y ))||(( ty > line1.pos_1.y )&&( ty > line1.pos_2.y )))
		return FALSE;

	if((( ty < line2.pos_1.y )&&( ty < line2.pos_2.y ))||(( ty > line2.pos_1.y )&&( ty > line2.pos_2.y )))
		return FALSE;

	return TRUE;
}