计蒜客 17318.Line Segments Clipped by Windows

493


题目



点击显/隐题目

A rectangular area specified in world coordinates is called a window. The rectangular area on the display device to which a window is mapped is called a viewport. The picture elements that fall within this window area is visible. In the viewport there is a block which is given higher priority for displaying. That is, those line segments that falls behind the block will not be visible. Assume the boundaries of a viewport: $x=x_{min}$, $x=x_{max}$, $y=y_{min}$, $y=y_{max}$, the boundaries of block: $x=x_{min}$, $x=x_{max}$, $y=y_{min}$, $y=y_{max}$, and $(x_{i1} , y_{i1} )$ $(x_{i2} , y_{i2})$ : he endpoints of the lines in device coordinates.

Please calculate the coordinate value of the endpoints of all the visible line.



The boundaries of a viewport and block, endpoints of the lines in device coordinates.
$x_{min}$ $y_{min}$ $x_{max}$ $y_{max}$
$x_{min}$ $y_{min}$ $x_{max}$ $y_{max}$
$x_{11}$ $y_{11}$ $x_{12}$ $y_{12}$
$x_{21}$ $y_{21}$ $x_{22}$ $y_{22}$
$...$
$x_{n1}$ $y_{n1}$ $x_{n2}$ $y_{n2}$


Endpoints of all the visible lines. Please sort the coordinate values of $x_{i1}$ ’s in descending order.
$x_{11}$ $y_{11}$ $x_{12}$ $y_{12}$
$x_{21}$ $y_{21}$ $x_{22}$ $y_{22}$
$...$
$x_{k1}$ $y_{k1}$ $x_{k2}$ $y_{k2}$
Note:
  1. $x_{i1} < x_{i2}$
  2. In the condition of only the endpoints of the segments are falling on the boundaries of the viewport or block and the other part is invisible, please neglect it.
  3. Integers: $x_{min}$, $y_{min}$ , $x_{max}$ , $y_{max}$, $x_{min}$ , $y_{min}$ , $x_{max}$ , $y_{max}$ ; float: $x_{ij}$, $y_{ij}$.
  4. All float number should be accurate to $10^{-4}$


1 2 2 3
3.0 3.0 7.0 7.0
9.0 7.0 2.0 6.0
4.0 2.0 1.1 4.0
9.0 -1.0 5.1 7.0
2.0 2.0 1.0 3.0
-2.5 3.1 5.2 -3.0
-1.0 7.3 -2.1 0.6
-2.1 5.6 6.0 7.0
-0.7 2.1 -5.2 12.6


3.0000 3.0000 5.0000 5.0000
1.1000 4.0000 4.0000 2.0000
0.0000 1.1195 1.4131 0.0000



题解


给你不超过50个线段,有一个大矩形为可视区域,一个小矩形为遮挡区域,输出所有能够看到的线段的首尾坐标(线段可以被小矩形分成两部分或者只能看到原线段的一部分)


按照讨论区的说法,如果正好在边界上,认为是不可见
根据线段的两个端点与矩形的关系以及与矩形的交点,可以分为如下情况:
  1. 整条线段都在矩形外部(保留整个线段 | 删除整个线段)
  2. 整条线段都在矩形上(删除整个线段)
  3. 整条线断都在矩形内部(删除整个线段 | 保留整个线段)
  4. 两个端点在矩形外部,但是和矩形有一个交点(分为两个线段 | 删除整个线段)
  5. 两个端点在矩形外部,但是和矩形有两个交点(分为两个线段 | 变成一个新线段)
  6. 一个端点在矩形内部,另一个在外部或者矩形上(变成一个新线段)

然后分别对应两种矩形进行不同的操作

最后按照要求排序输出即可

{% note danger%}
注意最后输出可能会有 -0.0000
输出时使用 fabs()
{% endnote %}


代码


点击显/隐代码
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
#define Log(format, ...) // printf(format, ##__VA_ARGS__)
/* 计算几何模板 */
const double eps = 1e-10;
const double INF = 0x4242424242424242;
inline int sgn(const double &x) {
    if (fabs(x) < eps)
        return 0;
    return x > 0 ? 1 : -1;
}
struct Vector;
struct Segment;
double Cross(const Vector &, const Vector &);
int Point_Segment(const Vector &, const Segment &);
struct Vector {
    double x, y;
    int n;
    Vector(double _x = 0, double _y = 0, int _n = 0) : x(_x), y(_y), n(_n) {}
    bool operator==(const Vector &rhs) const {
        return sgn(x - rhs.x) == 0 && sgn(y - rhs.y) == 0;
    }
    bool operator!=(const Vector &rhs) const { return !(*this == rhs); }
    bool operator<(const Vector &rhs) const {
        if (sgn(x - rhs.x) == 0)
            return sgn(y - rhs.y) < 0;
        return sgn(x - rhs.x) < 0;
    }
    Vector operator+(const Vector &rhs) const {
        return Vector(x + rhs.x, y + rhs.y);
    }
    Vector operator-(const Vector &rhs) const {
        return Vector(x - rhs.x, y - rhs.y);
    }
    Vector operator*(const double &rhs) const {
        return Vector(x * rhs, y * rhs);
    }
    Vector operator/(const double &rhs) const {
        return Vector(x / rhs, y / rhs);
    }
    double getAngle() { return atan2(y, x); }
    double squre() const { return x * x + y * y; }
    double distance() const { return sqrt(squre()); }
    void print(bool flag = 0) const {
        Log("(%.2f %.2f)", x, y);
        if (flag)
            Log("\n");
    }
};
typedef Vector Point;
struct Segment {
    Point a, b;
    Segment() {}
    Segment(Point _a, Point _b) : a(_a), b(_b) {}
    bool operator<(const Segment &rhs) const {
        double angle1 = getAngle();
        double angle2 = rhs.getAngle();
        if (sgn(angle1 - angle2) == 0)
            return Point_Segment(a, rhs) > 0;
        return sgn(angle1 - angle2) < 0;
    }
    double getAngle() const { return toVector().getAngle(); }
    Vector toVector() const { return b - a; }
    double distance() const { return toVector().distance(); }
    void print(bool flag = 0) const {
        a.print();
        Log(" -> ");
        b.print();
        if (flag)
            Log("\n");
    }
};
/**
    * 读入一个点的坐标
    * @return   读入的点
    */
inline Point read_Point() {
    double x, y;
    scanf("%lf%lf", &x, &y);
    return Point(x, y);
}
inline double xmult(const Vector &a, const Vector &b, const Vector &c) {
    return (a.x - c.x) * (b.y - c.y) - (b.x - c.x) * (a.y - c.y);
}
/**
    * 计算两个向量的叉积
    * @param a  向量1
    * @param b  向量2
    * @return   叉积
    */
inline double Cross(const Vector &a, const Vector &b) {
    return a.x * b.y - a.y * b.x;
}
/**
    * 计算两个向量的点积
    * @param a  向量1
    * @param b  向量2
    * @return   点积
    */
inline double Dot(const Vector &a, const Vector &b) {
    return a.x * b.x + a.y * b.y;
}
/**
    * 计算两点之间的距离
    * @param a  线段L1
    * @param b  线段L2
    * @return   两点间的距离
    */
inline double Distance(const Point &a, const Point &b) {
    return (a - b).distance();
}
/**
    * 点和直线的关系
    * @param p   目标点
    * @param L   目标直线
    * @return    1 在左侧,0 在直线上,-1在右侧
    */
inline int Point_Segment(const Vector &p, const Segment &L) {
    // printf("Point_segment %d\n", sgn(Cross(L.b - L.a, p - L.a)));
    return sgn(Cross(L.b - L.a, p - L.a));
}
/**
    * 计算两个线段(直线)是否平行
    * @param L1 L1的向量
    * @param L2 L2的向量
    * @return   返回是否平行
    */
bool parallel(const Vector &L1, const Vector &L2) {
    return sgn(Cross(L1, L2)) == 0;
}
/**
    * 计算两个直线的交点(需要确保不平行、重合)
    * @param L1 L1的向量
    * @param L2 L2的向量
    * @return   返回是否平行
    */
Point getIntersection(const Segment &L1, const Segment &L2) {
    Point ret = L1.a;
    double t = ((L1.a.x - L2.a.x) * (L2.a.y - L2.b.y) -
                (L1.a.y - L2.a.y) * (L2.a.x - L2.b.x)) /
               ((L1.a.x - L1.b.x) * (L2.a.y - L2.b.y) -
                (L1.a.y - L1.b.y) * (L2.a.x - L2.b.x));
    ret.x += (L1.b.x - L1.a.x) * t;
    ret.y += (L1.b.y - L1.a.y) * t;
    return ret;
}
/**
    * 计算两个线段的位置关系
    * @param L1 线段L1
    * @param L2 线段L2
    * @param p  返回交点坐标
    * @return   2   重叠
                1   相交
                0   延长线相交
                -1  平行
                -2  共线不交
    */
inline int Segment_Segment(const Segment &L1, const Segment &L2,
                           Point *p = NULL) {
    double a = L1.b.x - L1.a.x;
    double b = L2.b.x - L2.a.x;
    double c = L1.b.y - L1.a.y;
    double d = L2.b.y - L2.a.y;
    double f = a * d - b * c;
    // 平行或重叠
    if (sgn(f) == 0) {
        if (Point_Segment(L1.a, L2)) {
            // 平行
            return -1;
        } else {
            // 共线
            int len = max(max(Distance(L1.a, L2.a), Distance(L1.a, L2.b)),
                          max(Distance(L1.b, L2.a), Distance(L1.b, L2.b)));
            if (sgn(len - L1.distance() - L2.distance()) > 0) {
                // 共线不交
                return -2;
            } else {
                // 重叠
                return 2;
            }
        }
    }
    double g = L2.b.x - L1.a.x;
    double h = L2.b.y - L1.a.y;
    double t = (d * g - b * h) / f;
    double s = (-c * g + a * h) / f;
    if (p != NULL)
        *p = Point(L1.a.x + t * a, L1.a.y + t * c);
    // 在延长线上
    if (t < 0 || t > 1 || s < 0 || s > 1)
        return 0;
    // 线段相交
    return 1;
}
/**
    * 判断点是否在多边形内部
    * @param p              需要判断的点
    * @param polygon        多边形点集,需要保证有序
    * @param numberOfSide   多边形边数
    * @return   1 点在多边形内,0在多边形上, -1 点不在多边形内
    */
int Point_Polygon(const Point &p, const Point polygon[],
                  const int numberOfSide) {
    int res = Point_Segment(p, Segment(polygon[numberOfSide - 1], polygon[0]));
    for (int i = 1; i < numberOfSide; ++i)
        res = min(res, Point_Segment(p, Segment(polygon[i - 1], polygon[i])));
    return res;
}

const int maxn = 505;
Point Rec1[4], Rec2[4];
Segment s[maxn];
bool del[maxn];
int n;

// 保留里面的
bool judge1(int t, Point Rec[]) {
    bool era = false;

    int in[2]; // 两个点是否在矩形内
    in[0] = Point_Polygon(s[t].a, Rec, 4);
    in[1] = Point_Polygon(s[t].b, Rec, 4);

    if (in[0] == 0 && in[1] == 0) {
        // 正好在矩形上
        era = true;
    } else if (in[0] >= 0 && in[1] >= 0) {
        // 在矩形内部
        era = false;
    } else {
        // 交点个数
        int cnt = 0;
        Point p, pp[2];
        for (int i = 0; i < 4; i++) {
            if (1 ==
                Segment_Segment(s[t], Segment(Rec[i], Rec[(i + 1) % 4]), &p)) {
                pp[cnt++] = p;
            }
        }
        if (cnt == 2 && pp[0] == pp[1])
            --cnt;

        if (in[0] < 0 && in[1] < 0) {
            // 两个点都在矩形外部
            if (cnt == 0) {
                // 全部在矩形外部
                era = true;
            } else {
                if (cnt == 1) {
                    // 有一个交点
                    era = true;
                } else {
                    // 有两个交点
                    s[n++] = Segment(pp[0], pp[1]);
                    era = true;
                }
            }
        } else {
            // 一半在外面,一半在里面
            era = true;
            if (in[0] >= 0) {
                s[n++] = Segment(pp[0], s[t].a);
            } else {
                s[n++] = Segment(pp[0], s[t].b);
            }
        }
    }
    del[t] = era;
    return era;
}

// 保留外面的
bool judge2(int t, Point Rec[]) {
    bool era = false;

    int in[2]; // 两个点是否在矩形内
    in[0] = Point_Polygon(s[t].a, Rec, 4);
    in[1] = Point_Polygon(s[t].b, Rec, 4);

    if (in[0] == 0 && in[1] == 0) {
        // 正好在矩形上
        era = true;
    } else if (in[0] >= 0 && in[1] >= 0) {
        // 在矩形内部
        era = true;
    } else {
        // 交点个数
        int cnt = 0;
        Point p, pp[2];
        for (int i = 0; i < 4; i++) {
            if (1 ==
                Segment_Segment(s[t], Segment(Rec[i], Rec[(i + 1) % 4]), &p)) {
                pp[cnt++] = p;
            }
        }
        if (cnt == 2 && pp[0] == pp[1])
            --cnt;

        if (in[0] < 0 && in[1] < 0) {
            // 两个点都在矩形外部
            if (cnt == 0) {
                // 全部在矩形外部
                era = false;
            } else {
                if (cnt == 1) {
                    // 有一个交点
                    s[n++] = Segment(pp[0], s[t].a);
                    s[n++] = Segment(pp[0], s[t].b);
                    era = true;
                } else {
                    // 有两个交点
                    if (Distance(pp[0], s[t].a) + eps <
                        Distance(pp[1], s[t].b)) {
                        s[n++] = Segment(pp[0], s[t].a);
                        s[n++] = Segment(pp[1], s[t].b);
                    } else {
                        s[n++] = Segment(pp[1], s[t].a);
                        s[n++] = Segment(pp[0], s[t].b);
                    }

                    era = true;
                }
            }
        } else {
            // 一半在外面,一半在里面
            era = true;
            if (in[0] >= 0) {
                s[n++] = Segment(pp[0], s[t].b);
            } else {
                s[n++] = Segment(pp[0], s[t].a);
            }
        }
    }
    del[t] = era;
    return era;
}

void Erase() {
    int pos = 0, cnt = 0;
    for (int i = 0; i < n; ++i) {
        if (del[i]) {
            ++cnt;
            continue;
        } else {
            s[pos++] = s[i];
        }
    }
    n -= cnt;
    memset(del, false, sizeof(del));
}

void cmp1(Segment &t) {
    if (t.b < t.a)
        swap(t.a, t.b);
}
bool cmp2(Segment a, Segment b) {
    if (a.a == b.a)
        return b.b < a.b;
    return b.a < a.a;
}

int main() {
    Rec1[0] = read_Point();
    Rec1[2] = read_Point();
    Rec1[1] = Point(Rec1[2].x, Rec1[0].y);
    Rec1[3] = Point(Rec1[0].x, Rec1[2].y);

    Rec2[0] = read_Point();
    Rec2[2] = read_Point();
    Rec2[1] = Point(Rec2[2].x, Rec2[0].y);
    Rec2[3] = Point(Rec2[0].x, Rec2[2].y);

    n = 0;
    memset(del, false, sizeof(del));

    double x1, x2, y1, y2;
    while (~scanf("%lf%lf%lf%lf", &x1, &y1, &x2, &y2))
        s[n++] = Segment(Point(x1, y1), Point(x2, y2));

    // for (int i = 0; i < n; ++i)
    //     printf("%.4f %.4f %.4f %.4f\n", s[i].a.x, s[i].a.y, s[i].b.x,
    //     s[i].b.y);
    // printf("\n");

    int oldn = n;
    for (int i = 0; i < oldn; ++i)
        judge1(i, Rec1);
    Erase();

    // for (int i = 0; i < n; ++i)
    //     printf("%.4f %.4f %.4f %.4f\n", s[i].a.x, s[i].a.y, s[i].b.x,
    //     s[i].b.y);
    // printf("\n");

    oldn = n;
    for (int i = 0; i < oldn; ++i)
        judge2(i, Rec2);
    Erase();

    // for (int i = 0; i < n; ++i)
    //     printf("%.4f %.4f %.4f %.4f\n", s[i].a.x, s[i].a.y, s[i].b.x,
    //     s[i].b.y);
    // printf("\n");

    for (int i = 0; i < n; ++i)
        cmp1(s[i]);
    sort(s, s + n, cmp2);

    for (int i = 0; i < n; ++i)
        printf("%.4f %.4f %.4f %.4f\n", fabs(s[i].a.x), fabs(s[i].a.y),
               fabs(s[i].b.x), fabs(s[i].b.y));

    return 0;
}
发布评论
  • 点击查看/关闭被识别为广告的评论