相关文章推荐
烦恼的核桃  ·  Android图片加载框架最全解析(一),G ...·  1 周前    · 
坚韧的松鼠  ·  前沿 | ...·  1 周前    · 
乖乖的拐杖  ·  mongodb $lookup ...·  2 年前    · 
很拉风的啄木鸟  ·  VBA 格式化字符串 - Format大全 ...·  2 年前    · 
威武的绿豆  ·  交通运输部:网约车监管信息交互系统3月份共收 ...·  2 年前    · 
小眼睛的米饭  ·  涨姿势:利用AndroidStudio自带的 ...·  2 年前    · 
不爱学习的芒果  ·  技术分享:DNS过滤配置解析 - 知乎·  2 年前    · 
Code  ›  多边形包含点算法解释开发者社区
社区功能
https://cloud.tencent.com/developer/ask/sof/115256612
酷酷的枕头
1 年前
首页
学习
活动
专区
工具
TVP 最新优惠活动
返回腾讯云官网
提问

问 多边形包含点算法解释

Stack Overflow用户
提问于 2018-07-15 02:57:12
EN

我在许多不同的问题上见过这个解决方案的变体,所以关于包含点的多边形的问题,但是问题是没有一个作者给出任何解释。我似乎不知道这个函数是如何工作的,而且看到许多其他评论者对此的问题没有得到回答,我认为最好只是问一下,这样就会有一个具体的解释了。

此外,是否有此功能失败的情况?

更新:我知道光线投射方法是如何工作的,有一些非常好的资源,但是我真的很困惑这段代码具体是如何工作的。

代码语言: javascript
复制
public static bool(ean) PolygonContainsPoint(Point[] polygon, Point point)
    bool(ean) result = false;
    int j = polygon.Count - 1;
    for (int i = 0; i < polygon.Count; i++)
        if (polygon[i].Y < point.Y && polygon[j].Y >= point.Y || polygon[j].Y < point.Y && polygon[i].Y >= point.Y)
            if (polygon[i].X + (point.Y - polygon[i].Y) / (polygon[j].Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) < point.X)
                result = !result;
        j = i;
    return result;
}
1 112 0 票数 1
EN
algorithm
language-agnostic
geometry

回答 1

Stack Overflow用户

回答已采纳

发布于 2018-07-15 03:24:51

这是维基百科上描述的 光线投射算法 。

光线从多边形外部传递到任意点的交叉点数;如果是奇数,则表示该点位于多边形内。如果是偶数,点在多边形之外;这个测试也在三维上工作。

代码语言: javascript
复制
int j = polygon.Count - 1;
for (int i = 0; i < polygon.Count; i++)
    // ...
    j = i;
}

说明:代码循环遍历多边形的每个线段,其中 i 是当前点的索引, j 是前一点的索引(第一点的前一点是最后一点,因为多边形是关闭的)。

代码语言: javascript
复制
if (polygon[i].Y < point.Y && polygon[j].Y >= point.Y ||
    polygon[j].Y < point.Y && polygon[i].Y >= point.Y)

说明:如果多边形线段跨越线 O ,,即如果它从上面开始,结束在下面,或者开始在下面和上面结束。

代码语言: javascript
复制
if (polygon[i].X + (point.Y - polygon[i].Y)
    / (polygon[j].Y - polygon[i].Y)
 
推荐文章
烦恼的核桃  ·  Android图片加载框架最全解析(一),Glide的基本用法开发者社区
1 周前
坚韧的松鼠  ·  前沿 | GAN用于材料设计:哈佛大学新研究登上Science开发者社区
1 周前
乖乖的拐杖  ·  mongodb $lookup 之后再$project_MongoDB 如何实现嵌套子文档分组_weixin_39972768的博客-CSDN博客
2 年前
很拉风的啄木鸟  ·  VBA 格式化字符串 - Format大全 - 小时候可待亲了 - 博客园
2 年前
威武的绿豆  ·  交通运输部:网约车监管信息交互系统3月份共收到订单信息7.16亿单 环比上升9.7%_新浪财经_新浪网
2 年前
小眼睛的米饭  ·  涨姿势:利用AndroidStudio自带的Network Profiler来查看网络请求的相关数据_103style的博客-CSDN博客
2 年前
不爱学习的芒果  ·  技术分享:DNS过滤配置解析 - 知乎
2 年前
今天看啥   ·   Py中国   ·   codingpro   ·   小百科   ·   link之家   ·   卧龙AI搜索
删除内容请联系邮箱 2879853325@qq.com
Code - 代码工具平台
© 2024 ~ 沪ICP备11025650号