C++ 中的皮克定理

皮克定理是计算几何学中的一个基本思想，它利用一个简单而强大的概念来计算多边形面积，前提是多边形的所有顶点都位于由整数网格点构成的网格上。Georg Alexander Pick 于1899年引入了该定理。

该定理指出，对于任何一个简单的多边形（不自相交的多边形），如果其顶点位于格点上，则可以通过两个量来计算其面积：严格位于多边形内部的格点数（I）和位于边界上的格点数（B）。面积（A）的计算公式为：A=I+(B/2)-1

该定理对这种关系提供了一个有用的几何解释，这在输入数据通常使用整数坐标的计算问题中尤其有价值。皮克的方法在计算上非常高效且易于实现。

由于边界上的每个格点都与其他多边形相邻，因此边界项对面积的贡献被减半。皮克定理用于具有格点顶点的多边形，其数量不限，不适用于三维多边形。在其适用范围内，它具有无与伦比的简洁性和效率，已成为算法设计和计算几何的首选工具。学习皮克定理有助于我们理解离散数学和几何之间的关系。

方法一：朴素的暴力枚举方法

在这种方法中，我们迭代多边形边界框内的每个格点，直到找到内部点（I）的数量和边界点（B）的数量。第一步是计算多边形的边界框，即包含整个多边形的最小矩形。对于边界框内的每个格点，它会确定该点是完全位于多边形内部还是边界上。该方法通过执行点在多边形内测试（射线投射）来找到内部点，并通过验证边界点是否满足位于多边形边上的条件来确定边界点。

一旦计算出 I 和 B，就使用皮克定理计算多边形的面积：面积=I+ (B/2)-1

虽然这种方法简单直观，但计算成本很高，因为它会检查边界框内的所有格点。因此，它仅作为学习的良好示例，在边界框较小的情况下多边形适用。

程序

输出

Polygon Area Calculation using Pick's Theorem
1. Use default polygon
2. Input custom polygon
3. Exit
Enter your choice: 1
Bounding Box Dimensions:
Min X: 0, Max X: 4
Min Y: 0, Max Y: 3
Boundary Points (B): 14
Details:
(0, 0) (0, 1) (0, 2) (0, 3) (1, 0) (1, 3) (2, 0) (2, 3) (3, 0) (3, 3) (4, 0) (4, 1) (4, 2) (4, 3) 
Interior Points (I): 6
Details:
(1, 1) (1, 2) (2, 1) (2, 2) (3, 1) (3, 2) 
Area of the Polygon: 12
Bounding Box Visualization:
* * * * * 
* + + + * 
* + + + * 
* * * * * 
Polygon Area Calculation using Pick's Theorem
1. Use default polygon
2. Input custom polygon
3. Exit
Enter your choice: 2
Enter the number of vertices: 3
Enter the vertices (x y):
2 3
5 2
1 4
Bounding Box Dimensions:
Min X: 1, Max X: 5
Min Y: 2, Max Y: 4
Boundary Points (B): 4
Details:
(1, 4) (2, 3) (3, 3) (5, 2) 
Interior Points (I): 0
Details:
Area of the Polygon: 1
Bounding Box Visualization:
* . . . . 
. * * . . 
. . . . * 
Polygon Area Calculation using Pick's Theorem
1. Use default polygon
2. Input custom polygon
3. Exit
Enter your choice: 3
Exiting program. Goodbye!   

说明

结构定义

首先，我们定义一个 Point 结构，它用整数 x 和 y 坐标表示格点，并说明我们如何通过整数定义它们。接下来，这是关于多边形顶点和格点所有计算的基础。

边界框计算

计算边界框函数，它告诉我们多边形顶点的最小和最大 x 和 y 坐标。这些值是多边形的边界框（最小矩形）。重要的是要遍历所有可能的格点，对我们正在定义的面积取模。

边界框计算

calculateBoundingBox 函数确定多边形顶点的最小和最大 x 和 y 坐标。这些值定义了包围多边形的最小矩形（边界框）。这对于遍历指定区域内的所有可能的格点至关重要。

边界点检测

isOnBoundary 函数确定一个给定点是否位于多边形边上。它使用斜率方程检查点与线段之间的共线性，并确保点落在线段的范围内。这有助于准确识别边界点（B）。

点在多边形内测试

isInsidePolygon 函数实现了射线投射算法，该算法确定一个点是否位于多边形内部。通过计算从该点发出的水平射线与多边形边的交点数量，可以推断出该点是位于多边形内部（奇数次交叉）还是外部（偶数次交叉）。

可视化

visualizeBoundingBox 函数使用符号概念性地表示边界框和格点：* 表示边界点，+ 表示内部点，. 表示空白。它有助于用户理解边界框和格点的分布。

面积计算

程序遍历所有格点，使用边界框。内部点（I）是多边形内的点，边界点（B）是边上的点。程序使用皮克定理计算面积（面积=I+ (B/2)-1）。

程序输出

• 边界框尺寸。
• 所有内部点和边界点的列表。
• 计算出的多边形面积。
• 边界框的详细可视化。

复杂度分析

时间复杂度

决定程序时间复杂度的主要因素是遍历边界框的所有格点。程序查找每个点，以确定多边形边界和多边形内的位置。对于每个格点遍历 n 个多边形边，时间复杂度为 O(A)（其中 A 是边界框的面积）。

然而，它还包括其他操作，如计算边界框尺寸和输出生成，但主要成本实际上是 n 条边和 A 个格点的双重迭代。

空间复杂度

空间复杂度由存储多边形顶点、内部点和边界点决定。然而，我们为多边形顶点维护 O(n) 的空间，为内部点和边界点维护 O(A) 的空间。因此，总空间复杂度为 O(n+A)。

只要空间使用得当，对于具有大型边界框的大型多边形，所需的格点存储可能会变得非常巨大。因此，边界框内的格点数量，以及由此可能导致的低效执行（当需要边界的多边形较大时），主导了空间复杂度。

方法二：扫描线法

使用最优扫描线算法，我们可以以比暴力枚举少得多的成本更简洁地计算多边形的面积。扫描线方法不检查边界框中的每个格点，而是检查多边形与一系列（扫描线）水平线的交点。它仅处理感兴趣的交点，以减少不必要的计算。

该算法因此跨越每条扫描线，并针对每条扫描线，确定扫描线与多边形边的交点，从而确定多边形何时穿过水平线。我们找到这些交点，然后程序计算扫描线上交点之间的格点，并将它们视为内部点。通过检查是否有任何格点恰好位于多边形的边上，我们识别出边界点。

处理的格点数量的减少使得方法更加高效，尤其对于形状不规则且格点数量不多于暴力枚举法相比的非平凡形状的多边形，其效率显著提高。

程序

输出

Enter number of vertices in the polygon: 4
Enter the coordinates of the vertices (x y):
2 3
4 3
5 2
4 2
Polygon vertices:
(2, 3)
(4, 3)
(5, 2)
(4, 2)
Area of the polygon using Pick's Theorem: 1.5   

说明

点结构

顶点的 x 和 y 坐标由点结构表示，其中包含整数 x 和 y 坐标。这使得处理多边形顶点和格点更加容易。

交点计算

find 函数检查给定的多边形线是否与水平扫描线（即由固定 y 值给定）相交，如果相交，则计算该多边形边与其相交的位置。为了找出交点的 x 坐标，该公式在两个多边形顶点之间进行线性插值。

边界点检查

isBoundary 函数确定一个点是否是多边形的一条边。用于检查点与边之间共线性以及验证点是否位于线段范围内的直线方程。

面积计算

calculateArea 函数通过使用皮克定理获取多边形的面积。它首先通过计算最小和最大 x 和 y 值来确定多边形的边界框。然后，它遍历每条水平扫描线（从最小 y 到最大 y），并找到扫描线与多边形边的交点。

该函数收集每条扫描线的交点，对它们进行排序，并计算连续交点之间的内部点。它仅计算位于边界或多边形内的格点。

输入和输出

用户输入多边形的顶点。然后，程序使用皮克定理计算并显示多边形的面积，以及多边形的顶点。

复杂度分析

时间复杂度

最优扫描线算法的时间复杂度取决于多边形边的数量和扫描线的数量。给定一个有 n 个顶点的多边形，设边界框高度为 h（最大 y 坐标减去最小 y 坐标），令 n 为顶点数。它计算每条扫描线与多边形边的交点，需要 O(n) 操作。而暴力法是 O(n×h)，而每条扫描线排序交点需要 O(n×h+klogk)，这提供了更有效的解决方案。

空间复杂度

这取决于多边形顶点、交点和边界点的存储，每个都有其自己的空间复杂度。对于每条扫描线，程序将交点存储在 O(k) 大小的临时 数组中，并将多边形顶点存储在大小为 O(n) 的数组中。因此，空间复杂度为 O(n+k)。