1

四辺形（4x,y点で構成）を三角ストリップに変換する最速の方法は何ですか？私は存在する一般的な三角測量アルゴリズムをよく知っていますが、四辺形のみを処理する短く、十分に最適化されたアルゴリズムが必要です。

私の現在のアルゴリズムはこれを行います。これはほとんどのクワッドで機能しますが、それでも一部のクワッドではポイントが混同されます。

#define fp(f) bounds.p##f

/* Sort four points in ascending order by their Y values */
point_sort4_y(&fp(1), &fp(2), &fp(3), &fp(4));

/* Bottom two */
if (fminf(-fp(1).x, -fp(2).x) == -fp(2).x)
{
    out_quad.p1 = fp(2);
    out_quad.p2 = fp(1);
}
else
{
    out_quad.p1 = fp(1);
    out_quad.p2 = fp(2);
}

/* Top two */
if (fminf(-fp(3).x, -fp(4).x) == -fp(3).x)
{
    out_quad.p3 = fp(3);
    out_quad.p4 = fp(4);
}
else
{
    out_quad.p3 = fp(4);
    out_quad.p4 = fp(3);
}

編集：私は、単一のクワッドを4つのポイントで構成される単一の三角ストリップに変換することについて質問しています。

4

2 に答える 2

3
  1. 座標を使用してクワッドの極値点を見つけます。であるとしましょうp。ここで、pは循環コンテナのイテレータです。
  2. p + 2によって形成された耳の内側にあるかどうかを確認し{p - 1, p, p + 1}ます。はいの場合、他の座標で極値を探し（またはからminに、maxまたはその逆に切り替えて）、手順1を繰り返します。
  3. 極値の周りの「耳」を切り取って、四角形を2つの三角形に分割します t0 = { p - 1, p, p + 1}。 t1 = { p + 1, p + 2, p - 1 }

並べ替える必要はありません。極値を見つけるだけです。クワッドが凸状（実際の四辺形）であることが保証されている場合は、極値検索をスキップして任意のを選択しますp。

編集：コメントからの提案に従って変更されました。また、コメンターによって提案された定式化は、実装がより簡単です。

  1. クワッドA, B, C, Dフォームが与えられた場合、対角線 ACとBD
  2. ポイントBとDが異なる側にあるAC場合ACは、クワッドを分割するために使用できます
  3. 同じ推論をBDとポイントに適用しA、C
于 2012-09-03T09:18:21.020 に答える
2

クワッドが与えられると、それをまたはA B C Dに分割できます。A B C, A C DA B D, D B C

A-Cとの長さを比較B-Dし、分割エッジに短い方を使用します。つまり、A B C, A C DifA-Cが短い場合は、それ以外の場合に使用し A B D, D B Cます。

于 2012-09-03T08:41:07.093 に答える