线段
直线与线段的表示方法
我们可以用一条线段的两个端点来表示一条线段。直线的表示有两种方式，一种方式是使用二元一次方程来表示，另一种是用直线上任意一条长度不为零的线段来表示。由于使用方程表示接近垂直于某坐标轴的直线时容易产生精度误差，所以我们通常使用直线上的某条线段来表示直线。
struct Sg {
Pt s, t;
Sg() { }
Sg(Pt s, Pt t) : s(s), t(t) { }
Sg(double a, double b, double c, double d) : s(a, b), t(c, d) { }
};
点在线段上的判断
判断点在线段上的两条依据：
。
在以为对角顶点的矩形内。
示例代码
bool PtOnSegment(Pt s, Pt t, Pt a) {
return !det(a-s, a-t) && min(s.x, t.x) <= a.x && a.x <= max(s.x, t.x) &&
min(s.y, t.y) <= a.y && a.y <= max(s.y, t.y);
}
另一种方法
判断点在为对角线定点的矩形内较麻烦，可以直接判断的符号来判断在直线上是否在之间。
示例代码
bool PtOnSegment(Pt p, Pt a, Pt b) {
return !sgn(det(p-a, b-a)) && sgn(dot(p-a, p-b)) <= 0;
}
把上例代码中的<=改成<就能实现不含线段端点的点在线段上的判断。
点在直线上的判断
点在直线上的判断很简单只要把点在线段上的判断的步骤2去掉即可。
示例代码
bool PtOnLine(Pt p, Pt s, Pt t) {
return !sgn(det(p-a, b-a));
}
求点到直线的投影
示例代码
Pt PtLineProj(Pt s, Pt t, Pt p) {
double r = dot(p-s, t-s) / (t - s).norm();
return s + (t - s) * r;
}
判断直线关系
直线有相交和平行两种关系，靠叉乘能简单判断。
bool parallel(Pt a, Pt b, Pt s, Pt t) {
return !sgn(det(a-b, s-t));
}
判断线段关系
线段有相交和不相交两种关系，通常按照以下步骤判断。
快速排斥试验
跨立试验
快速排斥试验
设以线段为对角线的矩形为，设以线段为对角线的矩形为，如果和不相交，显然两线段不会相交。
跨立试验
如果两线段相交，则两线段必然相互跨立对方。若跨立，则矢量和位于矢量的两侧，即。上式可改写成。当时，说明和共线，但是因为已经通过快速排斥试验，所以一定在线段上；同理，说明一定在线段上。所以判断跨立的依据是：。同理判断跨立的依据是：。
经典题目
ZOJ 1648 Circuit Board
POJ 3304 Segments
POJ 2653 Pick-up sticks
求点到线段的距离
求线段到点p最短距离的方法为：
根据点到的投影点的位置进行判断的方法：
判断线段和所成的夹角，如果是钝角，那么是点到线段的最短距离。
判断线段和所成的夹角，如果是钝角，那么是点到线段的最短距离。
线段和线段与所成的夹角都不为钝角，那么点到线段的距离是点到直线的距离，这个距离可以用面积法直接算出来。
示例代码
double PtSegmentDist(Pt a, Pt b, Pt p) {
if (sgn(dot(p-a, b-a)) <= 0) return (p-a).norm();
if (sgn(dot(p-b, a-b)) <= 0) return (p-b).norm();
return fabs(det(a-p, b-p)) / (a-b).norm();
}
经典题目
URAL 1348 Goat in the Garden 2