概述
这是图形学中的一个经典问题(point-in-polygon),一种比较简易的判断方法是射线法,就是以判断点作为端点,朝着任意方向绘制一条射线。如果射线与多边形交点为奇数个,就说明此点在多边形内部。如果交点为偶数个,就说明此点在多边形外部。严格证明的话可以在网上根据关键词自行搜索,这里只是解释下这种方法,还有代码实现。
细节思考
交点奇数个在内部,偶数个在外部,虽然表述起来比较简单,但是这里还有细节条件需要约束,比如下面这三种情况。
A,B,C 三条射线都只跟多变形有一个交点,但是显然只有点 C 的端点在内部。这里的问题就在于,当射线跟多边形的顶点有交点时需要怎么计算?
虽然射线的方向可以任意,但我们平时为了计算方便,可以采用水平射线正方向,然后条件就是: 交点的 Y 坐标,需要大于线段的一其中个端点,小于等于另一个端点。 换成形象一点的理解方式就是,在射线”下面”的线段才会被计算,所以按照这种规则就是,A 算两个交点,B 算一个交点,C 没有交点,所以只有 C 在内部。
除此之外还有一种重合的情况,就是射线跟多边形的一条边重合了,其实按照上面的规则看,这种情况也属于没有交点。
代码实现
最后就是代码实现了,这里贴个 C语言 版的。
#include <stdio.h>
typedef struct
{
float x;
float y;
} Point;
// 多边形点坐标, 多边形点个数, 需要判断的点
int isInner(Point *poly, int num, Point p)
{
int flag = 0, i;
for (i = 0; i < num; i++)
{
// 多边形的边的两个点 p1, p2
Point p1 = poly[i];
Point p2 = poly[(i + 1) % num];
// 点的 Y 坐标一个大于等于,一个小于
if (p.y >= p1.y && p.y < p2.y || p.y >= p2.y && p.y < p1.y)
{
// 交点计算,两点式
float x = (p.y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y) + p1.x;
// 交点 X 坐标肯定在前
if (x > p.x)
{
flag++;
}
}
}
return flag % 2;
}
#define SIZEOF(T) (sizeof(T)/sizeof(T[0]))
int main()
{
Point a = {2, 3};
Point b = {3, 2};
Point c = {2, 1};
Point d = {-1, 0};
Point qz[] = {
{0, 0}, {3, 3}, {5, 2}, {4, 2}, {4, -1}, {3, 1}, {2, -1}, {1, 0}
};
printf("a, %d\n", isInner(qz, SIZEOF(qz), a));
printf("b, %d\n", isInner(qz, SIZEOF(qz), b));
printf("c, %d\n", isInner(qz, SIZEOF(qz), c));
printf("d, %d\n", isInner(qz, SIZEOF(qz), d));
return 0;
}
运行结果
a, 0
b, 1
c, 1
d, 0
补充
代码中交点计算主要用到了两点式:
如果对速度有要求的话,在计算交点之前可以多加点判断,比如 A B 两条线,显然 A 是没有交点的,因为 A 的两个端点的 X 轴坐标都要比判断点的 X 轴坐标小,几次大小比较可能要比计算交点快,这个看情况优化吧。
原文地址:http://www.cnblogs.com/asmer/p/16844861.html
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,请务用于商业用途!
3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员!
8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性