1.2.3

1.2.3 #

解答 #

首先先实现一个 Interval2D 类(位于 Geometry 库),再使用窗体应用程序绘图。

JAVA 版本参考:http://algs4.cs.princeton.edu/12oop/Interval2D.java.html

代码 #

Interval2D: #

/// <summary>
/// 二维闭合区间。
/// </summary>
public class Interval2D
{
    private readonly Interval1D _x;
    private readonly Interval1D _y;

    /// <summary>
    /// 构造函数。
    /// </summary>
    /// <param name="x">x 轴上的范围。</param>
    /// <param name="y">y 轴上的范围。</param>
    public Interval2D(Interval1D x, Interval1D y)
    {
        _x = x;
        _y = y;
    }

    /// <summary>
    /// 判断两个平面是否相交。
    /// </summary>
    /// <param name="that">需要判断的另一个平面。</param>
    /// <returns>相交则返回 <c>true</c>,否则返回 <c>false</c>。</returns>
    public bool Intersects(Interval2D that)
    {
        if (!_x.Intersect(that._x))
        {
            return false;
        }

        if (!_y.Intersect(that._y))
        {
            return false;
        }

        return true;
    }

    /// <summary>
    /// 判断目标区间是否被本区间包含。
    /// </summary>
    /// <param name="that">需要判断是否被包含的区间。</param>
    /// <returns>如果 <paramref name="that"/> 被包含,则返回 <c>true</c>,否则返回 <c>false</c>。</returns>
    public bool Contains(Interval2D that)
    {
        return _x.Contains(that._x) && _y.Contains(that._y);
    }

    /// <summary>
    /// 判断一个二维点是否在该平面范围内。
    /// </summary>
    /// <param name="p">需要判断的二维点。</param>
    /// <returns>如果 <paramref name="p"/> 被包含,则返回 <c>true</c>,否则 <c>false</c>。</returns>
    public bool Contains(Point2D p)
    {
        return (_x.Contains(p.X) && _y.Contains(p.Y));
    }

    /// <summary>
    /// 计算平面范围的面积。
    /// </summary>
    /// <returns>平面范围的面积。</returns>
    public double Area()
    {
        return _x.Length() * _y.Length();
    }

    /// <summary>
    /// 在画布上绘制二维区间。
    /// </summary>
    /// <param name="g">原点在左下方,x轴向右,y轴向上的画布。</param>
    public void Draw(Graphics g)
    {
        var rect = new Rectangle((int)_x.Min, (int)_y.Min, (int)_x.Length(), (int)_y.Length());
        g.DrawRectangle(Pens.White, rect);
        g.FillRectangle(Brushes.Black, rect);
    }

    /// <summary>
    /// 返回形如“[xmin, xmax] x [ymin, ymax]”的字符串。
    /// </summary>
    /// <returns>形如 "[xmin, xmax] x [ymin, ymax]" 的字符串。</returns>
    public override string ToString()
    {
        return _x + "x" + _y;
    }

    /// <summary>
    /// 判断两个二维区间是否相等。
    /// </summary>
    /// <param name="obj">需要比较的另一个区间。</param>
    /// <returns>相等则返回 <c>true</c>,否则返回 <c>false</c>。</returns>
    public override bool Equals(object obj)
    {
        if (obj == this)
        {
            return true;
        }
        if (obj  == null)
        {
            return false;
        }

        if (obj.GetType() != GetType())
        {
            return false;
        }

        var that = (Interval2D)obj;

        return _x.Equals(that._x) && _y.Equals(that._y);
    }

    /// <summary>
    /// 获取哈希值
    /// </summary>
    /// <returns>2D 区间的哈希值。</returns>
    public override int GetHashCode()
    {
        var hash1 = _x.GetHashCode();
        var hash2 = _y.GetHashCode();

        return 31 * hash1 + hash2;
    }
}

绘图方法 #

/// <summary>
/// 主绘图函数。
/// </summary>
/// <param name="N">2D 间隔的数目。</param>
/// <param name="Min">分布范围的下界。(大于 0 且小于 1)</param>
/// <param name="Max">分布范围的上界。(大于 0 且小于 1)</param>
public static void StartDrawing(int N, double Min, double Max)
{
    Interval2D[] list = new Interval2D[N];
    Random random = new Random();

    //开始绘图
    Form2 drawPad = new Form2();
    drawPad.Show();
    Graphics graphics = drawPad.CreateGraphics();

    //生成随机二维间隔
    for (int i = 0; i < N; ++i)
    {
        double x = random.NextDouble() * (Max - Min) + Min;
        double y = random.NextDouble() * (Max - Min) + Min;
        if (x >= y)
        {
            double temp = x;
            x = y;
            y = temp;
        }
        x *= drawPad.ClientRectangle.Width;
        y *= drawPad.ClientRectangle.Width;
        Interval1D tempx = new Interval1D(x, y);

        x = random.NextDouble() * (Max - Min) + Min;
        y = random.NextDouble() * (Max - Min) + Min;
        if (x >= y)
        {
            double temp = x;
            x = y;
            y = temp;
        }
        x *= drawPad.ClientRectangle.Height;
        y *= drawPad.ClientRectangle.Height;
        Interval1D tempy = new Interval1D(x, y);

        list[i] = new Interval2D(tempx, tempy);
    }

    //计算相交和包含的数量
    int intersectNum = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = i + 1; j < N; ++j)
        {
            if (list[i].Intersects(list[j]))
            {
                intersectNum++;
            }
        }
    }

    int containsNum = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (i == j)
                continue;

            if (list[i].Contains(list[j]))
            {
                containsNum++;
            }
        }
    }

    //移动原点至左下方,翻转坐标系
    graphics.TranslateTransform(0, drawPad.ClientRectangle.Height);
    graphics.ScaleTransform(1, -1);

    //绘制所有区间
    foreach (Interval2D n in list)
    {
        n.Draw(graphics);
    }

    //新建一个窗口,显示计算结果
    MessageBox.Show($"相交的区间数:{intersectNum}, 包含的区间数:{containsNum}");

    //清理资源
    graphics.Dispose();
}

另请参阅 #

Geometry 库