計算幾何學 | 投影 | Projection | C/C++實作

問題描述

對于給定的三個點p1、p2、p，從點p向通過p1、p2的直線引一條垂線，求垂足x的坐标。（點p在直線p1p2上的投影）

輸入：

輸入按以下格式給出：

x p 1 x_{p1} xp1​ y p 1 y_{p1} yp1​ x p 2 x_{p2} xp2​ y p 2 y_{p2} yp2​

q q q

x p 0 x_{p0} xp0​ y p 0 y_{p0} yp0​

x p 1 x_{p1} xp1​ y p 1 y_{p1} yp1​

…

x p q − 1 x_{p_{q-1}} xpq−1​​ y p q − 1 y_{p_{q-1}} ypq−1​​

第1行給出p1、p2的坐标。接下來給出q個p的坐标用作問題。

輸出：

根據各問題輸出垂足x的坐标，每個問題占1行。輸出允許誤差不超過0.00000001。

限制：

1 ≤ q ≤ 1000

-10000 ≤ x i , y i x_i,y_i xi​,yi​ ≤ 10000

p1、p2不是同一個點。

輸入示例

0 0 3 4
1
2 5
           

輸出示例

3.1200000000 4.1600000000
           

講解

從點p向線段（或直線）s = p1p2引1條垂線，交點設為x。這個x就叫做點p的投影（projection)。

設s.p2 - s.p1為向量base，p - s.p1為向量hypo，點s.p1與點x的距離為t，hypo與x的距離為t，hypo與base的夾角為θ，則：

t = ∣ h y p o ∣ c o s θ t=|hypo|cosθ t=∣hypo∣cosθ， h y p o ⋅ b a s e = ∣ h y p o ∣ ∣ b a s e ∣ c o s θ hypo·base=|hypo||base|cosθ hypo⋅base=∣hypo∣∣base∣cosθ

于是有 t = h y p o ⋅ b a s e / ∣ b a s e ∣ t=hypo·base/|base| t=hypo⋅base/∣base∣。

根據t與|base|的比例 r = t / ∣ b a s e ∣ r=t/|base| r=t/∣base∣可得：

x = s . p 1 + b a s e ∗ t / ∣ b a s e ∣ = s . p 1 + b a s e ∗ ( h y p o ⋅ b a s e ) / ∣ b a s e ∣ 2 x=s.p1+base*t/|base|=s.p1+base*(hypo·base)/|base|^2 x=s.p1+base∗t/∣base∣=s.p1+base∗(hypo⋅base)/∣base∣2

于是來看看如何用程式求點p線上段（直線）s上的投影。

點p線上段s上的投影：

Point project(Segment s, Point p) {
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / norm(base);
	return s.p1 + base * r;
}
           

AC代碼如下

class Point {//Point類，點 
	public:
		double x, y;
		
		Point(double x = 0, double y = 0): x(x), y(y) {}

		Point operator + (Point p) { return Point(x + p.x, y + p.y); }
		Point operator - (Point p) { return Point(x - p.x, y - p.y); }
		Point operator * (double a) { return Point(a * x, a * y); }
		Point operator / (double a) { return Point(x / a, y / a); }

		double abs() { return sqrt(norm()); }
		double norm() { return x * x + y * y; }
		
		bool operator < (const Point &p) const {
			return x != p.x ? x < p.x : y < p.y;
		}

		bool operator == (const Point &p) const {
			return fabs(x - p.x) < EPS && fabs(y - p.y) < EPS;
		}
};

typedef Point Vector;//Vector類，向量 

struct Segment{//Segment 線段 
	Point p1, p2;
};
double dot(Vector a, Vector b) {//内積 
	return a.x * b.x + a.y * b.y;
}

double cross(Vector a, Vector b) {//外積 
	return a.x*b.y - a.y*b.x;
}

bool isOrthogonal(Vector a, Vector b){//判斷正交 
	return equals(dot(a, b), 0.0);
}

bool isOrthogonal(Point a1, Point a2, Point b1, Point b2){//判斷正交 
	return isOrthogonal(a1 - a2, b1 - b2);
}

bool isOrthogonal(Segment s1, Segment s2){//判斷正交 
	return equals(dot(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}

bool isParallel(Vector a, Vector b){//判斷平行 
	return equals(cross(a, b), 0.0);
}

bool isParallel(Point a1, Point a2, Point b1, Point b2){//判斷平行 
	return isParallel(a1 - a2, b1 - b2);
}

bool isParallel(Segment s1, Segment s2){//判斷平行 
	return equals(cross(s1.p2 - s1.p1, s2.p2 - s2.p1), 0.0);
}

Point project(Segment s, Point p) {//投影 對于給定的三個點p1、p2、p，從點p向通過
//p1、p2的直線引一條垂線，求垂足x的坐标。（點p在直線p1p2上的投影） 
	Vector base = s.p2 - s.p1;
	double r = dot(p - s.p1, base) / base.norm();
	return s.p1 + base * r;
} 

int main(){
	Point p1, p2, p;
	cin>>p1.x>>p1.y>>p2.x>>p2.y;
	
	Segment s;
	s.p1 = p1;
	s.p2 = p2;
	
	int q;
	cin>>q;
	
	while(q--){
		cin>>p.x>>p.y;
		p = project(s, p);
		printf("%.10f %.10f\n", p.x, p.y);
	}
}
           

對于代碼中其他函數和類的詳細解釋，可參見：計算幾何學