1

光源は、単一の座標に位置する 2D 空間内のエンティティです。

周囲のさまざまな場所に複数の光源があり、それぞれが N、S、E、W、NW、NE、SW、SE の方向に 8 つの光線を放ちます。すべてのライトの座標は既知です。

グリッド内のこれらの光線のすべての交点を計算する必要があります。

long width = int.MaxValue; // 2D grid width.
long height = int.MaxValue * 3; // 2D grid height.
List<Point> lights = a bunch of randomly placed light sources.
List<Point> intersections = calculate all possible intersections.

for (int i=0; i < lights.Count - 1; i++)
{
    for (int j=i + 1; j < lights.Count; j++)
    {
        // How to compare using integers only?
        // If that is not possible, what is the fastest alternative?
    }
}
4

3 に答える 3

3

私の答えは、リンクされた質問に対するあなたのコメントに基づいています:2つの特定の点で斜めの光線がどの座標で交差するかを判断する簡単な方法はありますか? 光源によって与えられた光線の交点を決定したいようです。

すでに説明したことから、水平/垂直のケースは簡単です。2 つのソース間のポイントが交点を表します。対角線のケースはよりトリッキーです。これにアプローチする最も簡単な方法は、単に線の交点を計算することだと思います。

各対角線/反対角線は、 が光源の位置、 が光線の方向 ( 、、、または)ray = s + u * dであるベクトル方程式によって記述される線として記述できます。ソースごとに 4 つの方程式があり、方向ごとに 1 つです。ここで、対角線の交点を見つけるには、2 つのソースの非平行線の交点を見つけるだけです (一方のペアは平行になるため、交差できません)。sd[1, 1][1, -1][1, 0][0, 1]

これが明確でない場合は申し訳ありませんが、これを更新しようとします。

アップデート

簡単な最適化として、光源間の直線距離( ) が偶数である場合にのみ、光線が斜めに交差します。|x1 - x2| + |y1 - y2|ケースを単純化するのに役立つ他の条件があると思います。

これは、必要な方程式を見つけるための派生です。2 つの光線から始めます。

ray1 = s1 + u1 * d1
ray2 = s2 + u2 * d2

直交座標では:

ray1x = s1x + u1 * d1x
ray1y = s1y + u1 * d1y
ray2x = s2x + u2 * d2x
ray2y = s2y + u2 * d2y

交差点で、ray1x = ray2xおよびray1y = ray2y:

s1x + u1 * d1x = s2x + u2 * d2x
s1y + u1 * d1y = s2y + u2 * d2y

物事を簡単にするために、次のものを分離して排除できますu2

u2 = (s1x - s2x + u1 * d1x) / d2x
u2 = (s1y - s2y + u1 * d1y) / d2y

(s1x - s2x + u1 * d1x) / d2x = (s1y - s2y + u1 * d1y) / d2y
(s1x - s2x + u1 * d1x) * d2y = (s1y - s2y + u1 * d1y) * d2x

次に を解きu1ます:

(s1x - s2x) * d2y + u1 * d1x * d2y = (s1y - s2y) * d2x + u1 * d1y * d2x
u1 * (d1x * d2y - d1y * d2x) = (s1y - s2y) * d2x - (s1x - s2x) * d2y

u1 = ((s1y - s2y) * d2x - (s1x - s2x) * d2y) / (d1x * d2y - d1y * d2x)

見つけるu2には、上記の方程式の 1 つを評価するか、次を使用します。

u2 = ((s2y - s1y) * d1x - (s2x - s1x) * d1y) / (d2x * d1y - d2y * d1x)

それで、あなたはそれを持っています。ソースの位置 と光線の方向 が与えられ、について解く2u1つの方程式。元の方程式に値を差し込むだけで、1 つのペアの交点が得られます。あなたの場合、とが整数である場合にのみ、交差点が存在します。方向がとの場合、ゼロによる除算が発生するケースが 1 つありますが、そのケースを解決するのは簡単です (ソースの非ゼロ座標が交点の座標を形成します)。u2s1s2d1d2u1u2rayu1u2[1, 0][0, 1]

于 2012-07-27T03:50:34.107 に答える
1

私はここから数学を持ち上げました、

さて、各ポイントには4つの「基本光線」があります。光線は2つのポイント間を通過する無限の線です。

// A line in the form Ax+By=C from 2 points
public struct Ray
{
    public readonly float A;
    public readonly float B;
    public readonly float C;

    public Ray(PointF one, PointF two)
    {
       this.A = two.y - one.y;
       this.B = one.x - two.x;
       this.C = (this.A * one.x) + (this.B * two.x); 
    }
}

枢機卿を取得するために私たちは拡張することができますPointF

private readonly SizeF NS = new SizeF(0.0F, 1.0F);
private readonly SizeF EW = new SizeF(1.0F, 0.0F);
private readonly SizeF NESW = new SizeF(1.0F, 1.0F);
private readonly SizeF NWSE = new SizeF(-1.0F, 1.0F);

public static IEnumerable<Ray> GetCardinals(this PointF point)
{
    yield return new Ray(point + NS, point - NS);
    yield return new Ray(point + EW, point - EW);
    yield return new Ray(point + NESW, point - NESW);
    yield return new Ray(point + NWSE, point - NWSE);
}

2つの光線の交差点を見つけるために私たちができること

static PointF Intersection(Ray one, Ray two)
{
    var delta = (one.A * two.B) - (two.A * one.B);

    if (delta == 0.0F)
    {
        //Lines are parallel
        return PointF.Empty;
    }
    else
    {
        var x = ((two.B * one.C) - (one.B * two.C)) / delta;
        var y = ((one.A * two.C) - (two.A * one.C)) / delta;
        return new PointF(x, y);
    }
}

したがって、2点の枢機卿の交点を取得するには、

public static IEnumerable<PointF> GetCardinalIntersections(
    this PointF point,
    PointF other);
{
    return point.GetCardianls().SelectMany(other.GetCardinals(), Intersection)
        .Where(i => !i.IsEmpty());
}

これにより、

public static IEnumerable<PointF> GetCardinalIntersections(
    this PointF point,
    IEnumerable<PointF> others);
{
    return others.SelectMany((o) => point.GetCardinalIntersections(o));
}

その後、この機能をこのように使用できます。

var point = new PointF(1.0F, 1.0F);

var others = new [] { new PointF(2.0F, 5.0F), new PointF(-13.0F, 32.0F) };

var intersections = point.GetCardinalIntersections(others);

明らかに、ここには多くの反復があります。私はこれをコンパイルまたはテストしていませんが、その核心で、数学はかなり効率的であるように思われるので、私はパフォーマンスについて楽観的です。

于 2012-07-30T09:33:17.250 に答える
1

座標平面のサイズが固定されていて、さまざまな位置にある光源に対してこれらの計算を何度も実行すると仮定すると、すべてのポイントを反復処理するよりもうまく実行できます。

4つのブール(またはビット)配列を作成できます。

  1. ホリス
  2. ヴェルティ
  3. DiagR
  4. DiagL

そして、光源ごとに、それらを1次元配列に「投影」します。(写真では、2つの投影のみを示しています)。

ここに画像の説明を入力してください

HorizとVertiへの投影は簡単です。

写真に示されているDiagR配列に点(x、y)を投影するのは、xとyを足したものと同じくらい簡単です。

これで、すべてのグリッドポイントをウォークオーバーして、少なくとも2つの投影がtrueに設定されているかどうかを確認できます。

しかし、私たちはもっとうまくやることができます、

たとえば、この例では、Verti配列の上を歩くことから始めることができます。

Verti [0]がtrueに設定されていることに気付きました。ここで、Verti [0]がHoriz、DiagR、DiagLと交差するかどうかを確認します。

DiagR(写真の他の配列)との交差をチェックするには、DiagR [0]、DiagR [1]、DiagR [2]、およびDiagR[3]が真であるかどうかを確認するだけでよいと計算します。その配列の残りの部分は無視してください。

Verti [0]の光は、その要素のいずれかで地平線と交差する可能性があります。

Verti [0]のライトは、DiagLの位置0、1、2、および3でのみDiagLと交差できます。

Verti[i]の残りの部分を続行します。

これで、DiagRおよびDiagLを使用した真のHoriz[i]からの交差点を探すのと同様のことができます。

最後に、DiagRの上を歩き、DiagLとの交差点を探します。

これにより、光線のすべての交点のリストが返されますが、これには光源の点も含まれます。

ポイントソースがある場所で発生するすべての交点を単に無視するか、またはそれらのポイントを説明するためにいくつかの工夫を使用することができます。

于 2012-07-27T19:51:37.697 に答える