C++ 角度扫描算法

2025年3月22日 | 阅读4分钟

在本文中，我们将讨论 C++ 中的角度扫描算法及其实现。

这意味着我们需要确定在给定一组 2-D 点的情况下，半径为 r 的圆所包含（位于圆内而非圆周上）的点的最大数量。为此，角度扫描算法是最有效的技术。在计算几何中，角度扫描算法用于多种目的，包括确定一组点的凸包。

以下示例说明了如何使用角度扫描算法找到一组点的凸包：

示例 1

输入 {{0, 3}, {1, 1}, {2, 2}, {4, 4}, {0, 0}, {1, 2}, {3, 1}, {3, 3}}

输出 {(0, 0), (0, 3), (4, 4), (3, 1), (3, 3)}

示例 2

输入 {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}}

输出 {(0, 0), (4, 4), (3, 3)}

它确定了在给定 2 维平面上的 "n" 个点的情况下，半径为 "R" 的固定半径圆可能包围的最大点数。

注意：即使一个点在圆周上，它仍然被认为是位于圆内。

例如

输入：R = 1

点[] = {(8.65844, 5.67258), (4.25496 6.94715), (7.68547 7.58552)}

输出：2

最大点数为 2，

程序

让我们举一个例子来说明 C++ 中的角度扫描算法。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
struct Point {
    int a, b;
};
Point z1;  // Global variable for the reference point of the convex hull
Point nextToTop(std::vector<Point>& S1) {
    Point p = S1.back();
    S1.pop_back();
    Point res = S1.back();
    S1.push_back(p);
    return res;
}
// Utility function to swap two points
void swap(Point& z2, Point& z3) {
    Point temp = z2;
    z2 = z3;
    z2 = temp;
}

// Utility function to find the square of the Euclidean distance between two points
int distSq(Point z2, Point z3) {
    return (z2.a - z3.a)*(z2.a - z3.a) + (z2.b - z3.b)*(z2.b - z3.b);
}
// Function to compare two points based on their polar angle
int compare(const void* vp1, const void* vp2) {
    Point* z2 = (Point*)vp1;
    Point* z3 = (Point*)vp2;
    // Find orientation
    int orient = (z2->b - z1.b) * (z3->a - z2->a) - (z2->a - z1.a) * (z3->b - z2->b);
    if (orient == 0)
        return (distSq(z1, *z3) >= distSq(z1, *z2)) ? -1: 1;

    return (orient < 0)? -1: 1;
}
// Function to perform the Angular Sweep Algorithm
void convexHull(std::vector<Point>& points) {
    // Find the bottommost point
    int bmin = points[0].b, min = 0;
    for (int i = 1; i < points.size(); i++) {
        int b = points[i].b;
        // Pick the bottom-most or chose the left-most point in case of a tie
        if ((b < bmin) || (bmin == b && points[i].a < points[min].a))
            bmin = points[i].b, min = i;
    }

    // Place the bottom-most point at first position
    swap(points[0], points[min]);
    // Sort n-1 points concerning the first point
    // A point z2 comes before z3 in sorted output if z3 has larger polar angle (in counterclockwise direction) than z2
    z1 = points[0];
    qsort(&points[1], points.size() - 1, sizeof(Point), compare);

    // If two or more points make same angle with z1, remove all but the one that is farthest from z1
    int m = 1; // Initialize size of modified array
    for (int i = 1; i < points.size(); i++) {
        // Keep removing i while angle of i and i+1 is same with respect to z1
        while (i < points.size() - 1 && compare(&points[i], &points[i + 1]) == 0)
            i++;
        points[m] = points[i];
        m++; // Update size of modified array
    }
    if (m < 3) return; // Convex hull not possible
    // Create an empty stack and push the first three points to it
    std::vector<Point> S1;
    S1.push_back(points[0]);
    S1.push_back(points[1]);
    S1.push_back(points[2]);
    // Process remaining n-3 points
    for (int i = 3; i < m; i++) {
        // Keep removing top while the angle formed by points next-to-top, top, and points[i] makes a non-left turn
        while (S1.size() > 1 && ((S1[S1.size() - 1].b - S1[S1.size() - 2].b) * (points[i].a - S1[S1.size() - 1].a) -
            (S1[S1.size() - 1].a - S1[S1.size() - 2].a) * (points[i].b - S1[S1.size() - 1].b)) <= 0)
            S1.pop_back();
        S1.push_back(points[i]);
    }
    // Print convex hull points
    for (int i = 0; i < S1.size(); i++)
        std::cout << "(" << S1[i].a << ", " << S1[i].b << ")" << std::endl;
}
int main() {
    std::vector<Point> points = {{0, 3}, {1, 1}, {2, 2}, {4, 4},
                                  {0, 0}, {1, 2}, {3, 1}, {3, 3}};
    convexHull(points);
    return 0;
}

输出

下一主题C++ 中原子标志和原子布尔值的区别

C++ 角度扫描算法

注意：即使一个点在圆周上，它仍然被认为是位于圆内。

程序

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 角度扫描算法

注意：即使一个点在圆周上，它仍然被认为是位于圆内。

程序

相关帖子

C++ Delaunay 三角剖分

C++ 模板与多态的区别

C++ 中的洛布数

C++ std::remove_extent

C++ Manber 算法

C++ 中的订婚数

C++ 中静态队列与单向链表的区别

C++ std::tmpnam

C++ std::ranges::lazy_split 函数

C++ 中遇到数字时反转字符串

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器