如何用凸形状形成凹形状？
我试图绕过只能在 SFML C++ 库中形成凸形状的规则。
为此，我计划测试给定的顶点，如果是凹的， 将顶点分成组，测试每个组的凹性， 并重复直到得到看起来像的全套凹形形状 组合起来就像原来的形状
我想知道的是...
测试形状凹度的方程式是什么：它是什么以及它如何工作？
我将如何分割凹形状的顶点，以便最终形成形状由尽可能少的凸形状组成可能吗？
实现我的目标的最佳实践是什么？
谢谢！
i'm trying to get around the rule of only being able to form convex shapes in the SFML c++ library.
To do this I'm planning on testing given vertices, and if concave,
splitting the vertices into groups, testing each groups' concaveness,
and repeating until a full set of concave shapes results that look
just like the original shape when put together
What I would like to know is...
What the equation for testing a shapes concaveness is: What is it and how does it work?
How would i split up the vertices of the concave shape so in the end the shape is formed out of as few convex shapes as possible?
Whats the best practice for achieving my goal?
Thanks!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
Boost Geometry 库 昨天发布，有一个实现<代码>凸包算法。一张图片表达了一千多个单词：
尽管这构建了一个“新的” ' 非凹形（即凸形）的形状；这可能是也可能不是您想要的。然而，在此过程中，算法必然能够对凹/凸形状进行分类，因此您可能仍然对该库感兴趣。
有关凸包算法的一般信息：
由于 Adrian Japon 或多或少地建议“命中测试”（遏制测试）是关心凸/凹几何形状的常见原因，而无需话不多说，我将重点介绍相应的 Boost Geometry 算法：
内。The Boost Geometry library that was published yesterday, has an implementation of
Convex Hull algorithm. A picture says more than a thousand words:Although this constructs a 'new' shape that is non-concave (i.e. convex); This may or may not be precisely what you want. However, in the process the algorithm is bound to be able to classify shape a concave/convex, so you'd likely be interested in the library nonetheless.
General information on convex hull algorithm:
Since Adrian Japon more or less suggested that 'hit testing' (containment test) is of a usual reason to care about convex/concave geometries, without further ado, I'll highlight the corresponding Boost Geometry algorithm for that:
within.好吧，只是将所有信息混合在一起：
泰勒
最后，使用 此幻灯片：
添加对角线 uv2、uv3、...、uvi。
从堆栈中弹出 vi、vi-1、...、v1。
将 vi、u 压入堆栈。
情况(ii)：u 与vi 相邻，但不与v1 相邻。
当我> 1 且角 uvivi-1 <
添加对角线 uvi-1
从堆栈中弹出 vi
最后
推你
情况(iii)：u 与v1 和vi 都相邻。
添加对角线 uv2、uv3、...、uvi-1。
退出
转到步骤 3。
希望这对某人有帮助...但我仍在寻找更好/更快的解决方案。
Alright, just to mash all the info together:
Taylor
Finally, triangulate the now Monotone shapes using the information in this Powerpoint:
add diagonals uv2, uv3, …, uvi.
pop vi, vi-1, …, v1 from stack.
push vi, u on stack.
Case (ii): u is adjacent to vi but not v1.
while i > 1 and angle uvivi-1 <
add diagonal uvi-1
pop vi from stack
endwhile
push u
Case (iii): u adjacent to both v1 and vi.
add diagonals uv2, uv3, …, uvi-1.
exit
Go to step 3.
Hope this helps someone... but I'm still looking for any better/faster solutions.
需要考虑的一些事情：
左手角和右手角（叉积的符号是区分的简单方法）。凸形中的所有角都是相同的旋向性。
扩展边并添加新顶点可能会比在现有顶点之间添加边获得更好的结果。
Some things to think about:
Left-handed and right-handed corners (the sign of the cross-product is an easy way to distinguish). All corners in a convex shape are the same handed-ness.
Extending an edge and adding a new vertex may give you better results than adding edges between existing vertices.
我假设您将多边形作为点列表，一种非常简单的方法是围绕多边形并考虑连续点（A，B，C）的三元组序列。
然后，您只需检查 det(AB,BC) 在某一点是否更改其符号，其中
det(AB,AC) = (x_a-x_b)(yc-yb) - (x_c-x_b)(y_a-y_b)
I assume you have your polygon as a list of point, a very simple way would be to go around your polygon and consider the sequence of triplet of consecutive points (A,B,C).
Then you just check that at one point det(AB,BC) changes its sign, where
det(AB,AC) = (x_a-x_b)(yc-yb) - (x_c-x_b)(y_a-y_b)
您可以通过绕过所有边缘并检查下一条边缘始终沿相同方向移动（左/右手）来测试形状是否为凸包。这是一种快速且廉价的算法。这里有一个实现：en.wikipedia.org/wiki/Graham_scan
如果你不这样做如果没有凸包，请执行包包装算法以获得包含所有点的凸包（同样非常快）。 en.wikipedia.org/wiki/Gift_wrapping_algorithm
现在，寻找形状上的点，但是不在凸包上。对于这些点的每次运行，从这些点（加上凸包两侧的 2 个点）创建一个新形状。
递归现在是你的朋友：对你刚刚制作的每个子形状执行完全相同的过程。
我已经使用这种技术来测试任意形状内包含的点：即该点必须位于凸包内部（易于测试），但不是任何子形状或它们的子形状或它们的子形状-形状....
You can test for a shape being a convex hull by going round all the edges and checking the next edge is always moving in the same direction (left/right handed). This is a quick and cheap algorithm. There is an implementation of this here: en.wikipedia.org/wiki/Graham_scan
If you don't have a convex hull, perform a package wrapping algorithm to get a convex hull that encompasses all your points (again quite fast). en.wikipedia.org/wiki/Gift_wrapping_algorithm
Now, look for points that are on your shape, but aren't on the convex hull. For each run of these points, create a new shape from these points (plus the 2 either side on the convex hull).
Recursion is now your friend: do the exact same process on each of the sub-shapes you have just made.
I have used this techniques to test for a point being contained inside an arbitrary shape: i.e. the point must be inside the convex hull (easy to test), but not any of the sub-shapes, or their sub-shapes, or their sub-shapes....