问题标签 [concave]

我正在尝试使用 c# 和 directx 绘制多边形

我得到的只是文件中点的有序列表，我需要在 3d 世界中绘制平面多边形。

我可以使用三角扇和drawuserprimitives加载点并绘制凸形。

当多边形非常凹（可能是）时，这显然会导致错误的结果。

我无法想象我是唯一一个解决这个问题的人（虽然我是 gfx/directx 新手——我的背景是 gui\windows 应用程序开发）。

任何人都可以指出一个简单的资源\教程\算法可以帮助我吗？

对于使用 OpenGL 绘制复杂的凹多边形，最好将其细分为三角形，还是使用模板缓冲区？我猜模板缓冲区对于单帧会更快，但如果多边形不改变，三角剖分对于多帧会更好。但是，我还没有真正尝试过，所以我不知道。

我有一个 3D 顶点列表，创建一个多边形。我需要对其进行三角测量，并使用切割耳朵算法。我的多边形是非凸的，所以我需要找到多边形中的凹角。我也不知道我的多边形是哪个方向（顺时针或逆时针）

谁能帮我确定是顺时针还是逆时针

谢谢

我正在使用 Delaunay 对凹多边形进行三角剖分，但它填充了凹面。如何自动删除多边形边界之外的三角形？

我有一组顶点（称为 A），我想找到所有的边界顶点，使得这个边界顶点集是形状的轮廓。

A 中的许多顶点都是多余的，因为它们在形状内部，我想摆脱这些顶点。

我的问题类似于查找顶点边缘（多边形）的最佳算法，但我需要它来处理非凸多边形情况。

编辑：澄清：下图是一个凹多边形。这就是我所说的非凸的。如果我在其上运行凸包算法，它不会保留多边形的凹面部分。（除非我弄错了）。

我在多边形的边界内和边界上有一组顶点： [[x1,y1], [x2,y2]...] 我想减少集合，使顶点只是形状的边框轮廓。

我在一个 PathFigure 上有一个由 LineSegments 组成的 PathGeometry（多边形），我想确保它是凸的。我有一个方法使用 CrossProduct 来确定几何是否是凸的，我假设我可以返回一个点列表，当它为假时，我可以返回一个使其凹入的点列表，然后删除这些点来填充多边形，但它工作不正确。

这是我得到的代码：

这是我检查和纠正多边形的地方：

最终，我希望能够将我的凹面几何体变成这样的凸面体：

我最近几天搜索并研究了互联网，以找到适合我的问题的方法。

问题：

在没有方向的无限线上剪辑一个凹多边形（实际上是一个多边形在 3d 平面上，但我认为问题是相似的）。目前我使用 Sutherland-Hodgman，但生成的多边形有时包含从退化边缘创建的零面积部分，它也不支持包含孔的多边形。

我发现可以解决我的问题的最佳算法是 Weiler-Atherton 算法，但它用于裁剪具有顺时针边缘的多边形，而我所拥有的只是一条无限线（在 3d 平面中）缺少方向信息。

问题：

是否有一种算法可以裁剪一个适合我需要的凹多边形，或者有人对如何修改 Weiler-Atherton 算法以适用于这种情况有任何建议吗？有些网页表明它可以推广以支持更多案例，但我无法弄清楚。

//问候艾肯

我试图绕过只能在 SFML c++ 库中形成凸形的规则。

为此，我计划测试给定的顶点，如果是凹的，则将顶点分成组，测试每个组的凹度，并重复直到一组完整的凹形结果看起来就像放在一起时的原始形状

我想知道的是...

• 测试形状凹度的方程式是：它是什么以及它是如何工作的？

• 我将如何分割凹形的顶点，以便最终由尽可能少的凸形形成形状？

• 实现我的目标的最佳实践是什么？

谢谢！

Hey so i was told in a previous answer that to make concave shapes out of multiple convex ones i do the following:

If you don't have a convex hull, perform a package wrapping algorithm to get a convex border that encompasses all your points (again quite fast). en.wikipedia.org/wiki/Gift_wrapping_algorithm

Choose a point that is on the boarder as a starter point for the algorithm.

---

Now, itterate through the following points that are on your shape, but aren't on the convex border. When one is found, create a new shape with the vertices from the starter point to the found non-border point. Finally set the starter point to be the the found off-border point

Recursion is now your friend: do the exact same process on each new sub-shape you make.

---

I'm confused on one thing though. What do you do when two vertices in a row are off-border? After reaching the first one you connect the starter point to it, but then you immediatly run into another off-border point after you start itterating again, leaving you with only 2 vertices to work with: the starter point and new off-border point. What am i missing?

To illustrate my problem, here's a shape pertaining to this issue: It would be great if someone could draw all over it and walk through the steps of the algorithm using this. And using point 1 as the starting point.

Thanks!

我已经在互联网上搜索了好几天，但是对于似乎应该是一个常见问题的问题，我一直无法找到一个好的答案（或者至少是一个对我有意义的答案）。如何缩放任意多边形？特别是凹多边形。我需要一种可以处理凹面（肯定）和自相交（如果可能）多边形的算法。我用来处理简单凸多边形的明显而简单的算法是计算多边形的质心，将该质心平移到原点，缩放所有顶点，并将多边形平移回其原始位置。

这种方法不适用于许多（或所有）凹多边形，因为质心通常落在多边形之外，因此缩放操作也会导致平移，我需要能够在没有最终结果的情况下“就地”缩放多边形正在翻译。

有人知道缩放凹多边形的方法吗？或者也许是一种找到“视觉中心”的方法，可以用作缩放操作的参考框架？

澄清一下，我在 2D 空间中工作，我想使用“视觉中心”作为参考框架来缩放我的多边形。所以也许另一种问这个问题的方法是，我如何找到凹面和/或自相交多边形的视觉中心？

谢谢！