Разделение двух квадратов пополам на декартовой плоскости (нахождение середины)

Я работаю над решением следующей проблемы:

Даны два квадрата на двумерной плоскости, найдите линию, которая разрезала бы эти два квадрата пополам. Предположим, что верхняя и нижняя стороны квадрата параллельны оси x.

Это решение в книге:

public class Square {
    public double left;
    public double top;
    public double bottom;
    public double right;
    public double size;
    public Square(double left, double top, double size) {
        this.left = left;
        this.top = top;
        this.bottom = top + size;
        this.right = left + size;
        this.size = size;
    }

    public Point middle() {
        return new Point((this.left + this.right)/2.0, (this.top + this.bottom)/2.0);
    }

    public boolean contains(Square other) {
        if (this.left <= other.left && this.right >= other.right && this.top <= other.top && this.bottom >= other.bottom) {
            return true;
        }
        return false;
    }

    /* Return the point where the line segment connecting mid1 and
     * mid2 intercepts the edge of square 1. That is, draw a line 
     * from mid2 to mid1, and continue it out until the edge of
     * the square. */
    public Point extend(Point mid1, Point mid2, double size) {
        /* Find what direction the line mid2 -> mid1 goes */
        double xdir = mid1.x < mid2.x ? -1 : 1;
        double ydir = mid1.y < mid2.y ? -1 : 1;

        /* If mid1 and mid2 have the same x value, then the slope
         * calculation will throw a divide by 0 exception. So, we
         * compute this specially. */
        if (mid1.x == mid2.x) {
            return new Point(mid1.x, mid1.y + ydir * size / 2.0);
        }
        double slope = (mid1.y - mid2.y) / (mid1.x - mid2.x);
        double x1 = 0;
        double y1 = 0;

        /* Calculate slope using the equation (y1 - y2) / (x1 - x2).
         * Note: if the slope is “steep” (>1) then the end of the
         * line segment will hit size / 2 units away from the middle
         * on the y axis. If the slope is “shallow” (<1) the end of
         * the line segment will hit size / 2 units away from the
         * middle on the x axis. */
        if (Math.abs(slope) == 1) {
            x1 = mid1.x + xdir * size / 2.0;
            y1 = mid1.y + ydir * size / 2.0;
        } else if (Math.abs(slope) < 1) {
            x1 = mid1.x + xdir * size / 2.0;
            y1 = slope * (x1 - mid1.x) + mid1.y; 
        } else {
            y1 = mid1.y + ydir * size / 2.0;
            x1 = (y1 - mid1.y) / slope + mid1.x;
        }
        return new Point(x1, y1);
    }

    public Line cut(Square other) {
        /* Calculate where a line between each middle would collide with the edges of the squares */
        Point p1 = extend(this.middle(), other.middle(), this.size);
        Point p2 = extend(this.middle(), other.middle(), -1 * this.size);
        Point p3 = extend(other.middle(), this.middle(), other.size);
        Point p4 = extend(other.middle(), this.middle(), -1 * other.size);

        /* Of above points, find start and end of lines. Start is farthest left (with top most as a tie breaker)
         * and end is farthest right (with bottom most as a tie breaker */
        Point start = p1;
        Point end = p1;     
        Point[] points = {p2, p3, p4};
        for (int i = 0; i < points.length; i++) {
            if (points[i].x < start.x || (points[i].x == start.x && points[i].y < start.y)) {
                start = points[i];
            } else if (points[i].x > end.x || (points[i].x == end.x && points[i].y > end.y)) {
                end = points[i];
            }
        }

        return new Line(start, end);
    }

    public String toString() {
        return "(" + left + ", " + top + ")|(" + right + "," + bottom + ")";
    }
}

У меня есть следующие вопросы:

  1. Что такое параметр размера в функции расширения? Размер чего? В сторону? Вся квадратная (как мы можем количественно определить размер всего квадрата?) площадь?

  2. Что в конечном итоге делают p1-p4 в функции cut()? А зачем нам 4 балла, чтобы это сделать?


person ApathyBear    schedule 06.10.2015    source источник
comment
Я даже не понимаю, что такое лево, право, низ, верх в типе данных Square. Представляет ли это точку? но как?. Это размер? но почему?   -  person abb    schedule 07.04.2020


Ответы (2)


Насколько я понимаю задачу, необходимо и достаточно, чтобы линия соединила два центра.

Предположим, что верхняя и нижняя стороны квадрата параллельны оси x.

Я не знаю, почему это предположение необходимо.

person SK9    schedule 06.10.2015
comment
Я думаю, что причина не в том, чтобы иметь бриллиант - person Jorge Campos; 06.10.2015
comment
Я понимаю, что проведение линии между двумя центрами разрежет квадраты пополам, но у меня было несколько более конкретных вопросов, на которые я надеюсь получить ответы. - person ApathyBear; 06.10.2015
comment
@ Хорхе Кампос Я думаю, что причина не в том, чтобы иметь бриллиант Опять же, я не знаю, зачем это нужно. Например, если вы возьмете среднее значение 4 углов, результатом будет центр. - person SK9; 06.10.2015

Этот ответ может не иметь отношения к TS. Но в случае, если вас также интересует этот ответ, параметр «размер» вводит в заблуждение - он относится к длине квадрата (например, квадрат 3x3 имеет длину 3). Почему четыре точки? Потому что вопрос предполагает, что линия здесь представляет две «самые дальние» точки, пересекающие два квадрата. Каждый квадрат имеет две точки, которые потенциально могут стать началом/концом линии.

person 4tee    schedule 01.11.2017