如何用Convex形状形成凹形？ [英] How to form a Concave shape out of Convex shapes?

问题描述

我想绕过只能在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 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?

实现我的目标的最佳实践是什么？ / strong>

Whats the best practice for achieving my goal?

感谢！

推荐答案

您可以通过绕所有边缘测试一个形状为凸包，并检查下一个边总是以相同的方向移动（左/右手）。这是一个快速和便宜的算法。这里有一个实现： en.wikipedia.org/wiki/Graham_scan

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

如果你没有凸包，执行包装包装算法，得到包含所有点的凸包（再快一点）。 en.wikipedia.org/wiki/Gift_wrapping_algorithm

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

现在，寻找在你的形状上的点，但不是在凸包。对于这些点的每次运行，从这些点（加上凸包的任一侧上的2）创建新的形状。

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....

这篇关于如何用Convex形状形成凹形？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！