4

ここにある擬似コードを使用してポリゴン内の交差点を見つけるために、LuaでBentley-Ottmannアルゴリズムを実装しています。

私はアルゴリズムの実装に比較的慣れていないので、そのすべての部分を理解することはできませんでした。これまでの私のコードは次のとおりです。

local function getPolygonIntersectingVertices( poly )
  -- initializing and sorting X
  local X = {}
  for i = 1, table.getn( poly ) do
    if i == 1 then
      table.insert( X, { x = poly[i].x, y = poly[i].y, endpoint = 'left' } )
    elseif i == table.getn( poly ) then
      table.insert( X, { x = poly[i].x, y = poly[i].y, endpoint = 'right' } )
    else
      table.insert( X, { x = poly[i].x, y = poly[i].y, endpoint = 'right' })
      table.insert( X, { x = poly[i].x, y = poly[i].y, endpoint = 'left' })
    end
  end

  local sortxy = function( a, b )
    if a.x < b.x then return true
    elseif a.x > b.x then return false
    elseif a.y <= b.y then return true
    else return false end
  end
  table.sort( X, sortxy )

  -- Main loop
  local SL = {}
  local L = {}
  local E
  local i = 1
  while next(X) ~= nil do
    E = { x = X[i].x, y = X[i].y, endpoint = X[i].endpoint }
    if E.endpoint == 'left' then
      -- left endpoint code here
    elseif E.endpoint == 'right' then
      -- right endpoint code here
    else
    end
    table.remove( X, i )
  end

  return L
end

私のポリゴンは、次の構造を使用したテーブルです：{{x = 1、y = 3}、{x = 5、y = 6}、...}

「 SLのsegEより上のセグメント」と「 SLのsegEより下のセグメント」を判別するにはどうすればよいですか？また、スイープライン（SL）が空の場合はどうすればよいですか？また、IをXに挿入するときは、endpoint ='intersect'でマークして最後に追加する必要があります。これにより、ループがこの部分に到達したときに、メインループの "else"ステートメントに入るか、アルゴリズム全体が得られます。間違い？

疑似コードをたどってC++の例と一致させるのは難しいので、PythonやRubyなどの簡単な実装とのリンクを誰かに見せてもらえると完璧でしょう。

4

1 に答える 1

2

あなたの参照リンクは私の場所から失敗します。かなり良いウィキペディアの記事を参照します。

「SLのsegEより上のセグメント」を特定するにはどうすればよいですか。および「SLのsegEの下のセグメント」。

このアルゴリズムでは、yのキーで、つまり垂直方向に並べ替えられた現在のスキャンラインの交点にBSTが必要です。したがって、上のセグメントはBSTの後継であり、下のセグメントはBSTの前のセグメントです。BST内の特定のノードの先行および後続を見つけることは標準的なことです。キーKの先行ノードは、Kの左端のノードです。後続ノードは、Kの右端のノードです。これらを計算するには、いくつかの方法があります。最も簡単なのは、親ポインターを使用して、Kからツリーを上下に移動することです。スタックベースのイテレーターは、もう1つです。

スイープライン（SL）が空の場合はどうすればよいですか？

イベントキューの処理を続けます。空のスイープラインは、現在のx位置で交差しているセグメントがないことを意味します。

また、IをXに挿入する場合、endpoint ='intersect'でマークして、最後に追加する必要があります...？

イベントキューは、ポイントのx座標でソートされたままである必要があります。交差点を挿入するときは、それもx座標の順序である必要があります。交差点はエンドポイントとは異なる方法で処理されるため、交差点としてマークする必要があります。x順で最初に残っているアイテムになると、やがて処理されます。

Bentley Ottmanは、ほぼすべての幾何学的アルゴリズムと同様に、浮動小数点の不正確さによる恐ろしい失敗の影響を受けることで有名です。また、アルゴリズムは通常、「一般位置」の仮定で与えられます。これにより、垂直エッジ、ポイントエッジの一致、エッジエッジのオーバーラップなどの厄介なケースがすべて排除されます。有理演算を使用することを強くお勧めします。それでも、完全に堅牢で正しい実装を取得することは重要な成果です。これは、ごく少数の無料の実装でわかります。

于 2013-01-25T00:02:47.323 に答える