SVGパス内で最大の矩形を見つける

Question

SVGパスで作成された不規則なシェイプを考えると、その中に収まる最大の矩形（水平と垂直の罫線のみ）はどのように計算されますか？

Answer 1

一般的なケースでは、最大の矩形を見つけることはできません。グリッド上に描かれている図形の中に収まる最大の矩形を見つけて、探しているものを近似し、グリッドのステップを減らすことで、精度を上げることができますあなたの近似の。

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

Answer 2

SVGパスは、線、立方体ベジエパス、二次ベジエパス、楕円弧のセグメントで構成されています。したがって、それは区分的に区別可能である。無限の再発ではなく、有限個のセグメントで構成されています。笑ってはいけません。そのようなものはHaskellのような「怠惰な」プログラミング言語で簡単に表現できますが、SVGでは許されません。特に、SVGの経路は、我々の目にフラクタルのように見えるかもしれませんが、数学的にはフラクタルではありません。さらに、定数はIEEE単精度浮動小数点数である整数またはIDL浮動小数点数のみにすることができます。だからグリッドポイントでそれらの数字のすべてを持つグリッドの解像度は大きいと考えられるかもしれませんが、確かに有限です。

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

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