线段

直线与线段的表示方法

我们可以用一条线段的两个端点来表示一条线段。直线的表示有两种方式,一种方式是使用二元一次方程来表示,另一种是用直线上任意一条长度不为零的线段来表示。由于使用方程表示接近垂直于某坐标轴的直线时容易产生精度误差,所以我们通常使用直线上的某条线段来表示直线。

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

点在线段上的判断

判断点在线段上的两条依据:

  1. 在以为对角顶点的矩形内。

示例代码

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

判断线段关系

线段有相交和不相交两种关系,通常按照以下步骤判断。

  1. 快速排斥试验
  2. 跨立试验

快速排斥试验

设以线段为对角线的矩形为,设以线段为对角线的矩形为,如果不相交,显然两线段不会相交。

跨立试验

如果两线段相交,则两线段必然相互跨立对方。若跨立,则矢量位于矢量的两侧,即。上式可改写成。当时,说明共线,但是因为已经通过快速排斥试验,所以一定在线段上;同理,说明一定在线段上。所以判断跨立的依据是:。同理判断跨立的依据是:

经典题目

  • ZOJ 1648 Circuit Board
  • POJ 3304 Segments
  • POJ 2653 Pick-up sticks

求点到线段的距离

求线段到点p最短距离的方法为:

根据点到的投影点的位置进行判断的方法:

  1. 判断线段所成的夹角,如果是钝角,那么是点到线段的最短距离。
  2. 判断线段所成的夹角,如果是钝角,那么是点到线段的最短距离。
  3. 线段和线段所成的夹角都不为钝角,那么点到线段的距离是点到直线的距离,这个距离可以用面积法直接算出来。

示例代码

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

results matching ""

    No results matching ""