問題タブ [convex-polygon]

比較的単純なことを解決する必要があります。n個の頂点の凸型2Dポリゴンと、「y」座標を持つ水平（！）線があります。必要なのは1つだけです。ポリゴンがこの線と交差しているかどうか（つまり、2つの交差があるかどうか）を確認することです。

私が考えることができる最も速いものは、ポリゴン内の最小/最大y座標を見つけ（2つの比較と2つのストアでn回繰り返されるループ）、次に最小y <=y<最大yであるかどうかを比較することです。

どういうわけか、これはもっと「数学的に」解決できると思いますが、私は常に遅いコードで終わります（たとえば、ベクトルの方法-n[i]とn[i + 1]の差を計算してから、それらを乗算したり、追加したりする必要があります- -2 cmps +ストアよりもはるかに遅い）。

このようなQuadCurve（+=ノード）がある場合：

そして、Java 2Dで入力すると、結果は次のようになります：（x=色付き）

しかし、私は反対側を着色したいと思います：

これは、反対側に色を付けたい色で曲線の周りに長方形を描画してから、曲線を背景色で塗りつぶすことで成功します。

しかし、これは凸状の丸みを帯びた（QuadCurvesに基づく）ポリゴンを塗りつぶすには十分ではありません。長方形のいくつかの座標の場合（私が使用したトリックで説明したように）、ポリゴンの他の部分と重なります。これが2つの画像です（緑色の領域は私のポリゴンです）：

代替テキストhttp://img204.imageshack.us/img204/7823/convexpolygon.png 代替テキストhttp://img708.imageshack.us/img708/3669/convexpolygon2.png

したがって、質問は単純です。「曲線のシェイプビルドに色を付けるにはどうすればよいですか？」
しかし、答えは簡単ではないと思います...

どんなアドバイスも非常にありがたいです。
前もって感謝します。

_{答えが得られない場合は、この質問に報奨金を支払うつもりです。}

凸多角形が与えられた場合、その直径を維持しながら (「最大面積」のように) その形状を拡大しようとしています。直径は、ポリゴン内に配置できる最長のセグメントの長さとして定義されます。多角形は凸面なので、すべての頂点のペアをスキャンすることで、この直径を常に見つけることができると思います。

たとえば、正三角形を入力ポリゴンとして指定すると、三角形の直径はエッジの長さになります。これを平滑化すると、画像に示すように 3 つの円セグメントが生成されます

任意の凸多角形の場合、各多角形の頂点を中心とする最大直径の半径の円の交点を計算するアルゴリズムは非常に非効率的です。これは私が現在使用しているものです（Javaで）。もっと良いものはありますか？アルゴリズムへの疑似コードまたはポインタは高く評価されます。

別の例: 押しつぶされた五角形とそれに対応する直径を維持する最大形状。直径を大きくしないと、この形状の面積を大きくすることはできません (つまり、元の直径よりも長い形状の境界内に直線を引くことができます)。この特定のケースでは、radius = polygon_diameter/2 (ピンク) の単一の円は、radius = polygon_diameter (水色) の複数の大きな円の交点よりも優れているようです。2 番目のイメージは、比較を容易にするために両方の領域を重ね合わせていますが、領域はポリゴンを完全に囲む必要があります。

私はいくつかの解決策を見つけましたが、それらはあまりにも厄介です。

私はopenGLが初めてで、レッドブックを読んでいます。さて、演習として、手動で球を描きたいと思います。そのために、球をスライスとスタックに分割しているため、複数の長方形が得られますが、球の極の近くでは三角形が得られます。（これが私がやっていることを明確にしていることを願っています）。GL_POLYGON で多角形を描画し、たまたまそれ自体が交差した場合、動作は未定義であることがわかりました。私の質問は次のとおりです。1 つの行にない 3 つの点 v1、v2、v3 が与えられた場合、これを行う未定義の動作は次のとおりです。

これは 2 つの無関係な質問を 1 つに結合している可能性がありますが、これも疑問に思っています: 球ルーチンで長方形を三角形に分割することを選択した場合、どのように分割するか、つまり、長方形をどの対角線で分割するかは重要ですか?二つの三角形？単色の球体を描く場合は問題ないと思いますが、テクスチャ、シェーダー、照明などについてはわかりません。

青で表示されている次のポリゴンを分解して、凹面の原因となるすべてのポイントをポリゴンから削除します。

現在、私がやろうとしていることは次のとおりです。

• ポリゴンから各ポイントを取り出します
• ポイントをテストして、セットの残りの部分によって作成されたポリゴン内にあるかどうかを確認します
• trueの場合、ポイントを削除します
• falseの場合、要点を維持します

これはほとんどの場合に機能しますが、前のケースでは、（2,3）と（2,4）の両方のポイントが削除されることはありません。どちらの場合も、どちらかのポイントが削除されますが、もう一方は配列が渡される順序に依存しません。

私が疑問に思っているのはこれです：

1. 私が扱っているポリゴンにこれらのケースのいずれかが発生するかどうかをテストする方法はありますか（つまり、3つの連続した障害点がありますか？）
   または
2. 凸多角形を作成するより効果的な方法はありますか？

ありがとうございました。

線が凸多角形と交差するかどうかを検出する O(n) アルゴリズムは、多角形のエッジが線と交差するかどうかをチェックし、交差の数が奇数か偶数かを調べます。

O(log n) アルゴリズムなど、漸近的に高速なアルゴリズムはありますか?

関連：ポリゴンの分解-凸多角形を形成するための凹点の削除

私は次のことを行うためのアルゴリズムを探しています：

入力は2Dポイントの配列です（P0 _… PN _-1）。配列の長さNは変化します（3≤N<∞）任意のM≤Nに対して、頂点が_P0 …PM _-1
の順序 である凸多角形が存在する場合と存在しない場合があります。

エッジは必ずしもアレイ内の隣接するペアではないことに注意してください。

この凸多角形が存在するような最大Mを見つけるための最も効率的なアルゴリズムは何ですか？

私の現在のアルゴリズムは非常に非効率的です。M = 3、M = 4、M = 5などでテストし、船体を計算してから、すべてのP0 _… P _​​M-1が船体の頂点であることをテストします。そうでない場合は、ループから抜けてM-を返します。 1.1。

例1：[(-2,2), (2,2), (-2,-2), (-1,1)]

結果：3（最初の3つのポイントは三角形を形成しますが、P ₃ =(-1,1)を追加するとポリゴンが非凸になるため）

例2：[(-2,2), (2,2), (-2,-2), (1,-1)]

結果：4（配列内の4つのポイントすべてから凸四角形を作成できるため）

例3の更新[(-3,3), (3,3), (2,-1), (-3,-3), (3,-3), (-2,1)]
： 結果：4。

この例は、提供されたすべての点の凸包を取得して、そのサブセットである接頭辞を見つけるだけでは不十分である理由を示しています。(3,-3)最初の5つのポイントで構成される凸多角形の一部にすることはできません。これは、前のポイント(2,-1)が船体上に存在しなくなるためです。しかし、それは(3,-3)6つのポイントすべての船体にあり、そうではないにもかかわらず、拒否されなければならないということ(2,-1)です。

無効な入力の例：

• [(-1,-1), (0,0)]（ポイントが少なすぎる）
• [(-1,-1), (0,0), (1,1), (1, -1)]（最初の3つのポイントは同一線上にあります。アルゴリズムがこれを処理できるとは思いません。）

このような点の密なグラフを取り、それを接続された凸多角形のグラフに変えようとしています。接続を維持しながら、ポリゴンはできるだけ大きくシンプルにする必要があります。結果のグラフは経路探索に使用されます。誰かが私を正しい方向に向けることができますか?

Cudaを使用してすべてのランダムポイントを含む凸多角形を見つけるアルゴリズムを探しています。私が適応できる非常に効率的なアルゴリズムを知っている人はいますか?