5

ポイント（int x、int y）のリストがあります。一緒に領域を形成します。この領域が閉じているかどうかを確認し、この領域内にあるすべての位置によって形成される内部領域を取得する必要があります。

エリアの例:

ここに画像の説明を入力

私が持っていた唯一のアイデアは、この領域をベクトルに変換し、すべてのポイントがポリゴンの内側にあるかどうかをチェックし、ポリゴンの交点を軸のポイントとして数えることです。

しかし、それが最も効率的な方法だとは思いません。

他のアイデアは、最初に外側にあるすべてのポイントを取得することでした。コーナーから開始し (コーナーがポイントのリストの一部ではない場合、100% 空です)、空のすべての隣接ポイントを追加して繰り返します。外側になく、強調表示されたリストにないすべてのポイントは内側にあります。

だけど、なんだか面倒くさい…。

4

2 に答える 2

4

グリッド ポリゴンのすべての内側のグリッド ポイントを見つけるには、次の観測結果を利用できます。

  1. 各内側グリッド ポイント (x,y) についても、(x,y+0.5) および (x,y-0.5) は内側ポイントです。
  2. によって定義された線y=n+0.5は、グリッド ポリゴンと単純に交差します。

これにより、次のアルゴリズムが得られます。

  1. 前提条件として、すべての非水平 (つまり、垂直および対角線) のポリゴン エッジが必要です。実際には、各 (2 番目の) 中間行の昇順の中心の x 座標のみが必要です。

  2. グリッドは、1 秒ごとに水平方向の「中間線」でスキャンされます。つまりy=2n+0.5、n はポリゴンが「覆われる」十分な範囲の整数です。スケッチの青い線を参照してください。

  3. 左から始めて、多角形とのすべての交点 (つまり、非水平エッジ) とフォーム (m,2n+0.5) のすべての内側の点が検出されます。赤と緑の円を参照してください (これは、エッジの中心の x 座標)
  4. ここで、内側の点 (m,2n+0.5) の垂直グリッド近傍 (m,2n) および (m,2n+1) は内側の点です。境界上にない場合は、画像の緑色の点を参照してください。

AlgoScetch_innerPoints

ここにいくつかの疑似コードがあります (C++/python にインスパイアされた :-) ):

list<Point> polygon; // given polygon as list of neighbouring grid points

// get centers of non-horizontal edges organized by line
map<int, set<float> > edgeCentersX; // for each scan line the x-coords of edges in ascending order

p_i = polygon[0]
yMin, yMax =  999999, -999999
for (i=1; i<polygon.size(); ++i)
    p_i1 = polygon[i] // next point after p_i
    if (p_i.x == p_i1.x)
        continue // horizontal edges can be ignored
    yMin_i = min(p_i.y, p_i1.y)
    if (yMin_i % 2 == 1)
        continue // we only need to look at each second mid-row
    if (yMin_i < yMin)
        yMin = yMin_i
    if (yMin_i > yMax)
        yMax = yMin_i
    cx = 0.5*(p_i.x+p_i1.x)
    edgeCentersX[yMin_i].insert(cx) // store edge center (yMin_i+0.5, cx)
    p_i = p_i1

list<Point> innerPoints
for (y=yMin; y<= yMax; y+=2)
    inside = false
    cx_i = edgeCentersX[y][0]
    for (i=1; i<edgeCentersX[y].size(); ++i)
        cx_i1 = edgeCentersX[y][i]
        inside = !inside
        if (!inside)
            continue
        for (x=floor(cx_i)+1; x<cx_i1; ++x)
            pLower = Point(y,x)
            if (!polygon.contains(pLower))
                innerPoints.append(pLower)
            pUpper = Point(y+1,x)
            if (!polygon.contains(pUpper))
                innerPoints.append(pUpper)
于 2013-02-04T14:57:34.987 に答える
0

ピックの定理は、あなたが探している公式かもしれません。角が格子点である (つまり、整数座標を持つ) 多角形の面積をかなり簡単に計算できます。

于 2013-02-04T11:30:54.700 に答える