做饰品一般用什么网站做首饰,linux安装wordpress无法访问,2013网站设计,长沙网站推广优化1.前言#xff1a;
在GIS开发中#xff0c;经常会遇到确定一个坐标点是否在一块区域的内部这一问题。 如果这个问题不是一个单纯的数学问题#xff0c;例如#xff1a;在判断DEM、二维图像像素点、3D点云点等含有自身特征信息的这些点是否在一个区域范围内部的时候#x…1.前言
在GIS开发中经常会遇到确定一个坐标点是否在一块区域的内部这一问题。 如果这个问题不是一个单纯的数学问题例如在判断DEM、二维图像像素点、3D点云点等含有自身特征信息的这些点是否在一个区域范围内部的时候可以结合其高程信息、RGB信息、深度信息来辅助处理相比与单纯从数学角度来看更简单、快速。
举几个我认为正确的例子SLAM中前端角点的选取利用的是OpenCV来提取DEM提取边界根据周围高程的有无PS中扣出某物边界利用的是RGB差异性点云提取可以利用深度信息本质也是RGB来做。
但是如果我现在只拥有点的坐标该问题就变成一个数学问题了。
2.射线法 该算法基本思路是从待定点朝任意方向射出一条射线通常是水平向右判断该射线与多边形边的交点个数。一般来说交点个数为偶数包括0点在外部交点个数为奇数点在内部。 因为点和图形的位置是固定不动的所以射线的朝向对于最终的交点个数也就是位置结果是没有影响的。
2.1 算法介绍
在分析前要先明白几个问题
如果没有特殊需求待求点在图形的边界线段、交点上默认是属于图形内部的。默认待求点的射线沿着x轴方向水平射出水平向右。射线经过边界交点情况很常见为了防止上一个线段的末顶点和下一个线段的首顶点这两个是一个点被算作两次所以只看线段的y更小的一端即参数方程的值域符号[y1,y2)。 假如逆时针遍历各边看下图示例
1从简单情况开始分析 最简单的情况当属一个规整的四边形射线与四边形的交点个数存在的情况有012。 如果不考虑穿过顶点不考虑点的射线与边平行重合就单纯考虑穿的全部是边遇到这种情况 先建立遍历边的参数方程找到射线与参数方程的交点再判断交点X交和待定点的位置关系。 如果P在X交左侧有一个交点则计数1 如果P和X交是一个点则说明P在边界线段上直接返回true 如果在X交右侧没有交点。 注意这里的上下yi和yj的取值要包含下界不包含上界否则会被计算两次而且这样可以有效忽略水平边界而待求点在左侧的问题。 当然反过来也可以都选择更大的y值。 2我认为的几种特殊情况这几种特殊情况有特点就是无法找到线段去做参数方程或者实际交点无数个。这几种特殊情况需要单独处理。
待求点就是边界交点通过坐标判断直接返回是否在边界内。待求点在水平边界线上通过坐标判断直接返回是否在边界内。待求点在水平边界线左侧配合前后该水平边界先后线段参数方程的值域这种情况可以直接忽略忽略不是没有考虑
2.2 C#代码实现
using System;
using System.Collections.Generic;public class Point
{public double X { get; set; }public double Y { get; set; }public Point(double x, double y){X x;Y y;}
}
public class Polygon
{private ListPoint vertices;public Polygon(ListPoint points){vertices points;}public bool IsPointInside(Point testPoint){int intersectionCount 0;int vertexCount vertices.Count;for (int i 0, j vertexCount - 1; i vertexCount; j i){Point vi vertices[i];Point vj vertices[j];// 检查测试点是否在顶点上if ((vi.X testPoint.X vi.Y testPoint.Y) ||(vj.X testPoint.X vj.Y testPoint.Y)){return true;}// 检查测试点是否在水平边上if (vi.Y vj.Y vi.Y testPoint.Y){if (testPoint.X Math.Min(vi.X, vj.X) testPoint.X Math.Max(vi.X, vj.X)){return true;}}// 检查testpoint.y是否在两个端点的中间//if ((vi.Y testPoint.Y) ! (vj.Y testPoint.Y)) // 这行代码更简单但是有点小小的不直观if ((vi.Y testPoint.Y vj.Y testPoint.Y) || (vj.Y testPoint.Y vi.Y testPoint.Y)){double intersectionX (vj.X - vi.X) * (testPoint.Y - vi.Y) / (vj.Y - vi.Y) vi.X;// 处理边界情况if (testPoint.X intersectionX){return true;}if (testPoint.X intersectionX){intersectionCount;}}}// 如果交点数为奇数则点在多边形内部return intersectionCount % 2 ! 0;}
}
internal class Program
{static void Main(string[] args){ListPoint vertices new ListPoint{new Point(0,0),new Point(1,0),new Point(2,-1),new Point(3,0),new Point(5,0),new Point(5,1),new Point(4,1),new Point(4,2),new Point(3,3),new Point(3,4),new Point(2,4),new Point(2,3),new Point(1,3),new Point(1,4),new Point(0,4),new Point(0,2),new Point(-1,1),};Polygon polygon new Polygon(vertices);ListPoint testPoint new ListPoint();for (int i -1; i 6; i){for (int j -1; j 7; j){testPoint.Add(new Point(i, j));}}foreach (var p in testPoint){Console.WriteLine($p点坐标{p.X}, {p.Y},是否在图形内部{polygon.IsPointInside(p)});}Console.ReadKey();}
}用for循环写了一个从-1-1到56覆盖的测试点最后结果
p点坐标-1, -1,是否在图形内部False|p点坐标-1, 0,是否在图形内部False
p点坐标-1, 1,是否在图形内部True|p点坐标-1, 2,是否在图形内部False
p点坐标-1, 3,是否在图形内部False|p点坐标-1, 4,是否在图形内部False
p点坐标-1, 5,是否在图形内部False|p点坐标-1, 6,是否在图形内部False
p点坐标0, -1,是否在图形内部False|p点坐标0, 0,是否在图形内部True
p点坐标0, 1,是否在图形内部True|p点坐标0, 2,是否在图形内部True
p点坐标0, 3,是否在图形内部True|p点坐标0, 4,是否在图形内部True
p点坐标0, 5,是否在图形内部False|p点坐标0, 6,是否在图形内部False
p点坐标1, -1,是否在图形内部False|p点坐标1, 0,是否在图形内部True
p点坐标1, 1,是否在图形内部True|p点坐标1, 2,是否在图形内部True
p点坐标1, 3,是否在图形内部True|p点坐标1, 4,是否在图形内部True
p点坐标1, 5,是否在图形内部False|p点坐标1, 6,是否在图形内部False
p点坐标2, -1,是否在图形内部True|p点坐标2, 0,是否在图形内部True
p点坐标2, 1,是否在图形内部True|p点坐标2, 2,是否在图形内部True
p点坐标2, 3,是否在图形内部True|p点坐标2, 4,是否在图形内部True
p点坐标2, 5,是否在图形内部False|p点坐标2, 6,是否在图形内部False
p点坐标3, -1,是否在图形内部False|p点坐标3, 0,是否在图形内部True
p点坐标3, 1,是否在图形内部True|p点坐标3, 2,是否在图形内部True
p点坐标3, 3,是否在图形内部True|p点坐标3, 4,是否在图形内部True
p点坐标3, 5,是否在图形内部False|p点坐标3, 6,是否在图形内部False
p点坐标4, -1,是否在图形内部False|p点坐标4, 0,是否在图形内部True
p点坐标4, 1,是否在图形内部True|p点坐标4, 2,是否在图形内部True
p点坐标4, 3,是否在图形内部False|p点坐标4, 4,是否在图形内部False
p点坐标4, 5,是否在图形内部False|p点坐标4, 6,是否在图形内部False
p点坐标5, -1,是否在图形内部False|p点坐标5, 0,是否在图形内部True
p点坐标5, 1,是否在图形内部True|p点坐标5, 2,是否在图形内部False
p点坐标5, 3,是否在图形内部False|p点坐标5, 4,是否在图形内部False
p点坐标5, 5,是否在图形内部False|p点坐标5, 6,是否在图形内部False
