1

Sedgewick & Wayne によるアルゴリズム、演習 1.2.3:

Interval2Dコマンドライン引数N、 min、およびを取り、幅と高さがと単位正方形内に均一に分布するランダムな 2D 区間をmax生成するクライアントを作成します。それらを描画し、交差する間隔のペアの数と、互いに含まれる間隔の数を出力します。NminmaxStdDraw

Interval2D は、次の API を公開します。

Interval2D(Interval1D x, Interval1D y)
boolean intersects(Interval2D)
boolean contains(Point2D)
double area()
void draw()

Interval2Dこれらの方法だけを使用して、あるものが別の中に含まれているかどうかを確認することはできますか?

4

4 に答える 4

1

Interval1D でメソッド left() および right() を使用して、2D 間隔の作成中に事前に保存しておくことができます。

私はそのようにそれをやった

    int intersect = 0;
    int contain = 0;    
    for (int i = 0; i < N; i++) {
        for (int j = i + 1; j < N; j++) {
            if (arr2D[i].intersects(arr2D[j])){
                intersect++;
            }
            if ( (arrX[i].left() <= arrX[j].left() && arrX[i].right() >= arrX[j].right())
                && (arrY[i].left() <= arrY[j].left() && arrY[i].right() >= arrY[j].right())) {
                contain++;
            }   
        }
    }
于 2015-07-03T13:09:02.723 に答える
1

A) 状況を理解するには:

1D 間隔に関する 2D 間隔 A および B の定義:

 A = Ixa x Iya = [x1a, x2a] x [y1a, y2a]
 B = Ixb x Iyb = [x1b, x2b] x [y1b, y2b]

それで

 A is contained in B, iff 
 Ixa = [x1a, x2a] is contained in Ixb [x1b, x2b] and
 Iya = [y1a, y2a] is contained in Iyb = [y1b, y2b].

使用する

 I1 = [a, b] is contained in I2 = [c, d] iff c <= a and b <= d.

これは、Interval2D ( http://algs4.cs.princeton.edu/12oop/Interval2D.java.html ) および Intervall1D ( http://algs4.cs.princeton.edu/12oop/ )の交差メソッドの実装に似ています。Interval1D.java.html ) は、条件の論理的な逆をテストすることのみを示します。

B）今あなたの方法に：

左下 (x1a, y1a) と右上 (x2a, y2a) のポイントをチェックすると、contains(Point2D) でテストを実行できるようになります。

 A is contained in B, iff B contains (x1a, y1a) and B contains (x2a, y2a).

醜いのは、Interval1D にはプライベートな左右の座標にアクセスするゲッターがあるのに対し、Interval2D にはプライベートな x および y (1 次元) 間隔にアクセスするゲッターがないことです。toString() 出力からそれらを解析することもできますが、それは見苦しく、作業が多すぎます。スーパークラスの作成

public class Rect {
  public Interval1D x;
  public Interval1D y;
  public Interval2D r;
  Rect(Interval1D px, Interval1D py) {
    x = px;
    y = py;
    r = new Interval2D(px, py);
  }
  public boolean contains(Rect that) {
    if (!this.r.contains(new Point2D(that.x.left(), that.y.left()))) return false;
    if (!this.r.contains(new Point2D(that.x.right(), that.y.right()))) return false;
    return true;
  }
}

それを使うのはただ醜いです。

于 2013-07-14T13:00:51.500 に答える
0

間隔の上限と下限を使用して交差をチェックする方がはるかに理にかなっています。理論的には、リストされているメソッドのみを使用できるはずですが、効率的に使用するのは難しい場合があります。間隔 A に間隔 b が含まれている場合、B のすべての点は A にもあります。したがって、すべての点を反復処理して (座標系が double ではなく int に基づいている場合)、この条件を確認できます。double に直面した場合、修正された手法を使用して、高い確率で正しく機能する contains メソッドを生成できます。

//Iterate over some subset of points.
if(b.contains(pointP) && !a.contains(pointP))
   return false;

秘訣は、適切なサブセットを見つけることです。しかし、常に正しいことが保証されているアルゴリズムは、はるかに難しいと思います。一次元の場合を考えてみましょう。間隔A = (0.5,Math.PI/6)とB = [0.4,Math.PI/6]. B に A が含まれていることは明らかですが、これらの方法のいずれも、両方が同じ正しいエンドポイントを持っていることを確認するのに役立ちませんが、Bにはそのポイントが含まれていますが、A には含まれていません。これらの方法は、この例とこの例をどのように区別するのに役立ちますか:

A = (0.5,Math.PI/6]B = [0.4,Math.PI/6) B が A を含まないことを示すために選択する必要があるポイントが 1 つだけあります。これMath.PI/6 により、そのようなアルゴリズムはほとんど不可能であると感じられます。

于 2013-07-14T13:13:02.333 に答える