问题标签 [convex-polygon]

[这是我在本站的第一篇文章，我会尽量完整，如果我的问题陈述不清楚或代码格式不符合标准，请原谅我]

我正在尝试在迷宫环境中检测最大可能的矩形，因此我可以使用凸优化方法来维持迷宫中的视线连通性。这意味着任何其他凸形也可以，尽管我认为考虑到我正在使用的地图，矩形最容易实现（见下文）这也意味着矩形可以（并且应该）重叠，即在每个迷宫弯曲处应该至少是 2 个重叠的矩形。

我最初的想法是确定迷宫中的所有边缘，产生一个矩形网格，然后迭代检查哪些矩形可以组合形成凸形（如果有更好的方法找到这些矩形，我很想听听！）。

我到目前为止的代码如下所示：

虽然检测到一些边缘，但大多数仍然没有标记。将峰值阈值设置得较低并没有帮助。有谁知道为什么没有检测到剩余的边缘？我在下面添加了我的脚本生成的图。

边缘检测结果：

我面临以下问题：我在整数网格上给出了一组坐标，这些坐标定义了多边形的顶点。多边形保证是凸的。事实证明，这样的多边形总是可以被 2 条正交线切割成 4 个面积相等的部分。我们称这些线的交点为P。鉴于该集合，我应该计算P多边形内的坐标和线条需要打开的角度，以便线条将多边形切割成 4 个相等的部分。

我意识到，总的来说，蛋糕切割问题没有“好的”解决方案。但它的这种特殊情况应该。我已经搜索了一种算法来解决这个问题，但没有发现任何有用的东西。我应该去哪里看？

我的方法是计算多边形中心的坐标（可以或多或少容易地完成），放置P在那里，然后“摆动”线条，直到部件的区域匹配。但这听起来太不雅了。

UPD：这就是我正在处理的问题。也许这个问题应该暂停，直到我提出实际的代码问题。

我有两个由它们的光线表示的多面体锥体。我正在寻找他们的交叉点，这也将是一个多面体圆锥，希望能有效。有人知道这样做的方法吗？

谢谢

深盘树

我正在制作一个地形编辑器，我需要找到一组点的周边多边形。如果我只需要一个凸包，那么速度就没有问题了。要制作一个凹形船体，我必须经过几圈。我发现我可以对这些点进行三角测量，然后丢弃任何边长于点之间已知距离的三角形。

下一步是问题：使用 JSTS 几何库 ( http://github.com/bjornharrtell/jsts ) 将三角形（作为迷你多边形）组合成一个大多边形真的很慢。

查看完整代码：http ://codepen.io/anon/pen/oCfDh

我有一个数组（多边形），它被合并形成最终的多边形。问题是 552 点（我想支持 15k+），运行大约需要 3500 毫秒。查看 codepen 链接中的控制台以了解您的速度。

有没有人知道任何更快的方法可以将三角形合并成一个多边形，或者更宽，并以完全不同的方式从一组点构建一个凹多边形？

我试图找到一种算法，它将一系列边长作为输入，并用这些边形成一个凸多边形。我知道这种凸面并不总是存在，但我正在处理应该存在的数据。

基本上我试图找出边缘之间的角度。当我知道它们时，我也可以计算出角落的坐标。

R^3 中有两个多面体 A 和 B，有空交集。多面体由它的面定义，即它的超空间只有不等式，顶点是未知的。问题是找到 A 中的点 a 和 B 中的 b 使得 ||ab|| = d(A,B) -- A 和 B 之间的距离。我们也可以为 R^2 或 R^d 为 d>3 制定此问题。解决这个问题的方法是什么。这个问题有一些应用吗？

我需要用两条垂直线切割一个凸的非简单多边形，将其分成 4 个相等（面积）的部分。

我写了一个程序，但它没有通过测试。

• 我认为原因是舍入误差或我计算面积的函数。
• 请检查一下，是否正确？
• 我使用鞋带算法和苍鹭公式

这是代码：

我在做什么：

• 寻找point(x, y)切割多边形。
• 我把它剪了x = a in [ min(x), max(x)]
• 并计算S'（从 x=min(x) 到 x=a 的多边形的一部分）
• 如果S' = S/2，我拿来a计算价值(a, *)
• 然后与y = bwhere相同b in [min(y), max(y)]
• 有没有更快的方法？

我有这样的形状：

并且点的坐标可用（顶点具有 x 和 y 分量）

我的质地是：

一个简单的平面 UV 映射给了我：

我想要的是：

如何计算顶点位置以获得所需的映射？请注意，这是一道数学题。

另外，我可以忍受拉伸，只要顶点落在草地上。

我想找到手掌的中心。首先，我找到轮廓并选择最大面积轮廓。我使用了pointPolygonTest。我的代码和结果图像如下，但我没有找到任何使用 pointPolygonTest 的点。问题是什么？

我正在使用 Three.js 和 Physijs。我有一堵墙应该作为边界，但如果力量足够的话，物体（尤其是盒子）经常会穿过它。检测到碰撞，因为它们没有干净地这样做，但它们开始在某个方向旋转或反弹。有没有办法增加墙可以作用在碰撞物体上的最大力？

墙的所有四个点都在同一平面上，形成一个矩形。网格由两个大三角形面组成。我正在使用凸网格。

将两个三角形分成许多较小的三角形并不能缓解问题。

我可以确认法线没有问题，因为墙壁的阴影正确。

如何在不将墙转换为 BoxMesh 的情况下解决此问题？

我也会感谢解释为什么会发生这种情况。我猜引擎限制了碰撞可以施加的最大力。