在计算几何中，我们经常会遇到一个问题：如何确定一个给定的点是位于多边形的内部、外部，还是边界上。这个问题就是著名的 “点在多边形内” 问题。它在计算机图形学、地理信息系统（GIS）和机器人技术等领域有着广泛的应用。
在本文中，我们将学习如何使用 C 语言来检查一个给定点是位于多边形内部还是外部。我们还将探讨实现这一目标的不同方法。
示例：
**输入：**
多边形: { { 0, 0 }, { 10, 0 }, { 10, 10 }, { 0, 10 } }
点: {20, 20};
**输出：**
点在多边形外部。
在 C 语言中解决点在多边形问题的方法
- 方法 1：使用射线投射算法
- 方法 2：使用环绕数算法
- 方法 3：使用边交叉算法
方法 1：使用射线投射算法
在这种方法中，我们首先从给定点向无穷远处投射一条水平射线，然后计算该射线与多边形边缘相交的次数。如果相交次数为奇数，则该点在多边形内部；如果是偶数，则该点在外部。
如下图所示，点 A 和 C 与多边形边相交一次，数量为奇数，因此点 A 和 C 在多边形内部；而点 B 和 D 与多边形边相交两次，数量为偶数，因此点 B 和 D 在多边形外部；此外，点 E 与多边形边的相交次数为 0，这也是偶数，因此它也位于多边形外部。我们可以从图中证实上述推测是正确的。
方法思路
> – 将交点计数器初始化为零。
> – 对于多边形的每一条边：
> – 检查该边是否与从点向右延伸的水平射线相交。
> – 如果相交，则增加交点计数器的值。
> – 如果交点计数器为奇数，则点在多边形内；如果为偶数，则点在多边形外。
使用射线投射算法检查点在多边形内的 C 程序
下面的程序演示了我们如何在 C 语言中使用射线投射算法来检查一个点是位于多边形内部还是外部。
C
// C program to check if a point is inside a polygon using
// ray-casting algorithm
#include
#include
#include
// Structure for a point
typedef struct {
double x, y;
} Point;
// Function to check if a point is on the boundary of a
// polygon edge
int onSegment(Point p, Point q, Point r)
{
if (q.x = fmin(p.x, r.x)
&& q.y = fmin(p.y, r.y))
return 1;
return 0;
}
// Function to find the orientation of the triplet (p, q, r)
// 0 –> p, q and r are collinear
// 1 –> Clockwise
// 2 –> Counterclockwise
int orientation(Point p, Point q, Point r)
{
double val = (q.y – p.y) * (r.x – q.x)
– (q.x – p.x) * (r.y – q.y);
// collinear
if (val == 0)
return 0;
// clock or counterclock wise
return (val > 0) ? 1 : 2;
}
// Function to check if two line segments intersect
int doIntersect(Point p1, Point q1, Point p2, Point q2)
{
int o1 = orientation(p1, q1, p2);
int o2 = orientation(p1, q1, q2);
int o3 = orientation(p2, q2, p1);
int o4 = orientation(p2, q2, q1);
// General case
if (o1 != o2 && o3 != o4)
return 1;
// Special Cases
// p1, q1 and p2 are collinear and p2 lies on segment
// p1q1
if (o1 == 0 && onSegment(p1, p2, q1))
return 1;
// p1, q1 and p2 are collinear and q2 lies on segment
// p1q1
if (o2 == 0 && onSegment(p1, q2, q1))
return 1;
// p2, q2 and p1 are collinear and p1 lies on segment
// p2q2
if (o3 == 0 && onSegment(p2, p1, q2))
return 1;
// p2, q2 and q1 are collinear and q1 lies on segment
// p2q2
if (o4 == 0 && onSegment(p2, q1, q2))
return 1;
return 0; // Doesn‘t fall in any of the above cases
}
// Function to check if the point p is inside the polygon
int isInside(Point polygon[], int n, Point p)
{
// Create a point for the ray (a point far outside the
// polygon)
Point extreme = { DBL_MAX, p.y };
int count = 0, i = 0;
do {
int next = (i + 1) % n;
if (doIntersect(polygon[i], polygon[next], p,
extreme)) {
if (orientation(polygon[i], p, polygon[next])
== 0)
return onSegment(polygon[i], p,
polygon[next]);
count++;
}
i = next;
} while (i != 0);
// Return true if count is odd, false otherwise
return count & 1;
}
int main()
{
Point polygon[]
= { { 0, 0 }, { 10, 0 }, { 10, 10 }, { 0, 10 } };
int n = sizeof(polygon) / sizeof(polygon[0]);
Point p = { 20, 20 };
isInside