最近遇到一个需求，给定一个多边形（边与边可能相交），求这个多边形的轮廓线。 需要注意的是，轮廓线多边形内不能有空洞，使用的不是常见的非零绕数规则（nonzero）以及奇偶规则（odd-even）。...: 10 }, ]; 然后我们做去重，如果连续的多个点的位置 "相同"，其实就等价于一个，保留一个就好。...const right = (i + 1) % size; adjList.push([left, right]); } return adjList; } 需要求解的轮廓线多边形的点不一定是目标多边形上的点...（1）取左下角点作为起点 找顶点（不包括交点）中最靠下的点，如果有多个，取最靠左的。这个点一定是轮廓多边形的一个点。...，超过最大循环次数 ${MAX_LOOP}`); } // outlineIndices 为我们需要的轮廓线多边形 这里有个求两向量夹角的方法要实现，这里不具体展开了。
如果两个相同类型的几何图形具有相同的x、y坐标值，即如果第二个图形与第一个图形的坐标信息相等（相同），则ST_Equals()返回TRUE。...B)，如果两个几何图形没有重合的部分，则它们不相交，反之亦然。...ST_Touches() 测试两个几何图形是否在它们的边界上接触，但在它们的内部不相交 如果两个几何图形的边界相交，或者只有一个几何图形的内部与另一个几何图形的边界相交，则**ST_Touches(geometry...与直觉相反，执行空间索引搜索并不总是更快：如果搜索将返回表中的每条记录，则遍历索引树以获取每条记录实际上比从一开始线性读取整个表要慢（注意这句话）。...如果多点中有两个或两个以上的点重合（也就是坐标一致），那么它就不是简单的，但是确是有效的 7.2 线串的简单性与有效性 7.2.1 单线串 单线串（LINESTRING）如果有重叠、相交就不是简单的（除了端点相交
内含：Within几何形状A的线都在几何形状B内部。B⊃A相交：Crosses几何形状至少有一个共有点 A∩B≠∅ ， 检查两个几何对象是否交叉相交。只能在不同维度使用：如点和线，线和面等。...不能在线与线之间，和点与点之间，也不能在面与面之间使用。脱节：Disjoint几何形状没有共有的点 A∩B=∅， 检查两个几何对象是否相交。...如果返回值为真，则它们应该包含（Contains）另外一个图形同时也被另外一个图形所包含(Within)。...检查两个几何对象是否相连判断两个图形的边界是否相交，如果两个图形的交集不为空，但两个图形内部的交集为空，则返回值为真。...crosses 穿过（相交)这里的拓扑关系比较特殊，使用crosses，不能在同纬度使用，但可以在不同的维度使用，如：点和线，线和面等。不能在线与线之间，和点与点之间，也不能在面与面之间使用。
MySQL提供单个的存储类型 POINT、LINESTRING、POLYGON 对应几何图形点、线、多边形，GEOMETRY 可以存储三种中的任何一种。...如果不是闭合的polygon返回的结果将是NULL，插入语句就会执行失败。...如果几何满足诸如此(非穷举)列表中的条件，则它在语法上是 well-formed： 线串至少有两个点 多边形至少有一个环 多边形环关闭(第一个和最后一个点相同) 多边形环至少有 4 个点(最小多边形是一个三角形...如果任一参数是NULL或空几何，则 return value 为NULL。 2、图形1是否完全包含图形2 ST_Contains(g1，g2)，返回 1 或 0 以指示g1是否完全包含g2。...3、不相交 ST_Disjoint(g1，g2)，返回 1 或 0 以指示g1是否在空间上与(不相交)g2不相交。
最近做了一个算法题【盒马配货】： （题目大意）盒马店的配送范围由一些点组成的多边形确定，给定一个点判断其是否在配送范围内，若在，则此点不需要挪动，打印"no 0"；若不在，则给出此点需要挪动到配送范围的最短距离...这个表达式的意思是说，随便画个多边形，随便定一个点，然后通过这个点水平划一条线，先数数看这条横线和多边形的边相交几次（可先排除那些不相交的边，即第一个判断条件），然后再数这条横线穿越多边形的次数是否为奇数...，如果是奇数，那么该点在多边形内，如果是偶数，则在多边形外（射线法）。...点在直线下 - 相交判断 如下图，ab与过p点的水平线相交于c， ? 则有： ? Java代码实现： if (((ys[j] > y) !...contained;} 点在多边形内部 - 射线法 判断点是否在多边形内，可以从这个点做一条射线，计算它跟多边形边界的交点个数，如果交点个数为奇数，那么点在多边形内部，否则点在多边形外。
判断两线段是否相交： 我们分两步确定两条线段是否相交： (1)快速排斥试验 设以线段 P1P2 为对角线的矩形为R， 设以线段 Q1Q2 为对角线的矩形为T，如果R和T不相交，显然两线段不会相交...(2)跨立试验 如果两线段相交，则两线段必然相互跨立对方。...计算点到线段的最近点： 如果该线段平行于X轴（Y轴），则过点point作该线段所在直线的垂线，垂足很容易求得，然后计算出垂足，如果垂足在线段上则返回垂足，否则返回离垂足近的端点；如果该线段不平行于X...；如果不在则计算两端点到垂足的距离，选择距离垂足较近的端点返回。 ...另外，一开始就先利用矢量叉乘判断线段与线段（或直线）是否相交，如果结果是相交，那么在后面就可以将线段全部看作直线来考虑。
2 类与方法 在上一篇博客中说道了几何数据类型（点、线、面和集合）的定义，既然几何数据类型是通过CLR来扩展出来的，学习过C#的都知道，一个对象下面会有属性和方法，那么几何数据类型对应的也有其属性和方法...，点是0维，线是1维，面是2维，如果是集合就要看几何中最大的纬度了。...如：SELECT @g.STSrid STIsEmpty确定实例是否为空，如果为空则返回1，否则返回0。注意这里的空并不是NULL的意思哈。...STArea 返回实例的面积，这个就不用多说了吧，如果中间带孔是要扣除孔的面积的。返回float类型。 PolyGon类的方法： STExteriorRing 返回多边形实例的外环。...GemoColllection类的方法： STNumGeometries 返回几何图形集合实例中的几何图形数目，如果是Point等非集合的实例，则返回1，空实例返回0.使用如：SELECT @g.STNumGeometries
然后我们可以先使用判别式求出式子解的数量，0根代表视线不经过球，1根代表视线擦过球，2根代表视线与球相交 最后用求根公式可以得到t的值，如果求出的t是两个正数，在视野内，t一正一负，视点在球内，t两负，...视线与多边形的相交判断是个更加复杂的问题，因为多边形可能是凸多边形或凹多边形，平面交点可能刚好穿过多边形的空洞。...关键思路是计算射线在多边形平面的交点与投影到二维平面的多边形可以形成的交点数量 首先求解下面的式子，其中p=e+td，通过求解t得出射线与多边形所在平面相交的交点，这一步可以筛选掉多边形与射线平行的情况...然后我们将多边形和交点投影到某个轴面上，例如xoy面，在二维上让交点向着某个轴向例如x轴方向形成直线，接着计算与多边形产生的交点数量，如果交点数量是偶数个则代表交点在多边形外，如果交点数量是奇数则表示交点在多边形内...视线与一组物体相交 场景中一般不会只有一个物体，对于复杂的场景通常的射线相交判断方法是先将需要判断是否相交的物体归为一组 然后计算出这组物体中所有相交的交点 返回交点t在范围内且最小物体，也就是最接近投影面物体
上图中，和黄色星星相交的线的数量是 1，即红色那条线。但是与黄色框相交的范围框有红色和蓝色，共 2 个。...数据库求解 “什么线与黄色星相交” 这个问题，是先用空间索引求解 “什么范围框与黄色范围框相交” 这个问题的（速度非常快），然后才是 “什么线与黄色的星星相交”。...，将其替换为点将强制它位于一侧或另一侧，而不是与两侧的多边形都相交 ST_Centroid(geometry) —— 返回大约位于输入几何图形的质心上的点。...这种简单的计算速度非常快，但有时并不可取，因为返回点不一定在要素本身上。如果输入的几何图形具有凹性（形如字母’C’的几何图形），则返回的质心可能不在图形的内部。...关于它们的交集的DE9IM矩阵如下： 请注意，以上两个要素的边界实际上根本不相交（线的端点与多边形的内部相交，而不是与多边形的边界相交，反之亦然），因此B/B单元用"F"填充。
交点数如果是奇数，说明点在多边形内；如果是偶数，则点不在多边形内。 背后的原因是，交点刚好把这条射线切割为 “...内-外-内-外” 这样交替的子区域。...然后就是遍历多边形的所有边，判断边线段和射线是否有交点，有交点就给相交数 count 加 1。...这是因为我们要处理一些特殊情况，就是 射线刚好穿过多边形的顶点的情况。 如果等于也算的话，会导致穿过一个点变成了穿过两个点的效果，最后结果错误。...如果叉积为 0，说明是特殊情况：点在边上。此时不用继续遍历，直接返回 true（或 false）。 如果叉积是正数，说明目标点在边的左侧，交点数 count 加 1。...} } } return count % 2 === 1; }; 其它 对于该算法，有一些可以调整的点： 可以将交点数变量 count 换成一个默认为 false 的布尔值变量
a)有效，其中一个内环在一个点上与外环接触； b)无效，因为它的内环在多个点上与外环接触； c)无效，因为它的外环和内环沿一条线接触； d)无效，因为它的内环沿着一条线接触 1、Polygon的面积和长度不为...如果normalized参数为True，则返回对象长度的标准化距离，project()方法是interpolate()的逆方法。...（在点集术语中）与空集重合，则返回True >>>> Point().is_empty True >>> Point(0, 0).is_empty False 注意：在操作符模块的attrgetter...LineString，则返回True。...False object.is_valid 如果要素是“有效的”，则返回True 一个有效的LinearRing 不能在一个点上与自己交叉或相接。
CGAL：线段和多边形之间的交点？ [英] CGAL: Intersection between a segment and a polygon?...问题描述 我有一组多边形，我想测试它与线段之间的交点。 我检查了手册，但找不到匹配的功能。 点，线，线段，三角形，平面之间的交点确实存在。 多边形之间的交点也在那里。...如果没有，这是否意味着我需要将多边形分解为多个部分，并在这些部分之间进行相交？ （我不愿意这样做的原因是，我认为CGAL实际上可能会使用这种方式在多边形之间进行相交。...为什么没有这样的函数将线与多边形相交？）或者还有其他更好的方法吗？ 推荐答案 最简单的方法是创建一个Polygon_set_2对象，该对象可能包含几个多边形。...要使用此集测试外部多边形的交集，您只需应用do_intersect方法。
主流算法： （1）面积和判别法：判断目标点与多边形的每条边组成的三角形面积和是否等于该多边形，相等则在多边形内部。...如果有奇数个交点，则说明在内部，如果有偶数个交点，则说明在外部。 具体做法：将测试点的Y坐标与多边形的每一个点进行比较，会得到一个测试点所在的行与多边形边的交点的列表。...在下图的这个例子中有8条边与测试点所在的行相交，而有6条边没有相交。如果测试点的两边点的个数都是奇数个则该测试点在多边形内，否则在多边形外。...Layer4G 是点图层 Buildings 是面图层 该查询的意思是获取“点位于多边形中的元素”，点击确定，查询完毕后返回一张表格； 4、表->导出，选择刚才的查询结果 query，保存类型选择...另外的算法： 1、将点设置为红色； 2、将多边形设置为黑色； 3、查询点的颜色，黑色则说明位于多边形内，红色则说明位于多边形外。
图8 并且如果原始数据中存在互相存在重叠的矢量对象，通过unary_union之后，返回的shapely对象会自动对存在重叠的矢量对象进行融合，这一点可以方便我们的很多日常操作： ?...图16 在how='union'下，叠加分析的结果会包含所有存在相交的部分，以及df1与df2各自剩下的不相交的部分，如图中蓝色部分即为df1与df2相交从而不存在缺失值的部分，而剩余的灰色部分因为没有相交...图19 这时返回的结果中不再有value2字段，结合图13可以知晓在how='difference'下的返回结果与Arcgis中的擦除功能一样，返回的是df1中不与df2相交的部分，且以Multi的形式保留被切割开来的碎片矢量...图24 从图24中可以看出，在how='identity'条件下，所有df1中不与df2相交的部分，以及两者相交的部分作为返回结果，且每个相交的部分都变为单独的要素带上所有涉及的属性字段，而df1中不涉及相交的部分则仍然以...keep_geom_type 有些时候我们需要做的不仅仅是面与面之间的叠加分析。比如在计算路网相关的指标时，我们可能会需要与目标区域存在叠置关系的部分路网，这就存在面与线之间的叠加分析。
射线法的原理是以待判断的点坐标画一条水平的直线，然后判断这条直接与多边形各条边的交点数量，如果是奇数则代表点在多边形内，如果是偶数则代表点在多边形之外。...以一个简单图形举例： 上图中的六边形是由四个三角形组成，前端从服务端拿到的数据一般只包括六边形的6个顶点坐标，即v1 - v6，而且这6个坐标点是按照顺时针排列（如果有hole，则hole的顶点是逆时针排列...所以WebGL中的任何图形本质上都是多边形，既然是多边形就可以按照上文的方案解决点与多边形的相对位置判断问题。 如何判断两条线段有交点？...回顾上文提到的多边形顶点数据制备，多边形的边是由相邻两个顶点相连而成，顶点是有序的，也就是说多边形的每条边都是有向线段，所以判断两条线段是否相交这个问题准确的说发应该是：判断两个有模向量是否相交。...判断两条线段是否相交用到了上述的规则2-4。先看下面这张图： 如果线段AB和CD相交可以推导出以下规则： 点A和点B分别位于线段CD的两侧； 点C和点D分别位于线段AB的两侧。
首先，创建一个与其他几何形状相交的几何形状，然后使用.intersection()方法获取相交的几何形状。...：', intersection); 注意，当几何形状没有相交的部分时，intersection()方法将返回一个空的几何形状。...返回几何体最高维度分量的中心点。低维组件将被忽略，因此包含两个多边形、三条线和一个点的几何体的中心点等同于仅包含两个多边形的几何体的中心点。...返回给定几何体的凸壳。单个点的凸面形是点本身，相邻点的凸面形是一条直线，其他所有点的凸面形是一个多边形。需要注意的是，如果一个退化多边形的所有顶点都在同一条直线上，那么该多边形将生成一条线段。 ...，根据多边形来选取出相交点的坐标。
由面要素裁剪线要素： 由面要素裁剪点要素： 由线要素裁剪线要素： 由点要素裁剪点要素： 相交 计算输入要素的几何交集。然后输出相交的要素 输入要素必须是简单要素：点、多点、线或面。...如果输入具有不同几何类型（即，面上的线、线上的点等），则输出要素类几何类型默认与具有最低维度几何的输入要素相同。...例如，如果一个或多个输入的类型为点，则默认输出为点；如果一个或多个输入为线，则默认输出为线；如果所有输入都为面，则默认输出为面。 输出类型可以是具有最低维度几何或较低维度几何的输入要素类型。...例如，如果所有输入都是面，则输出可以是面、线或点。如果某个输入类型为线但不包含点，则输出可以是线或点。如果任意一个输入是点，则输出类型只能是点。...擦除 通过将输入要素与擦除要素的多边形相叠加来创建要素类。只将输入要素处于擦除要素外部边界之外的部分复制到输出要素类。 联合 计算输入要素的几何并集。将所有要素及其属性都写入输出要素类。
绘制多边形区域面 面数据通常以离散点串形式存储，面的绘制与线的绘制原理类似。渲染的基本单位是三角形，线是通过扩展线宽构造三角形后渲染，而面是通过将多边形拆分为多个三角形后渲染。...通过全链路的排查，才查出是多边形数据的问题。 三角剖分在使用时有一个前置条件：使用对象必须为简单多边形，即多边形中的任何两条边仅可以在顶点处相交。...下图(a)多边形为满足定义的简单多边形，图(b)多边形边01和23在非顶点处相交，因此是非简单多边形。...简单多边形的判定与修复 根据简单多边形的定义，很容易想到采用暴力解法进行判定：一个 [6bfde5c5d3504a829642a724fe8e07a8~tplv-k3u1fbpfcp-watermark.image...但在当前的建筑拔起渲染方式下，只能通过贴图的形式去表达建筑细节，如果需要更精细的表达效果，例如玻璃窗体结构、楼顶设施等，需要增加额外的三角形去进行呈现。
矢量类型不同时（譬如面与线数据之间进行叠加分析），用于决定在叠加分析产生结果中，是否只保留与df1矢量类型相同的记录，默认为True 首先我们构造示例矢量数据，以方便演示overlay()不同参数下结果的区别...，以及df1与df2各自剩下的不相交的部分，如图中蓝色部分即为df1与df2相交从而不存在缺失值的部分，而剩余的灰色部分因为没有相交，无法获得来自另一个GeoDataFrame的属性值，所以返回出来的结果会在对应的字段下填充为缺失值...value2字段，结合图13可以知晓在how='difference'下的返回结果与Arcgis中的擦除功能一样，返回的是df1中不与df2相交的部分，且以Multi的形式保留被切割开来的碎片矢量： ax...，以及两者相交的部分作为返回结果，且每个相交的部分都变为单独的要素带上所有涉及的属性字段，而df1中不涉及相交的部分则仍然以Multi的形式被返回。...keep_geom_type 有些时候我们需要做的不仅仅是面与面之间的叠加分析。 比如在计算路网相关的指标时，我们可能会需要与目标区域存在叠置关系的部分路网，这就存在面与线之间的叠加分析。
透视投射 透视投影可以产生近大远小的效果，就和人类观察世界的方式类似 在真实的3D世界中，平行线段会在远处收敛与一点 为什么复杂图形的绘制要使用三角形 在3D图形学中，我们叫三角形“多边形” 一堆多边形的集合叫做...扫描线算法会填满两个相交点之间的像素 因为是三角形，如果相交一条边，必然相交另外一条边 抗锯齿 这样的三角形比较丑，因为边缘满是锯齿 一种减轻锯齿的方法叫做抗锯齿 抗锯齿：与其每一个像素都涂成一样的像素...如果像素在多边形内部直接填充颜色；如果多边形划过像素，那么颜色就会浅一些 遮挡的渲染算法 在3D场景中有很多的多边形，但是只有一部分能看见，因为其他的被遮挡住了。...这次要考虑的是多边形面对的方向，他们不平行与屏幕，而是面对不同方向。...面对的方向叫做“表面法线“ 用一个垂直与表面的小箭头来显示这个方向 加一个光源，因为不同多边形面对光源的角度不同，因此会导致箭头的方向和光源照亮的方向重叠越多，代表这个多边形越亮 纹理Textures
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
ICP备案
对象存储
腾讯会议
云直播
