计算几何基础

1、 矢量叉积

AB * AC > 0 ; AC在AB的 逆时针方向， 否则顺时针

= 0; A B C 共线

class Point{
public:
	double x;
	double y;
	Point(double _x,double _y):x(_x),y(_y){}
};

//P Q 为向量   A,B,C为点
// P * Q = x1 * y2 - x2 * y1
// P = A-B  Q=C-A
//即  (x1-x0) * (y2-y0) - (x2-x0) * (y1-y0)

/*
 *计算 AB*AC 的叉积
 */
double CorssProd(Point A, Point B, Point C){
	return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

2 、 判断点是否在线段上

点Q, 线段 P1,P2.

/*
 * 点Q 是否在  线段 P1,P2 上
 */
bool on_segment(Point P1, Point P2, Point Q){
	return  CrossProd(P1,P2,Q) == 0 &&
			(min(P1.x,P2.x) <= Q.x  && max(P1.x, P2.x) >= Q.x )
			&& ( min(P1.y,P2.y) <= Q.y && max(P1.y, P2.y) >= Q.y );
}

3、跨立实验 线段是否相交。

#include <iostream>
using namespace std;

class Point{
public:
	double x;
	double y;
	Point(double _x,double _y):x(_x),y(_y){}
};

//P Q 为向量   A,B,C为点
// P * Q = x1 * y2 - x2 * y1
// P = A-B  Q=C-A
//即  (x1-x0) * (y2-y0) - (x2-x0) * (y1-y0)

/*
 *计算 AB*AC 的叉积
 */
double CrossProd(Point & A, Point & B, Point & C){
	//cout << (B.x - A.x) <<  " " <<  (B.y - A.y)<< endl;
	//cout << (C.x - A.x) << " " << (C.y - A.y) <<  endl;
	return (B.x - A.x) * (C.y - A.y) - (C.x - A.x) * (B.y - A.y);
}

/*
 * 点Q 是否在  线段 P1,P2 上
 */
bool on_segment(Point P1, Point P2, Point Q){
	return  CrossProd(P1,P2,Q) == 0 &&
			(min(P1.x,P2.x) <= Q.x  && max(P1.x, P2.x) >= Q.x )
			&& ( min(P1.y,P2.y) <= Q.y && max(P1.y, P2.y) >= Q.y );
}

// (Q1P1 * Q1Q2) * (Q1Q2 * Q1P2) >=0 并且
// (P1Q1 * P1P2) * (P1P2 * P1Q2) >= 0
bool corssJudge(Point P1,Point P2, Point Q1, Point Q2){
	return ( CrossProd(Q1,P1,Q2) * CrossProd(Q1,Q2,P2) >=0 ) &&
			( CrossProd(P1,Q1,P2) * CrossProd(P1,P2,Q2) >= 0);
}

int main() {
	Point p1(1.0,2.0);
	Point p2(3.0,3.0);

	Point q1(2.0, 2.5); //在
	Point q2(1.0, 2.5); //不在
	Point q3(5.0, 4.0); //在延长线上

	//cout << CrossProd( p1, p2 , q1) << endl;
	cout << "测试点是否在线段 p1p2 上： q1在, q2,q3不在 "  << endl;
	cout << on_segment(p1, p2, q1) << endl;
	cout << on_segment(p1, p2, q2) << endl;
	cout << on_segment(p1, p2, q3) << endl;


	cout << "测试线段是否相交:"  << endl;
	cout << "p1(1.0,2.0) p2(3.0,3.0)  q1(2.0, 2.5) q2(1.0, 2.5) q3(5.0, 4.0)" << endl;
	cout << "p1p2 与 q1q2相交， 与 q2q3不相交" << endl;
	cout << corssJudge(p1,p2,q1,q2) << endl;
	cout << corssJudge(p1,p2,q2,q3) << endl;

	return 0;
}