segmentsintersect.cpp

计算几何的利用叉积判断线段是否相交的算法

//Calculate Geometry
//#include<iostream>
#include<cstring>
#include<ctime>
#include<fstream>
using namespace std;

ofstream cout( "test.txt" );
int x, y;
int MAX = 21;
int BEGIN = -10;
inline int max( int a, int b ) {	return a > b ? a : b;	}
inline int min( int a, int b ) {	return a < b ? a : b;	}

struct Point
{
	int x, y;
 
	friend ostream & operator << ( ostream& out, const Point& p )
	{
		out << "(" << p.x << ", " << p.y << ")";

		return out;
	}

	bool equals( const Point p )
	{
		return x == p.x && y == p.y;
	}
};

Point first1, first2, second1, second2;

Point makeVector( Point p1, Point p2 )
{
	Point res;
	res.x = p2.x - p1.x;
	res.y = p2.y - p1.y;

	return res;
}

int makeMul( Point p1, Point p2 )
{
	return p1.x * p2.y - p2.x * p1.y;
}

bool onSegment( Point p1, Point p2, Point point )
{
	return point.x >= min( p1.x, p2.y ) && point.x <= max( p1.x, p2.x ) && point.y >= min( p1.y, p2.y ) && point.y <= max( p1.y, p2.y );
}

int direction( Point base, Point p1, Point p2 )
{
	return makeMul( makeVector( base, p1 ), makeVector( base, p2 ) );
}

inline bool different( int a, int b )
{
	if ( a > 0 && b < 0 || a < 0 && b > 0 )
		return true;
	else
		return false;
}

bool segmentsIntersection( Point p1, Point p2, Point p3, Point p4 )
{
	int d1 = direction( p3, p4, p1 );
	int d2 = direction( p3, p4, p2 );
	int d3 = direction( p1, p2, p3 );
	int d4 = direction( p1, p2, p4 );

	cout << "d1 " << d1 << endl;
	cout << "d2 " << d2 << endl;
	cout << "d3 " << d3 << endl;
	cout << "d4 " << d4 << endl;

	if ( different( d1, d2 ) && different( d3, d4 ) )
		return true;

	if ( d1 == 0 && onSegment( p3, p4, p1 ) ||
		 d2 == 0 && onSegment( p3, p4, p2 ) ||
		 d3 == 0 && onSegment( p1, p2, p3 ) ||
		 d4 == 0 && onSegment( p1, p2, p4 ) )
		 return true;

	return false;
}

inline void randomPoints( Point &p )
{
	p.x = rand() % MAX + BEGIN;
	p.y = rand() % MAX + BEGIN;
}

void getPoints()
{
	randomPoints( first1 );
	randomPoints( first2 );
	randomPoints( second1 );
	randomPoints( second2 );
}

void printBoard()
{
	int base = BEGIN;
	int i, j;

	cout << "  ";
	for ( i = 0; i < MAX; i ++ )
		cout << i + base << " ";
	cout << endl;
	for ( i = MAX - 1; i >= 0; i -- )
	{
		cout << i + base << " ";
		for ( j = 0; j < MAX; j ++ )
		{
			Point curPoint;
			curPoint.x = i + base;
			curPoint.y = j + base;
			if ( first1.equals( curPoint ) || first2.equals( curPoint ) )
				cout << "* ";
			else if ( second1.equals( curPoint ) || second2.equals( curPoint ) )
				cout << "# ";
			else
				cout << "  ";
		}
		cout << endl;
	}
}
void test()
{
	getPoints();
	
	cout << "线段1 -- " << first1 << " -- " << first2 << endl;
	cout << "线段2 -- " << second1 << " -- " << second2 << endl;
	printBoard();
	if ( segmentsIntersection( first1, first2, second1, second2 ) )
	{
		x ++;
		cout << "线段相交！\n";
	}
	else 
	{
		y ++;
		cout << ( "线段不相交! \n" );
	}
	cout << endl << endl;
}

int main()
{
	srand( time( 0 ) );
	int N;
	x = 0, y = 0;

	scanf( "%d", &N );
	while ( N -- )
		test();

	cout << "相交" << x << endl << "不相交" << y << endl;
	/*while ( cin >> first1.x >> first1.y >> first2.x >> first2.y >> second1.x >> second1.y >> second2.x >> second2.y )
	{
		if ( segmentsIntersection( first1, first2, second1, second2 ) )
			printf( "线段相交\n" );
		else
			printf( "线段不相交\n" );
	}*/

	return 0;
}