问题标签 [convex-polygon]

I have multiple convex polygons that intersect. I want to find the areas, where many of them intersect. In an image, one could think of it as a "peak". I am searching for the local peaks.

I have the software to intersect two polygons. Now I am thinking about how to compute the peaks, without computing all possible intersections (exponential time!).

Does somebody have a hint?

我的图表中有一组线条，我也有一点。我想要的是一组线，它们将通过有序的遍历一起形成一个多边形。我不需要实现或任何我想要的只是有人指导我使用我可以使用的算法。有人问过类似的问题，但对我不起作用，因为

一个常见的问题是，给定一个多边形，我需要找出点是否在其中，但这对我不起作用，因为我没有任何多边形，我只有一组线。

最终的多边形也可以是凸的，所以简单地从该点在每一侧绘制光线并找到交叉点是行不通的，我需要更高级的东西。

抱歉所有的混乱：为了清楚起见，请参阅此https://ibb.co/nzbxGF

任何人都可以建议一种算法来找到帕累托最优点（形成一个楼梯），就像图中给出的O(n*h)时间O(n*log(h))复杂度一样，h帕累托最优点的数量在哪里？

我使用礼品包装算法来解决这个问题（在 中O(n*h)），但它只找到凸包类型的楼梯，而错过了那些形成凹角的点。

所以我将 KML 文件加载到我的谷歌地图，它们在地图上显示为凸多边形。
我也有用户位置，基本上我想知道用户是否位于多边形的边缘之一（这是一个凸多边形）。
并且由于位置服务不是 100% 准确，如果位置很近（边缘距离为 15m），那很好:)

我的解决方案是找到在 2 个顶点之间传递的函数 y=f(x)，然后检查用户位置是否低于 f(x)+a 和高于 f(x)-a。

我觉得我错过了一些东西，应该有更好（更准确）的方法来解决我的问题，甚至可能有一个已经解决这个问题的 android 的 java 库。

谢谢 ：）

给定一个凸多面体，我需要找到一个更快的算法来计算其中的最大体积四面体。我只能想到O（n ^ 4）的蛮力解决方案。我在想，如果我们可以使用一些预处理在不到 O(n) 时间内从使用 3 个多面体顶点形成的三角形中找到凸多面体中最远的顶点。这个四面体的体积将在这个三角形底下最大（四面体的体积是 1/3*底面积*高），对所有三角形执行此操作将使我在小于 O(n^4) 的时间内获得最大体积四面体。

我一直在做一个需要对球体进行三角测量的项目。我知道剪耳算法并且知道如何将它应用到非闭合多边形中，比如平面。

但是如何对一个封闭的多边形进行三角剖分，比如一个球体？

我正在开发 Scale 游戏： Scale

为此，我需要按顺时针方向对点进行排序，并为此过程实现了算法。这是算法参考链接：按顺时针顺序排序点？

但是现在这种情况发生在我身上。我做了适当的草图来代表我的侧面错误情况。

上图我希望能准确地解释我的问题。基本上使用算法，点得到正确排序，但根据游戏要求，我想对这些进行一些调整。

那么在这种情况下该怎么办呢？请给我一些建议。

我正在研究图像分割，我认为凸包可以为我的问题提供一个简单的解决方案。目前我有边的多边形（见下图）。由于图像处理问题，形状没有干净的直边，因此当我使用标准凸包（在 Matlab 中）时，我可能会得到超过四个主要角来定义它。

我的目标是强制凸包算法找到将包围我的多边形的最佳 4 个顶点（即每个多边形 4 个最佳封闭顶点）。这可能吗？示例代码将不胜感激。

谢谢

我得到了一个严格的S边凸多边形和Q查询来处理。

多边形的所有点和查询点都以 (x,y) 对形式给出。多边形的点按逆时针顺序给出。

上述变量受限于1<=S<=10^6和1<=Q<=10^5和1<=|x|,|y|<=10^9。

对于每个查询，如果给定点位于多边形内，我应该输出 Yes；否则，不。

我尝试使用 O(S)包含测试（光线投射），但它对于更大的测试用例超时，但也没有通过所有初步测试。

显然，实现并没有涵盖所有边缘情况，我了解了这个问题的特定算法，它可以使用二进制搜索回答O(log S)中的每个查询，但我不知道如何从伪代码（第一次做计算几何）。

任何人都可以为我提供涵盖所需时间复杂度（Q log S）内所有边缘情况的算法，或者指导我找到实现它的页面或论文吗？

打开图像以查看以下代码的结果

我想获得凸包上点的坐标索引（黑色+线上的点）。我选择矩形只是为了得到一个极端的情况。

hull.points只能给出标记为红色的点（仅矩形的角点）。

代码结果