Геометрические примитивы

Точки, прямые, лучи, отрезки, многоугольники

#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const double EPS = 1e-9;

struct Point {
    double x, y;

    Point() {}

    Point(double x, double y) : x(x), y(y) {}

    Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}

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

    bool operator != (const Point &that) const {
        return !(*this == that);
    }

    double angle() const {
        double a = atan2(y, x);
        if (a < -EPS)
            a += 2 * acos(-1.0);
        return a;
    }

    double length() const {
        return hypot(x, y);
    }

    double distanceTo(const Point &that) const {
        return Point(*this, that).length();
    }

    Point operator + (const Point &that) const {
        return Point(x + that.x, y + that.y);
    }

    Point operator - (const Point &that) const {
        return Point(x - that.x, y - that.y);
    }

    Point operator * (double k) const {
        return Point(x * k, y * k);
    }

    Point setLength(double newLength) const {
        double k = newLength / length();
        return Point(x * k, y * k);
    }

    double dotProduct(const Point &that) const {
        return x * that.x + y * that.y;
    }

    double angleTo(const Point &that) const {
        return acos(max(-1.0, min(1.0, dotProduct(that) / (length() * that.length()))));
    }

    bool isOrthogonalTo(const Point &that) const {
        return fabs(dotProduct(that)) < EPS;
    }

    Point orthogonalPoint() const {
        return Point(-y, x);
    }

    double crossProduct(const Point &that) const {
        return x * that.y - y * that.x;
    }

    bool isCollinearTo(const Point &that) const {
        return fabs(crossProduct(that)) < EPS;
    }
};

struct Line {
    double a, b, c;

    Line() {}

    Line(double a, double b, double c) : a(a), b(b), c(c) {}

    Line(const Point &p1, const Point &p2) : a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}

    static Line LineByVector(const Point &p, const Point &v) {
        return Line(p, p + v);
    }

    static Line LineByNormal(const Point &p, const Point &n) {
        return LineByVector(p, n.orthogonalPoint());
    }

    Point normal() const {
        return Point(a, b);
    }

    Line orthogonalLine(const Point &p) const {
        return LineByVector(p, normal());
    }

    Line parallelLine(const Point &p) const {
        return LineByNormal(p, normal());
    }

    Line parallelLine(double distance) const {
        Point p = (fabs(a) < EPS ? Point(0, -c / b) : Point(-c / a, 0));
        Point p1 = p + normal().setLength(distance);
        return LineByNormal(p1, normal());
    }

    int side(const Point &p) const {
        double r = a * p.x + b * p.y + c;
        if (fabs(r) < EPS)
            return 0;
        else
            return r > 0 ? 1 : -1;
    }

    double distanceTo(const Point &p) const {
        return fabs(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
    }

    bool has(const Point &p) const {
        return distanceTo(p) < EPS;
    }

    double distanceTo(const Line &that) const {
        if (normal().isCollinearTo(that.normal())) {
            Point p = (fabs(a) < EPS ? Point(0, -c / b) : Point(-c / a, 0));
            return that.distanceTo(p);
        } else
            return 0;
    }

    bool intersectsWith(const Line &that) const {
        return distanceTo(that) < EPS;
    }

    Point intersection(const Line &that) const {
        double d = a * that.b - b * that.a;
        double dx = -c * that.b - b * -that.c;
        double dy = a * -that.c - -c * that.a;
        return Point(dx / d, dy / d);
    }
};

struct Ray {
    Point p1, p2;
    double a, b, c;

    Ray(const Point &p1, const Point &p2) : p1(p1), p2(p2), a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}

    double distanceTo(const Point &p) const {
        if (Point(p1, p).dotProduct(Point(p1, p2)) >= -EPS)
            return fabs(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
        else
            return p1.distanceTo(p);
    }

    bool has(const Point &p) const {
        return distanceTo(p) < EPS;
    }

    double distanceTo(const Ray &that) const {
        Line l(a, b, c), thatL(that.a, that.b, that.c);
        if (l.intersectsWith(thatL)) {
            Point p = l.intersection(thatL);
            if (has(p) && that.has(p))
                return 0;
        }
        return min(distanceTo(that.p1), that.distanceTo(p1));
    }

    bool intersectsWith(const Ray &that) const {
        return distanceTo(that) < EPS;
    }
};

struct Segment {
    Point p1, p2;
    double a, b, c;

    Segment(const Point &p1, const Point &p2) : p1(p1), p2(p2), a(p1.y - p2.y), b(p2.x - p1.x), c(p1.x * p2.y - p2.x * p1.y) {}

    double distanceTo(const Point &p) const {
        if (Point(p1, p).dotProduct(Point(p1, p2)) >= -EPS && Point(p2, p).dotProduct(Point(p2, p1)) >= -EPS)
            return fabs(a * p.x + b * p.y + c) / sqrt(a * a + b * b);
        else
            return min(p1.distanceTo(p), p2.distanceTo(p));
    }

    bool has(const Point &p) const {
        return distanceTo(p) < EPS;
    }

    double distanceTo(const Segment &that) const {
        Line l(a, b, c), thatL(that.a, that.b, that.c);
        if (l.intersectsWith(thatL)) {
            Point p = l.intersection(thatL);
            if (has(p) && that.has(p))
                return 0;
        }
        return min(min(distanceTo(that.p1), distanceTo(that.p2)), min(that.distanceTo(p1), that.distanceTo(p2)));
    }

    bool intersectsWith(const Segment &that) const {
        return distanceTo(that) < EPS;
    }
};

struct Polygon {
    vector<Point> points;

    void addPoint(const Point &p) {
        points.push_back(p);
    }

    bool has(const Point &p) const {
        bool pos = 0, neg = 0;
        for (int i = 0; i < points.size(); i++) {
            const Point &a = points[i], &b = points[(i + 1) % points.size()];
            Point ab(a, b), ap(a, p);
            double cross = ab.crossProduct(ap);
            pos |= cross > EPS;
            neg |= cross < -EPS;
        }
        return !pos || !neg;
    }

    double perimeter() const {
        double p = 0;
        for (int i = 0; i < points.size(); i++)
            p += points[i].distanceTo(points[(i + 1) % points.size()]);
        return p;
    }

    double area() const {
        double s = 0;
        for (int i = 0; i < points.size(); i++)
            s += points[i].crossProduct(points[(i + 1) % points.size()]);
        return fabs(s) / 2;
    }
};

Точная проверка на пересечение отрезков с целыми координатами

struct Point {
    long long x, y;

    Point() {}
    Point(const Point &a, const Point &b) : x(b.x - a.x), y(b.y - a.y) {}

    long long crossProduct(const Point &that) const {
        return x * that.y - y * that.x;
    }
};


struct Segment {
    Point p1, p2;

    Segment(const Point &p1, const Point &p2) : p1(p1), p2(p2) {}

    bool intersectsWith(const Segment &that) const {
        long long abx1 = min(p1.x, p2.x), abx2 = max(p1.x, p2.x);
        long long cdx1 = min(that.p1.x, that.p2.x), cdx2 = max(that.p1.x, that.p2.x);
        if (max(abx1, cdx1) > min(abx2, cdx2))
            return 0;

        long long aby1 = min(p1.y, p2.y), aby2 = max(p1.y, p2.y);
        long long cdy1 = min(that.p1.y, that.p2.y), cdy2 = max(that.p1.y, that.p2.y);
        if (max(aby1, cdy1) > min(aby2, cdy2))
            return 0;

        Point ab(p1, p2), ac(p1, that.p1), ad(p1, that.p2);
        long long abc = ab.crossProduct(ac), abd = ab.crossProduct(ad);
        if (abc > 0 && abd > 0 || abc < 0 && abd < 0)
            return 0;

        Point cd(that.p1, that.p2), ca(that.p1, p1), cb(that.p1, p2);
        long long cda = cd.crossProduct(ca), cdb = cd.crossProduct(cb);
        if (cda > 0 && cdb > 0 || cda < 0 && cdb < 0)
            return 0;

        return 1;
    }
};

Ссылки

Теория:

• Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости / Е. В. Андреева, Ю. Е. Егоров. // Информатика. — 2002. — №39, 40, 43, 44
• Ахмедов М. Geometry, stereometry and spherical geometry
• E-maxx — Проверка двух отрезков на пересечение

Задачи:

• Codeforces 100168 — 2012-2013 Тренировка СПбГУ C #8. Геометрия. База.
• Задачи: Геометрия