Jarvis步进法（Jarvis March）凸包算法

Jarvis步进法（也称为包裹法）： Jarvis步进法是一种逐步选择凸包顶点的算法。从点集中选择一个起始点，然后在每一步中选择下一个顶点，该顶点是当前点集中与当前点形成的线段上，极角最小的点。该算法的时间复杂度为O(nh)，其中n是点的数量，h是凸包的顶点数。请帮我使用 python 实现该算法，并且绘制出原始的离散点和凸包的点并连接成凸包多边形

Jarvis步进法（Jarvis March），又称为包裹法（Gift Wrapping），是一种求解平面点集凸包问题的算法。凸包是包含给定点集合的最小凸多边形。以下是Jarvis步进法的基本数学原理：

• 选择起始点： 算法首先需要选择一个起始点。通常情况下，选择最左下角的点，以确保算法的稳定性。选择起始点的过程可以通过遍历点集，找到y坐标最小的点，并在y坐标相同时，选择x坐标最小的点。

• 极角排序： 在选择了起始点之后，对剩余的点按照相对于当前点的极角进行排序。极角可以使用反正切函数（atan2）计算，它表示从当前点到其他点的线段与x轴正方向之间的夹角。排序后的点集顺序将决定扫描过程中点的访问顺序。

• 扫描过程： 从起始点开始，选择当前点（假设为p），然后选择下一个点（假设为q），这个点是当前点p与其他点形成的线段上，极角最小的点。通过比较极角大小，可以确定下一个点的选择。重复这个过程，直到回到起始点形成一个闭合的凸包。

• 构建凸包： 扫描完成后，选择的点序列就是凸包的顶点，这个顺序是按照逆时针方向排列的。

  关键思想是通过在每一步中选择具有最小极角的点，逐步构建凸包。这样可以确保在构建的凸包上，点的极角是递增的，最终形成一个逆时针方向的凸多边形。算法的时间复杂度主要取决于对点的排序操作，通常为O(n log n)，其中n是点的数量。 Jarivs步进法的优势在于其相对简单的实现和较好的性能。然而，在某些情况下，例如存在大量共线点的情况下，算法的性能可能会下降。

import matplotlib.pyplot as plt
import numpy as np

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def orientation(p, q, r):
    val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y)
    if val == 0:
        return 0  # 平行
    return 1 if val > 0 else 2  # 顺时针或逆时针

def jarvis_march(points):
    n = len(points)
    if n < 3:
        print("Jarvis March requires at least 3 points.")
        return []

    hull = []

    # 找到最左下角的点作为起始点
    start_point = min(points, key=lambda p: (p.y, p.x))
    current_point = start_point

    while True:
        hull.append(current_point)
        next_point = points[0]

        for candidate_point in points:
            if candidate_point != current_point:
                if next_point == current_point or orientation(current_point, next_point, candidate_point) == 2:
                    next_point = candidate_point

        current_point = next_point

        if current_point == start_point:
            break

    return hull

def plot_convex_hull(points, convex_hull):
    x_values = [point.x for point in points]
    y_values = [point.y for point in points]

    hull_x = [point.x for point in convex_hull]
    hull_y = [point.y for point in convex_hull]
    hull_x.append(convex_hull[0].x)  # 闭合凸包
    hull_y.append(convex_hull[0].y)

    plt.scatter(x_values, y_values, color='blue', label='Original Points')
    plt.plot(hull_x, hull_y, color='red', linestyle='-', linewidth=2, label='Convex Hull')

    plt.legend()
    plt.xlabel('X')
    plt.ylabel('Y')
    plt.title('Jarvis March Convex Hull')
    plt.grid(True)
    plt.show()

# 示例点集
new_points = [Point(1, 1), Point(2, 3), Point(4, 2), Point(5, 5), Point(7, 1), Point(8, 4), Point(9, 2), Point(10, 6)]

# 计算凸包
new_convex_hull_points = jarvis_march(new_points)

# 绘制原始离散点和凸包
plot_convex_hull(new_points, new_convex_hull_points)

#include <iostream>
#include <vector>
#include <algorithm>

class Point {
public:
    double x, y;

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

    // 定义 == 运算符
    bool operator==(const Point& other) const {
        return (x == other.x) && (y == other.y);
    }

    // 定义 != 运算符
    bool operator!=(const Point& other) const {
        return !(*this == other);
    }
};

int orientation(const Point& p, const Point& q, const Point& r) {
    double val = (q.y - p.y) * (r.x - q.x) - (q.x - p.x) * (r.y - q.y);
    if (val == 0) return 0;  // 平行
    return (val > 0) ? 1 : 2; // 顺时针或逆时针
}

std::vector<Point> jarvisMarch(const std::vector<Point>& points) {
    size_t n = points.size();
    if (n < 3) {
        std::cerr << "Jarvis March requires at least 3 points." << std::endl;
        return std::vector<Point>();
    }

    std::vector<Point> hull;
    Point start_point = *std::min_element(points.begin(), points.end(),
        [](const Point& p1, const Point& p2) {
            return (p1.y < p2.y) || (p1.y == p2.y && p1.x < p2.x);
        });
    Point current_point = start_point;

    while (true) {
        hull.push_back(current_point);
        Point next_point = points[0];

        for (const auto& candidate_point : points) {
            if (candidate_point != current_point) {
                if (next_point == current_point || orientation(current_point, next_point, candidate_point) == 2) {
                    next_point = candidate_point;
                }
            }
        }

        current_point = next_point;

        if (current_point == start_point) {
            break;
        }
    }

    return hull;
}

int main() {
    // 示例点集
    std::vector<Point> newPoints = { {1, 1}, {2, 3}, {4, 2}, {5, 5}, {7, 1}, {8, 4}, {9, 2}, {10, 6} };

    // 计算凸包
    std::vector<Point> newConvexHullPoints = jarvisMarch(newPoints);

    // 打印凸包点信息
    std::cout << "Convex Hull Points:" << std::endl;
    for (const auto& point : newConvexHullPoints) {
        std::cout << "(" << point.x << ", " << point.y << ")" << std::endl;
    }

    return 0;
}