3

これは別の質問から派生したものであり、問​​題に対する Keith Randall の回答と関係があります。下の関数が何をしようとしているのかを確認するために、そこにある画像を簡単に見てください。

つまり、 と の場合、2D グリッド上の任意の 2 点には 2 つの対角線交点がx2 != x1ありy2 != y1ます。次の関数を実装しましたが、デルタを減算するセルと加算するセルを決定する方法がわかりません。その結果、ある座標のペアでは結果が正確になり、他のペアでは結果が逆になります。

// This class is the same as [Point] except
// it uses BigInteger instead of Int32 types.
public class Cell
{
    System.Numerics.BigInteger X = 0;
    System.Numerics.BigInteger Y = 0;
}

public List<Cell> GetIntersections (Cell c1, Cell c2)
{
    List<Cell> cells = new List<Cell>();
    System.Numerics.BigInteger delta = 0;
    System.Numerics.BigInteger deltaHalf = 0;
    System.Numerics.BigInteger width = 0;
    System.Numerics.BigInteger height = 0;

    width = System.Numerics.BigInteger.Abs(c2.X - c1.X);
    height = System.Numerics.BigInteger.Abs(c2.Y - c1.Y);
    delta = System.Numerics.BigInteger.Abs(height - width);
    deltaHalf = System.Numerics.BigInteger.Divide(delta, 2);

    // INTRODUCE CONDITIONS HERE TO DETERMINE +/- COMBINATION.
    cells.Add(new Cell(c1.X - deltaHalf, c1.Y + deltaHalf));
    cells.Add(new Cell(c2.X + deltaHalf, c2.Y - deltaHalf));

    return (cells);
}

最初は、これは単純な勾配/勾配の問題だと思っていましたが、 と の組み合わせの間に一貫した相関関係を見つけることができないようslopeです+/- deltaHalf。

重要:受け入れ可能な回答は、x1、y1、x2、y2 の比較のみを行う必要があることに注意してください。実際に線の傾きを計算することは、パフォーマンス上のペナルティのためオプションではありません。すでに 2 による除算を行っており、別の除算を行う余裕はありません。

4

2 に答える 2

0

単純に斜辺 ( ) を使用することはできませんdelta。三角形の高度を発見する必要があります。そして、後でわかるように、高度を取得するには脚を計算する必要があります (ピタゴラスの定理を使用)。

ただし、これを達成するBigIntegerには、平方根が存在するため、追加の助けが必要です。ここで提供されているソリューションを使用しました(ニュートン ラフソン法)。

これらの値を取得しましょう:

    // leg = sqrt(hypoteneuse²)/2)
    triangleLeg = SqRtN(System.Numerics.BigInteger.Divide(System.Numerics.BigInteger.Pow(delta, 2), 2));
    // altitude = leg²/hypoteneuse
    triangleAltitude = System.Numerics.BigInteger.Divide(System.Numerics.BigInteger.Pow(triangleLeg, 2), delta);

さて、要点として、deltaHalf( Yの場合) とtriangleAltitude( Xの場合) を使用します。

私はこのようにしました：

        // INTRODUCE CONDITIONS HERE TO DETERMINE +/- COMBINATION.
        cells.Add(
            new Cell()
            {
                X = c1.X < c2.X? c1.X - triangleAltitude : c1.X + triangleAltitude,
                Y = c1.Y < c2.Y ? c1.Y - deltaHalf : c1.Y + deltaHalf
            }
        );

        cells.Add(
            new Cell()
            {
                X = c2.X < c1.X ? c2.X - triangleAltitude : c2.X + triangleAltitude,
                Y = c2.Y < c1.Y ? c2.Y - deltaHalf : c2.Y + deltaHalf
            }
        );

フィードバックをお待ちしております。

于 2012-08-07T19:50:29.000 に答える
0

答えは、斜辺を計算するのではなく、単純な比較のどこかにあることがわかりました。

public List<Cell> GetCellIntersections (Cell cell1, Cell cell2)
{
    Cell c1 = null;
    Cell c2 = null;
    List<Cell> cells = null;
    System.Numerics.BigInteger delta = 0;
    System.Numerics.BigInteger deltaHalf = 0;
    System.Numerics.BigInteger width = 0;
    System.Numerics.BigInteger height = 0;

    cells = new List<Cell>();

    // Sorting on y reduces conditions from 8 to 4.
    if (cell1.Y < cell2.Y)
    {
        c1 = cell1;
        c2 = cell2;
    }
    else
    {
        c1 = cell2;
        c2 = cell1;
    }

    if ((c1.X != c2.X) && (c1.Y != c2.Y))
    {
        width = System.Numerics.BigInteger.Abs(c2.X - c1.X);
        height = System.Numerics.BigInteger.Abs(c2.Y - c1.Y);
        delta = System.Numerics.BigInteger.Abs(height - width);
        deltaHalf = System.Numerics.BigInteger.Divide(delta, 2);

        if ((c1.X < c2.X) && (c1.Y < c2.Y))
        {
            if (width < height)
            {
                cells.Add(new Cell(this, c1.X - deltaHalf, c1.Y + deltaHalf));
                cells.Add(new Cell(this, c2.X + deltaHalf, c2.Y - deltaHalf));
            }
            else
            {
                cells.Add(new Cell(this, c1.X + deltaHalf, c1.Y - deltaHalf));
                cells.Add(new Cell(this, c2.X - deltaHalf, c2.Y + deltaHalf));
            }
        }
        else
        {
            if (width < height)
            {
                cells.Add(new Cell(this, c1.X + deltaHalf, c1.Y + deltaHalf));
                cells.Add(new Cell(this, c2.X - deltaHalf, c2.Y - deltaHalf));
            }
            else
            {
                cells.Add(new Cell(this, c1.X - deltaHalf, c1.Y - deltaHalf));
                cells.Add(new Cell(this, c2.X + deltaHalf, c2.Y + deltaHalf));
            }
        }
    }

    return (cells);
}
于 2012-08-08T19:55:00.853 に答える