美文网首页
一种判断点在多边形内算法猜想

一种判断点在多边形内算法猜想

作者: 寽虎非虫003 | 来源:发表于2021-11-28 13:04 被阅读0次

    一、目前已有的一些算法

    有转角法;
    弧度法;
    面积法;
    叉乘法;
    射线法;

    二、想法

    但是像这里的差乘法,好多资料只说了只适用于凸多边形。我就在想,是否可以基于叉乘计算出的正向面积或者反向面积的数量来进行计数来判断呢?
    以逆时针方向为正向。
    比如,假设点在多边形内,那么,点至少会在多边形的边集某中3条边延长线所围成的三角形中,问题的第一步就转换成了该多边形边集中,是否至少存在一个可以由三条边的延长线所围成的三角形包含求需要判别的点,即,该点在可围成三角形的三条边的左侧,即:点在三条互不平行的边的左侧。
    那么我们计算该点在多边形的多少条边的左侧,多少条边的右侧,左侧的边数,减去右侧的边数的差值至少为3。


    点是否在多边形内

    如图中所示:
    F点在4条边的左侧,在1条边CD的右侧,4-1>=3;
    K点同理。
    I点在4条边左侧,在一条边AB右侧,4-1>=3,猜想失败。

    相关文章

      网友评论

          本文标题:一种判断点在多边形内算法猜想

          本文链接:https://www.haomeiwen.com/subject/yegcxrtx.html