计算几何学 | 映像 | Reflection | C/C++实现

问题描述

对于三个点p1、p2、p，设以通过p1、p2的直线为对称轴与点p成线对称的点为x，求点x的坐标（点p对于直线p1p2的映像）。

输入：
输入按照以下格式给出：
$x_{p1}$xp1​ $y_{p1}$yp1​ $x_{p2}$xp2​ $y_{p2}$yp2​
$q$q
$x_{p0}$xp0​ $y_{p0}$yp0​
$x_{p1}$xp1​ $y_{p1}$yp1​
…
$x_{p_{q-1}}$xpq−1​​ $y_{p_{q-1}}$ypq−1​​
输出：
根据各个问题输出点x的坐标，每个问题占1行。输出允许误差不超过0.00000001
限制：
1 ≤ q ≤ 1000
-10000 ≤ $x_i,y_i$xi​,yi​ ≤ 10000
p1、p1不是同一个点。

输入示例

0 0 3 4
3
2 5
1 4
0 3

输出示例

4.2400000000 3.3200000000
3.5600000000 2.0800000000
2.8800000000 0.8400000000

讲解

设以线段（直线）s = p1p2为对称轴与点p成线对称的点为x，这个点x就称为p的映像（reflection）。

首先求点p到线段p1p2的投影点p’。然后将p到p’的向量（p’ - p）扩大至标量2倍。最后给起点p加上这个向量，得出x的坐标。

下面我们来看看如何用程序求以线段s为对称轴与点p成线对称的点x。

以线段s为对称轴与点p成先对称的点：

Point reflect(Segment s, Point p) {
	return p + (project(s, p) - p) * 2.0;
}

注：对于一些计算几何学函数的类的详细解释，可参见：计算几何学汇总

AC代码如下

#include<stdio.h>
#include<iostream>
#include<cmath>
using namespace std;

#define EPS (1e-10)
#define equals(a, b) (fabs((a) - (b)) < EPS)

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;
} 

Point reflect(Segment s, Point p) {//映像 以线段s为对称轴与点p成先对称的点
//对于三个点p1、p2、p，设以通过p1、p2的直线为对称轴与点p成线对称的点为x，
//求点x的坐标（点p对于直线p1p2的映像） 
	return p + (project(s, p) - p) * 2.0;
} 

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 = reflect(s, p);
		printf("%.10f %.10f\n", p.x, p.y);
	}
} 

注：以上本文未涉及代码的详细解释参见：计算几何学