Выпуклая оболочка: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
(не показаны 3 промежуточные версии этого же участника)
Строка 4: Строка 4:
* Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.
* Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.


{|
  struct Point {
| width="50%"  | 
     double x, y;
 
  struct P {  
     Point() {}
     double x, y;  
     P(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 y < that.y || y == that.y && x < that.x;
    }
     double length() const {
     double length() const {
         return sqrt(y * y + x * x);
         return hypot(x, y);
     }  
     }
     double cross(const P &p) const {
         return x * p.y - y * p.x;
     double crossProduct(const Point &that) const {
     }  
         return x * that.y - y * that.x;
     }
  };
  };
   
   
  bool compareByCoords(const P &a, const P &b) {
  vector<Point> convexHull(vector<Point> &points) {
     return a.y &lt; b.y || (a.y == b.y && a.x &lt; b.x);
     nth_element(points.begin(), points.begin(), points.end());
}
    sort(points.begin() + 1, points.end(), [&](Point &a, Point &b) {
        Point &o = points[0], oa(o, a), ob(o, b);
P o(0, 0);
        return oa.crossProduct(ob) > 0 || oa.crossProduct(ob) == 0 && oa.length() < ob.length();
bool compareByAngle(const P &a, const P &b) {
    });
    P va(a.x - o.x, a.y - o.y), vb(b.x - o.x, b.y - o.y);
    return va.cross(vb) &gt; 0 || (va.cross(vb) == 0 && va.length() < vb.length());
}
 
| width="10px" |
| width="50%"  |
  vector&lt;P&gt; convexHull(vector&lt;P&gt; &p) {
    sort(p.begin(), p.end(), compareByCoords);
    o = p[0];
    sort(p.begin() + 1, p.end(), compareByAngle);
   
   
     vector&lt;P&gt; hull;
     vector<Point> hull;
     for (int i = 0; i &lt; p.size(); i++) {
     for (Point &p : points) {
         while (hull.size() &gt;= 2) {
         while (hull.size() >= 2) {
             P &o = hull[hull.size() - 2], &a = hull[hull.size() - 1], &b = p[i];
             Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1];
             P oa(a.x - o.x, a.y - o.y), ob(b.x - o.x, b.y - o.y);
             Point ab(a, b), ap(a, p);
             if (oa.cross(ob) &lt;= 0)
             if (ab.crossProduct(ap) <= 0)
                 hull.pop_back();
                 hull.pop_back();
             else
             else
                 break;
                 break;
         }
         }
         hull.push_back(p[i]);
         hull.push_back(p);
     }
     }
     return hull;
     return hull;
  }
  }
|}


== Ссылки на задачи ==
== Ссылки ==
* [http://acmp.ru/?main=task&id_task=374 ACMP #374 &mdash; Выпуклая оболочка - 2]
Теория:
* [http://e-maxx.ru/algo/convex_hull_graham e-maxx.ru — Построение выпуклой оболочки обходом Грэхэма]
* [https://cp-algorithms.com/geometry/grahams-scan-convex-hull.html cp-algorithms.com — Convex Hull construction using Graham's Scan]
* algorithmica.org — Выпуклая оболочка: [https://algorithmica.org/ru/convex-hulls 1], [https://ru.algorithmica.org/cs/convex-hulls/graham/ 2]
* [http://e-maxx.ru/bookz/files/andreeva.pdf Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости]
* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures &mdash; 2.1 Elementary Sorts]
* [https://usaco.guide/plat/convex-hull?lang=cpp usaco.guide — Convex Hull]
Демонстрация:
* [http://visualgo.net/en/convexhull VisuAlgo &mdash; Convex Hull]
Код:
* [https://github.com/indy256/codelibrary/blob/master/cpp/geometry/convex_hull.cpp indy256/codelibrary/cpp/geometry/convex_hull.cpp]
* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp ADJA/algos/Geometry/convex_hull_graham_scan.cpp]
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/GrahamScan.java kevin-wayne/algs4/GrahamScan.java]
Задачи:
* [http://informatics.mccme.ru/course/view.php?id=22 informatics.mccme.ru &mdash; Курс &laquo;Геометрия&raquo; &mdash; часть 3]
* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=290 MCCME #290 &mdash; Выпуклая оболочка (периметр и площадь)]
* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=290 MCCME #290 &mdash; Выпуклая оболочка (периметр и площадь)]
* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=638 MCCME #638 &mdash; Выпуклая оболочка - периметр]
* [http://informatics.mccme.ru/mod/statements/view3.php?chapterid=638 MCCME #638 &mdash; Выпуклая оболочка - периметр]
 
* [http://acmp.ru/?main=task&id_task=374 ACMP #374 &mdash; Выпуклая оболочка - 2]
== Ссылки ==
* [http://informatics.mccme.ru/course/view.php?id=22 informatics.mccme.ru &mdash; Курс &laquo;Геометрия&raquo; &mdash; часть 3]
* [http://www.cs.princeton.edu/courses/archive/fall12/cos226/lectures/21ElementarySorts.pdf www.cs.princeton.edu/~cos226/lectures &mdash; 2.1 Elementary Sorts]
* [http://e-maxx.ru/bookz/files/andreeva.pdf Андреева Е. В., Егоров Ю. Е. Вычислительная геометрия на плоскости]
* [http://visualgo.net/geometry.html VisuAlgo &mdash; (Computational) Geometry]
* [http://github.com/ADJA/algos/blob/master/Geometry/convex_hull_graham_scan.cpp Algos &mdash; Graham scan]


[[Категория:Геометрия]]
[[Категория:Геометрия]]

Текущая версия от 11:47, 9 октября 2022

  • Любая экстремальная точка (например, самая левая из самых нижних) всегда принадлежит выпуклой оболочке. Сортируем точки по координатам, выбираем экстремальную точку O.
  • Сортируем остальные почки по полярному углу от O. Точка A должна идти раньше точки B, если поворот от вектора OA к вектору OB происходит против часовой стрелки (косое произведение положительно). Если OA и OB коллинеарны, то раньше идёт точка, ближайшая к O.
  • Добавляем точку O в оболочку.
  • Рассматриваем остальные точки в порядке сортировки по углу. Пока две последние точки оболочки вместе с новой точкой лежат на одной прямой или дают поворот по часовой стрелке (косое произведение неотрицательно), выкидываем последнюю точку из оболочки. Добавляем следующую точку в оболочку.
struct Point {
    double x, y;

    Point() {}

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

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

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

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

vector<Point> convexHull(vector<Point> &points) {
    nth_element(points.begin(), points.begin(), points.end());
    sort(points.begin() + 1, points.end(), [&](Point &a, Point &b) {
        Point &o = points[0], oa(o, a), ob(o, b);
        return oa.crossProduct(ob) > 0 || oa.crossProduct(ob) == 0 && oa.length() < ob.length();
    });

    vector<Point> hull;
    for (Point &p : points) {
        while (hull.size() >= 2) {
            Point &a = hull[hull.size() - 2], &b = hull[hull.size() - 1];
            Point ab(a, b), ap(a, p);
            if (ab.crossProduct(ap) <= 0)
                hull.pop_back();
            else
                break;
        }
        hull.push_back(p);
    }
    return hull;
}

Ссылки

Теория:

Демонстрация:

Код:

Задачи: