amobbs.com 阿莫电子技术论坛

标题: 有偿（300¥）：判断一个点是否在封闭形状内的算法 [打印本页]
作者: 1a2b3c    时间: 2020-7-11 09:05
标题: 有偿（300¥）：判断一个点是否在封闭形状内的算法
还是300元寻一个算法函数：判断某一个点（x，y）是否在一个已知的封闭区域（目前起来看只有圆形和多边形这两种情况）内，封闭区域的参数为圆形的圆心及半径（圆心x1，y1；半径r米），以及多边形各个点（分别为x1，y1，x2，y2。。。xn，yn，n最大限定为100）。坐标均为浮点数的经纬度值。圆半径也是浮点。当然有更好的模式可以自行优化，因为用于mcu中，可能希望是速度快以及消耗资源小了：）
作者: k_er_tlwei    时间: 2020-7-11 09:31
圆形好判断，点到圆心的距离少于直径就在圆内。多边形，就判断点同在多边形所有边的的“右边”或同在“左边”。
作者: zouzhichao    时间: 2020-7-11 09:34
我有代码，报价3000
作者: 浮华一生    时间: 2020-7-11 09:35
和 GUI 的裁剪算法 类似吧。 网上搜搜
作者: iamseer    时间: 2020-7-11 09:44
本帖最后由 iamseer 于 2020-7-11 10:27 编辑

圆形很简单，算一下到圆心距离然后和半径比比。

多边形最简单的方法是射线法，一点朝任意方向做射线，和多边形相交次数为奇数则在多边形中。最简单射线那就是朝右

  1. #define MIN(x,y) (x < y ? x : y)
  2. #define MAX(x,y) (x > y ? x : y)
  3. #define INSIDE 0
  4. #define OUTSIDE 1

  6. typedef struct {
  7.    double x,y;
  8. } Point;

  10. int InsidePolygon(Point *polygon,int N,Point p)
  11. {
  12.   int counter = 0;
  13.   int i;
  14.   double xinters;
  15.   Point p1,p2;

  17.   p1 = polygon[0];
  18.   for (i=1;i<=N;i++) {
  19.     p2 = polygon[i % N];
  20.     if (p.y > MIN(p1.y,p2.y)) {
  21.       if (p.y <= MAX(p1.y,p2.y)) {
  22.         if (p.x <= MAX(p1.x,p2.x)) {
  23.           if (p1.y != p2.y) {
  24.             xinters = (p.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y)+p1.x;
  25.             if (p1.x == p2.x || p.x <= xinters)
  26.               counter++;
  27.           }
  28.         }
  29.       }
  30.     }
  31.     p1 = p2;
  32.   }

  34.   if (counter % 2 == 0)
  35.     return(OUTSIDE);
  36.   else
  37.     return(INSIDE);
  38. }
复制代码


[attach]519898[/attach]

gif图片在手机上渲染不正确，补个jpg
[attach]519903[/attach]

另外 https://stackoverflow.com/questi ... is-within-a-polygon 还提到一点比较重要的优化：先找到多边形的外接长方形。如果点在外接长方形里面的话再进一步分析，否则就不用跑这套算法。

你既然提到是MCU上跑，那么分支的开销应该比三角函数运算的开销低。另一种算法卷绕法应该不合适。

http://www.eecs.umich.edu/course ... OJ2/InsidePoly.html
作者: zhd1021    时间: 2020-7-11 09:55
网上找到的
struct Point
{
    double x, y;
};
bool IsInPolygon(Point p,Point *ptPolygon,int ncount)
{
    int ncross = 0;
    for (int i = 0; i < ncount; i++)
    {
        Point p1 = ptPolygon;
        Point p2 = ptPolygon[(i + 1) % ncount]; //相邻两条边p1,p2
        if (p1.y == p2.y)         
            continue;
        if (p.y < min(p1.y, p2.y))
            continue;
        if (p.y >= max(p1.y, p2.y))
            continue;
        double x = (p.y - p1.y)*(p2.x - p1.x) / (p2.y - p1.y) + p1.x;
        if (x > p.x)
            ncross++; //只统计单边交点
    }
    return(ncross % 2 == 1);
}

链接：https://blog.csdn.net/qq_27161673/article/details/52973866
https://blog.csdn.net/F2304/arti ... earnPai2-2.nonecase
作者: jasonzhu8888    时间: 2020-7-11 09:57
本帖最后由 jasonzhu8888 于 2020-7-11 10:04 编辑

  2. struct Point
  3. {
  4.         float x;
  5.         float y;
  6. };

  8. bool circle_contains(Point* p_center, float radius, float x, float y)
  9. {
  10.         float xx = p_center->x - x;
  11.         float yy = p_center->y - y;
  12.         return xx*xx + yy*yy <= radius*radius;
  13. }

  15. bool polygon_contains(Point* pypts,int num,float x, float y)
  16. {
  17.         int hits = 0;

  19.         int n = num - 1;
  20.         Point* plastpt = &pypts[n];
  21.         float lastx = plastpt->x;
  22.         float lasty = plastpt->y;
  23.         float curx, cury;

  25.         for (int i = 0; i < n; lastx = curx, lasty = cury, i++)
  26.         {
  27.                 Point* p = &pypts[i];
  28.                 curx = p->x;
  29.                 cury = p->y;

  31.                 if (cury == lasty)
  32.                 {
  33.                         continue;
  34.                 }

  36.                 float leftx;
  37.                 if (curx < lastx)
  38.                 {
  39.                         if (x >= lastx)
  40.                         {
  41.                                 continue;
  42.                         }
  43.                         leftx = curx;
  44.                 }
  45.                 else
  46.                 {
  47.                         if (x >= curx)
  48.                         {
  49.                                 continue;
  50.                         }
  51.                         leftx = lastx;
  52.                 }

  54.                 float test1, test2;
  55.                 if (cury < lasty)
  56.                 {
  57.                         if (y < cury || y >= lasty)
  58.                         {
  59.                                 continue;
  60.                         }
  61.                         if (x < leftx)
  62.                         {
  63.                                 hits++;
  64.                                 continue;
  65.                         }
  66.                         test1 = x - curx;
  67.                         test2 = y - cury;
  68.                 }
  69.                 else
  70.                 {
  71.                         if (y < lasty || y >= cury)
  72.                         {
  73.                                 continue;
  74.                         }
  75.                         if (x < leftx)
  76.                         {
  77.                                 hits++;
  78.                                 continue;
  79.                         }
  80.                         test1 = x - lastx;
  81.                         test2 = y - lasty;
  82.                 }

  84.                 if (test1 < (test2 / (lasty - cury) * (lastx - curx)))
  85.                 {
  86.                         hits++;
  87.                 }
  88.         }

  90.         return ((hits & 1) != 0);
  91. }
复制代码
作者: jasonzhu8888    时间: 2020-7-11 10:01
polygon_containes 前面两个参数是输入的多边形坐标，最好首尾的点是同一个形成闭环，也即是输入点至少4个
如  (x0 y0)  (x1 y1) ... (x n-1  y n-1) (x0 y0)
作者: jjj    时间: 2020-7-11 10:01
点到线的距离，
https://www.amobbs.com/thread-5728196-1-1.html
作者: AWEN2000    时间: 2020-7-11 10:15
这个是自动割草机上用的吧
作者: zouzhichao    时间: 2020-7-11 10:39
[attach]519909[/attach]
[attach]519908[/attach]
[attach]519907[/attach]
[attach]519906[/attach]
[attach]519905[/attach]
[attach]519904[/attach]
作者: 19504643    时间: 2020-7-11 11:43
zouzhichao 发表于 2020-7-11 10:39

厉害，matlab能生成 c 代码吧
作者: zouzhichao    时间: 2020-7-11 12:05
19504643 发表于 2020-7-11 11:43
厉害，matlab能生成 c 代码吧

c代码写的啊，matlab只是调用它做验证用的
作者: deadline2012    时间: 2020-7-11 12:19
如何判断一个点是否在多边形内部？ （1）面积和判别法：判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形，相等则在多边形内部。--采纳 （2）夹角和判别法：判断目标点与所有边的夹角和是否为360度，为360度则在多边形内部。 （3）引射线法：从目标点出发引一条射线，看这条射线和多边形所有边的交点数目。如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。  （4）转角法：按照多边形顶点逆时针顺序，根据顶点和判断点连线的方向正负（设定角度逆时针为正）求和判断；
作者: 1a2b3c    时间: 2020-7-14 09:24
感谢楼上各位的无私帮助，这几天耽搁了今天才来看到。
我不知道报酬该给哪一位了，当然我自己也都还没有来得及验证，不过一定会兑现的。
如果可以的话，可否私信给我，因为我是想直接使用经纬度作为参数，里面涉及到跨半球操作以及一些经纬度转换什么的不是很懂了，如果可以，就帮我一并处理一下 再次感谢
作者: skystalker    时间: 2020-7-14 10:43
这不就是禁飞区用得很普遍的算法。
作者: qwe2231695    时间: 2020-7-14 12:26
禁飞区算法合集
作者: 3466756555    时间: 2020-7-14 14:13
最早在部标的行车记录仪 上有过电子围栏算法
作者: haoran518    时间: 2020-7-14 14:20
网上搜射线法                     
作者: minisystem    时间: 2020-7-14 15:41
mark 最近可能会用到
作者: advarx21ic    时间: 2020-7-14 15:46
高手如云啊
作者: avrwoo    时间: 2020-7-15 21:40
学习一下这个算法。
作者: wangzheyu    时间: 2020-7-16 13:15
1a2b3c 发表于 2020-7-14 09:24
感谢楼上各位的无私帮助，这几天耽搁了今天才来看到。
我不知道报酬该给哪一位了，当然我自己也都还没有来 ...

用经纬度做参数的话，要做高斯-克吕格投影，有个复杂的计算公式。
作者: 1a2b3c    时间: 2020-7-16 14:49
wangzheyu 发表于 2020-7-16 13:15
用经纬度做参数的话，要做高斯-克吕格投影，有个复杂的计算公式。

是这样的，我的区域很小，撑死了就5公里的最大边距，所以是不是就无需要这样处理了呢？
而且也不是两极地区，误差也可以允许5米左右都可以。
作者: zouzhichao    时间: 2020-7-16 17:52
输入围栏经纬度，输入目标经纬度，输出目标是否在围栏内，支持半个球的跨程，单片机无缝移植，交期一个晚上，楼主可有性趣？
作者: 1a2b3c    时间: 2020-9-19 07:50
抱歉你这个回复今天才看到，我私信你吧
作者: AWEN2000    时间: 2020-9-19 08:11
楼主是做自动割草机的吧
作者: 1a2b3c    时间: 2020-9-19 08:34
回楼上和前面同样的问题，不是割草机和飞行的那些，之前都没有想到原来这个应该是一样的目的：）我是自己的一个想法，需要先验证一下，离实现整机还早，所以就需要个这样的功能，但自己又不会所以才来寻求帮助的，
作者: lin28    时间: 2024-3-21 08:38
不错，标记下



欢迎光临 amobbs.com 阿莫电子技术论坛 (https://www.amobbs.com/) Powered by Discuz! X3.4