問題タブ [convex-polygon]

次の問題に直面しています。多角形の頂点を定義する整数グリッド上の一連の座標が与えられています。多角形は凸面であることが保証されています。このような多角形は、直交する 2 本の線分で常に 4 つの等面積部分に分割できることが証明されています。これらの線の交点を としましょうP。そのセットを考慮して、ポリゴン内の座標とP、ラインがポリゴンを 4 つの等しい部分に分割するようにラインをオンにする必要がある角度を計算する必要があります。

一般的に言えば、ケーキカットの問題には「良い」解決策がないことを認識しています。しかし、この特定のケースはそうすべきです。その問題を解決するアルゴリズムを探しましたが、何も役に立ちませんでした。どこを見ればいいですか？

私のアプローチは、ポリゴンの中心の座標を計算し（多かれ少なかれ簡単に実行できます）、Pそこに配置してから、パーツの領域が一致するまで線を「小刻みに動かす」ことです。しかし、それはあまりにもエレガントに聞こえません。

UPD:それが私が扱っている問題です。おそらく、この質問は、実際のコードに関する質問を思い付くまで中断する必要があります。

光線で表される 2 つの多面体円錐があります。できれば効率的に、多面体円錐でもあるそれらの交点を見つけようとしています。誰もそれを行う方法を知っていますか?

ありがとう

ディーパンシュ

地形エディターを作成していますが、一連のポイントの境界ポリゴンを見つける必要があります。凸包だけが必要な場合は、速度は問題になりません。凹型の船体を作るには、いくつかのフープを通過する必要があります。ポイントを三角形分割し、ポイント間の既知の距離よりも長い辺を持つ三角形を破棄できることがわかりました。

次のステップは問題です: JSTS ジオメトリ ライブラリ ( http://github.com/bjornharrtell/jsts ) を使用して三角形 (ミニ ポリゴンとして) を 1 つの大きなポリゴンに結合するのは非常に遅いです。

完全なコードを参照してください: http://codepen.io/anon/pen/oCfDh

最終的なポリゴンを形成するためにマージされる配列 (ポリゴン) があります。問題は、552 ポイント (15k+ をサポートしたい) の場合、実行に約 3500 ミリ秒かかることです。あなたの速度については、codepen リンクのコンソールを見てください。

三角形をポリゴンにマージするか、さらに広くして、まったく異なる方法でポイントのセットから凹型ポリゴンを構築するより高速な方法を知っている人はいますか?

入力としてエッジの長さのシーケンスを取り、これらのエッジで凸多角形を形成するアルゴリズムを見つけようとしています。そのような凸が常に存在するとは限らないことは知っていますが、存在すべきデータを扱っています。

基本的に、エッジ間の角度を把握しようとしています。それらがわかれば、コーナーの座標も計算できます。

R^3 には交差が空の 2 つのポリトープ A と B があります。ポリトープは面によって定義されます。つまり、ハイパースペースの不等式のみが存在し、頂点は不明です。問題は、||ab|| となるような A の点 a と B の点 b を見つけることです。= d(A,B) -- A と B の間の距離。また、d>3 の R^2 または R^d についてこの問題を定式化できます。この問題に対するアプローチは何ですか。そして、この問題にはいくつかのアプリケーションがありますか?

単純ではない凸状の多角形を 2 つの垂直線で切断して、4 つの等しい (面積) 部分に分割する必要があります。

プログラムを書きましたが、テストに合格しません。

• その理由は、丸め誤差または面積を計算する私の機能だと思います。
• 確認してください、正しいですか？
• 靴ひものアルゴリズムとヘロンの公式を使用

コードは次のとおりです。

私がしていること：

• point(x, y)切断ポリゴンの発見。
• で切りましたx = a in [ min(x), max(x)]
• 計算しますS'(x=min(x) から x=a までのポリゴンの一部)
• の場合S' = S/2、a値の計算に使用します(a, *)
• y = bどこでも同じb in [min(y), max(y)]
• もっと速い方法はありますか？

手のひらの中心を見つけたい。まず、等高線を見つけて、最大面積等高線を選択しました。そして、pointPolygonTest を使用しました。私のコードと結果の画像を以下に示しますが、pointPolygonTest を使用してもポイントが見つかりませんでした。何が問題ですか？