寻找算法:将带有孔的形状切成一组没有孔的形状? [英] Looking for algorithm: cut a shape with holes into a group of shapes without holes?
问题描述
我正在寻找一种算法，该算法可以将有孔的形状切成无孔的形状.语言最好是C#.
I'm looking for an algorithm that can cut a shape with holes into shapes without holes. Language is preferably C#.
这是这种形状的示例图像.
Here's an example image of such a shape.
我想将该形状切成最少数量的较小形状，而没有孔消除大部分空白区域(白色).在这种情况下，这可能是一堆矩形.但是原始形状可能会更复杂，例如带有圆孔.
I'd like to cut that shape into the least amount of smaller shapes without holes getting rid of most of the empty space (white). In this case this might probabyl be a bunch of rectangles. But the original shape might be more complex with rounded holes for example.
对我来说，这听起来像某种垃圾箱包装问题，因此，使用遗传算法可能可以最好地解决.
For me this sounds like some sort of a bin packing problem and therefore might be solved best with a genetical algorithm.
但是，如果您知道更好的方法，这就是我要问的原因.
But in case you know a better approach, it's why I ask.
//edit :好的，我显然有一些要解释的东西:
//edit: alright, I've obviously got some things to explain:
-
形状是一个几何对象(WPF)，它是通过从一较大的几何图形中减去一堆小几何图形而得到的.所以我猜想顶点存储在某个地方.
The shape is a Geometry object (WPF) resulting from the subtraction of a bunch of small Geometries from a larger Geometry. So I guess there are vertex points stored somewhere.
应最大程度地减少形状的数量，是的，最小的形状.
The amount of resulting shapes should be minimized, yes, the smallest set.
所得到的形状应具有尽可能笔直的边缘，并尽可能减少拐角.
The resulting shapes should have edges that are as straight as possible with the smallest amount of corners possible.
不幸的是，我还不能提供任何代码，因为我没有任何技巧，如何实际地以编程方式来解决这个问题.真的很抱歉.
Unfortunately, I can't provide any code, yet, since I have no clou whatsoever how to practically approach this programmatically. I'm really sorry.
生成的形状应该很复杂，但不必如此.
The resulting shapes should be complex but don't have to.
要解释其原因:我正在研究一个纺织工艺(特别是拼布)程序，利用该程序可以创建拼布并计算所需的面料和成本.使用类似Tetris的算法将修补程序放置在织物面板上已经可以通过某种方式工作，该算法将修补程序尽可能地靠近放置以减少浪费.
To explain the reason for this: I'm working on a textile crafting (in particular patchworking) program with which one can create patchworks and calculate how much fabric is needed and the cost. Placing the patches on the fabric panel already works somehow using a Tetris like algorithm where patches get placed as close together as possible to reduce waste.
此外，在形状被切割的任何地方，我都需要为所得的零件添加接缝余量(这就是示例图中以绿色显示的内容).
Additionally, everywhere the shape gets cut I need to add a seam allowance to the resulting parts (that's what you can already see in green in the example image).
//编辑2 可接受的解决方案如下所示.红线显示在何处切割形状，以便获得一定数量的没有孔的形状.结果集包含六个大和25个小矩形:
//edit 2 An acceptable solution might look as follows. Red lines show where shape gets cut in order to get an amount of resulting shapes that don't have holes. The result set contains six large and 25 small rectangles:
但是，根据看起来可能完全不同的原始形状，即使带有圆角的边缘(圆形孔)，可接受的解决方案也可能看起来有所不同.目的是尽可能消除白色区域，同时在以后的实际织物切割方面保持一定的便利.不得不重新缝制很多碎纸(因此都需要接缝余量)只是为了节省更多的面料而在某种程度上适得其反.
However depending on the original shape which might look totally different, even with rounded edges (circular holes), acceptable solutions also might look different. The goal is to get rid of the white areas as far as possible while maintaining some convenience regarding the later actual cutting of the fabric. It'd be somehow counter-productive to have lots of shred that has to be sewed together again (and hence all need seam allowances) only to save a little bit fabric more.
推荐答案
我不确定您希望生成的形状如何，但是我假设您希望它们在Polygon中.就像在对象多边形中一样，它是2D顶点(x，y)的向量.现在，您可以使用此Clipper库解决几何空间问题.它可以进行多边形减法，加法，相交等等.它还快速，免费，不需要许可证.
I'm not sure how you want the resulting shapes to be but I'm going to assume that you want them in Polygon. As in an object Polygon which is a vector of 2D vertex points (x,y). What you can do now is use this Clipper library for solving geometric spatial problems. It does polygon subtraction, addition, intersection, and a bit more. Its also fast, free, and no license is needed.
http://sourceforge.net/projects/polyclipping/
此后，只需找到沿每个多边形顶点的距离并将其相加即可计算出接缝长度.但是，此库不支持弯曲的轮廓.
Afterwards, you can calculate your seam lengths by just finding the distances along each polygon vertex and adding them up. However, this library does not support curved contours.
这篇关于寻找算法:将带有孔的形状切成一组没有孔的形状?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
