5

凹多角形または凸多角形の内側にある軸に沿った長方形を見つける方法を探しています。

私はウェブを見回してきましたが、私が見つけた最も近い解決策は凸多角形にのみ適合し、凹多角形には適合しませんでした。例えば ​​-

ポリゴン内で軸に沿った長方形を見つける

正直なところ、私は数学の専門家ではないので、コードサンプルやコードライブラリを見つけたいと思いますが、自分で数学を処理するか、誰かに助けてもらうことができると思います。

解決策がJavaでもあるとしたら本当にいいのですが、私は貪欲すぎるかもしれません：P

編集：ラッセルのコメントに応えて、私はもう少し情報を追加しています。

境界のある長方形は、できるだけ大きくする必要があります。長方形は、その中にテキストを含めることを目的としています。最大1〜4語、テキストの折り返しをサポート。したがって、たとえば薄すぎる場合は、テキストを水平方向ではなく垂直方向に配置します。したがって、アスペクト比については、ワードラップを使用して垂直方向または水平方向に1〜4語を含めるのに十分である必要があると思います。長方形が小さい場合はテキストのサイズを変更できますが、テキストはできるだけ大きくすることが望ましいです。

ポリゴンの一般的な方向が対角線であり、対角線の方向にテキストがはるかによくフィットする場合、長方形は必ずしも軸と位置合わせされるとは限らず、代わりに次のように位置合わせされるというもう1つの要件があります。ポリゴンの対角線。この要求がこれを本当にトリッキーにしていると思いますが、皆さんがそれが可能だと思うなら、それは素晴らしいことです！

これですべての要件をカバーできたと思います。：P

ありがとう！

4

2 に答える 2

1

テキストに対してこれを行いたいので、速度が重要であり、正確性はそれほど重要ではないと仮定します。私はこれを提案します：

  1. セルがテキストの寸法に比例するグリッド上に多角形を配置します。
  2. Bresenham のライン アルゴリズムを使用して、境界上のセルを削除します。.
  3. 境界セルの外側のセルを削除します (グリッドの端から内側に向​​かって作業します。
  4. ここに示す方法など、残りのセルで最大の四角形を見つけます。

パズル: 最大の長方形を見つける (最大長方形の問題)も参照してください。

編集:ポリゴンが斜めに向いている場合、このアルゴリズムが調整するという要求に気付きました。私の提案は、ポリゴンの主軸を見つけて方向を確認し、回転させて主軸を x 軸に合わせ、上記のアルゴリズムを適用することです。

また、「セルを削除する」とは、実際にはグリッド セルを表す 2D 配列にビットを設定することを意味することに注意してください。

于 2012-04-19T00:04:23.703 に答える
1

私はかつて、可能な長方形を検索しShape.contains()てそれらを使用するだけで、非常に厄介な方法で同様のシステムを実装しました。やや遅かった - 楕円形の Gettsburg Address のレイアウトではおそらく 1 秒だった - しかし、静的テキストや単純な形状の小さなテキストには便利だった.

興味がある場合は、こちらで jar ファイルを解凍して を参照してくださいTextWrappingLayout。単一の長方形にレイアウトする代わりに、各線をできるだけ端に近づけようとするため、おそらく必要なものよりもはるかに複雑ですが、基本的な考え方はわかります。

于 2012-04-18T18:21:07.220 に答える