小编Cra*_*aig的帖子

我想知道是否有人能指出我最适合我特定多边形包装问题的算法/启发式算法.我给了一个多边形作为边界(凸面或凹面也可能包含孔)和一个"填充"多边形(也可能是凸面或凹面,不包含孔)我需要用指定的数字填充边界多边形填充多边形.(我在2D工作).

我发现的许多多边形填充启发式假设边界和/或填充多边形将是矩形的,并且填充多边形将具有不同的大小.在我的例子中,填充多边形可能是非矩形的,但都是完全相同的.

也许这是一种特殊类型的包装问题？如果有人对这种类型的多边形包装有一个定义,我很乐意google,但到目前为止,我还没有发现任何类似的东西都很有用.

谢谢.

我想弄清楚如何完全填充自定义几何体.这似乎应该是一个常见的问题,但我还没有真正找到任何解决方案.

我有以下示例几何:

    <Path Fill="White" Stretch="Fill" Stroke="Black" StrokeThickness="2">
        <Path.Data>
            <PathGeometry
                Figures="M112,296C112,296 136,296 136,320 M112,344C112,344 136,344 136,320 M112,296L112,296 96,296 96,344 112,344"/>
        </Path.Data>
    </Path>

这产生以下结果:

这是我希望看到的结果:

有任何想法吗？我知道我可以制作一个弧形并且可以解决这个特殊情况,但在我的应用程序中,用户可以绘制任何类型的几何体,因此结果可以由任意数量的"基元"组成(PolyLineSegments,EllipseGeometries,ArcSegments等)如果生成的几何体包含某种类型的封闭区域,我想准确填充该区域.

编辑:

以下是如果我确保所有三个相邻几何图形重叠并使用以下代码创建联合CombinedGeometry,那么CombinedGeometry的示例:

        <Path Grid.Row="2" Fill="White" Stretch="Fill" Stroke="Black" StrokeThickness="2">
        <Path.Data>
            <CombinedGeometry GeometryCombineMode="Union">
                <CombinedGeometry.Geometry1>
                    <CombinedGeometry GeometryCombineMode="Union">
                        <CombinedGeometry.Geometry1>
                            <PathGeometry
                                Figures="M111,293C111,296 136,293 136,325"/>
                        </CombinedGeometry.Geometry1>
                        <CombinedGeometry.Geometry2>
                            <PathGeometry
                                Figures="M111,346C111,344 136,344 136,320"/>
                        </CombinedGeometry.Geometry2>
                    </CombinedGeometry>
                </CombinedGeometry.Geometry1>
                <CombinedGeometry.Geometry2>
                    <PathGeometry
                        Figures="M125,296L115,296 96,296 96,344 120,344"/>
                </CombinedGeometry.Geometry2>
            </CombinedGeometry>
        </Path.Data>
    </Path>

这是结果:

我希望它只会结合笔画并自动找出新的连续多边形的正确填充...无赖.

编辑2:

嗯所以我想我已经想出了几个可能的解决方案,这些解决方案都不像我希望的那样容易.第一个选项是使用CombineGeometry结构组合上面的所有几何,然后在结果"CombineGeometry"上调用"GetFlattenedPathGeometry"以获得PathGeometry.接下来,我迭代在PathGeometry中的每个图形,然后删除那些是洞(我认为你应该能够通过去除所有其他完全包含的图形来做,或者孔可以遵循顺时针方向或逆时针坐标,不确定..),如果一切顺利,你应该留下一个完全填充的几何.

第二种选择是在所得到的路径上再次调用"GetFlattenedPathGeometry",以便获得路径的基于顶点的多边形近似(没有所有曲线,弧,椭圆等符号,我们想要一个仅包含点的路径和线).之后,您只需将所有结果图形/线段组合成一个图形,其图形按顺时针或逆时针顺序排列.

我已经测试了两种方法,它们似乎至少适用于上面概述的简单测试用例,尽管它们不适用于更复杂的形状(自相交,凹陷等).我需要的支持..所以问题遗体,我该怎么做？

编辑3:

这是一个更复杂的几何图形,其中排序/组合变得更加困难:

        <Path Fill="White" Stretch="Fill" Stroke="Black" StrokeThickness="2">
        <Path.Data>
            <PathGeometry
            Figures="M104,160C104,160 72,160 72,136 …

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

这种方法不适用于许多(或者全部)凹面多边形,因为质心经常落在多边形之外,因此缩放操作也会导致平移,我需要能够"就地"缩放多边形而不需要最终结果被翻译.

有人知道缩放凹多边形的方法吗？或者也许找到"视觉中心"的方法,它可以用作缩放操作的参考框架？

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

谢谢!