1

SVGパスによって作成された不規則な形状を前提として、その中に収まる最大の長方形（水平方向と垂直方向の境界線のみ）をどのように計算しますか？

4

2 に答える 2

2

一般的なケースでは、最大の長方形を見つけることができないと思います。グリッド上に描画された形状の内側に収まる最大の長方形を見つけるために問題をよりよく考慮する必要があります。それはあなたが探しているものの良い近似を与え、グリッドのステップを減らすことによって、精度を上げることができますあなたの近似の。

グリッドでは、問題はO（n）で解決できます。ここで、nはグリッド内のセルの数です。

于 2012-05-08T23:56:34.633 に答える
0

SVGパスは、線のセグメント、3次ベジェパス、2次ベジェパス、および楕円弧で構成されます。したがって、区分的に微分可能です。これは、無限の繰り返しではなく、有限数のセグメントで構成されます。笑わないでください。そのようなことは、Haskellなどの「遅延」プログラミング言語で簡単に表現できますが、SVGでは許可されていません。特に、SVGパスは私たちの目にはフラクタルのように見えるかもしれませんが、数学的にはフラクタルになることはできません。さらに、定数は整数またはIDL浮動小数点数のみにすることができます。これらは、IEEE単精度浮動小数点数です。したがって、グリッドポイントにこれらすべての数値が含まれるグリッドの解像度は大きいと見なされる可能性がありますが、それは確かに有限です。

これらの事実を使用して、一般に、SVGパスが領域を囲む場合、パスで囲まれた長方形の最大の領域が存在すると主張します。そして、その面積が最大の面積である（少なくとも）1つの長方形を見つけるための扱いやすいアルゴリズムがあること。

どのアルゴリズムでも、空間充填曲線（の近似）などの難しいケースを考慮する必要があります。この曲線には、小さいが「最大」の長方形が多数含まれている可能性があります。アルゴリズムがわからないので、ここでアルゴリズムの開発方法を検討します。線分だけでできているパスの問題を解決できますか？メッシュ生成アルゴリズムは役に立ちますか？同じ中心と面積を持つ長方形の角が双曲線のペアにあると考えるのは役に立ちますか？凸包アルゴリズムについて知ることは役に立ちますか？max-minと呼ばれる微分計算法が必要ですか、それとも必要ありませんか？次に、他のタイプのパスセグメントを許可するようにアルゴリズムをどのように拡張しますか？これらのパスセグメントをポリゴンパスとして近似する必要があるか、役立つか、または不要ですか？

于 2012-05-09T01:35:19.153 に答える