Расширение отрезка для размещения в ограничительной рамке

Question

У меня есть отрезок, определяемый двумя pointF s, вместе с двухмерным ограничительным прямоугольником. Я хочу максимально расширить линейный сегмент в обоих направлениях, чтобы сегмент находился на одном уровне со стенками ограничительной рамки. Вот несколько примеров того, что я пытаюсь сделать:

У кого-нибудь есть предложения, как это сделать?

Answer 1

Определить прямоугольник как четыре линии.

Найдите пересечение между вашей линией и каждой из четырех линий. (Как твоя геометрия в старшей школе?)

Из этих четырех точек пересечения определить, какие точки находятся в пределах прямоугольника. (найдите точки пересечения, в которых значения x и y находятся в пределах диапазона прямоугольников).

Ваш алгоритм также должен учитывать следующие крайние случаи:

• Линия параллельна вертикали горизонтального края прямоугольника
• Линия фактически пересекается с углом прямоугольника.

Answer 2

Вот пример кода на python:

def extend(xmin, ymin, xmax, ymax, x1, y1, x2, y2):
    if y1 == y2:
        return (xmin, y1, xmax, y1)
    if x1 == x2:
        return (x1, ymin, x1, ymax)

    # based on (y - y1) / (x - x1) == (y2 - y1) / (x2 - x1)
    # => (y - y1) * (x2 - x1) == (y2 - y1) * (x - x1)
    y_for_xmin = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1)
    y_for_xmax = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1)

    x_for_ymin = x1 + (x2 - x1) * (ymin - y1) / (y2 - y1)
    x_for_ymax = x1 + (x2 - x1) * (ymax - y1) / (y2 - y1)

    if ymin <= y_for_xmin <= ymax:
        if xmin <= x_for_ymax <= xmax:
            return (xmin, y_for_xmin, x_for_ymax, ymax)
        if xmin <= x_for_ymin <= xmax:
            return (xmin, y_for_xmin, x_for_ymin, ymin)
    if ymin <= y_for_xmax <= ymax:
        if xmin <= x_for_ymin <= xmax:
            return (x_for_ymin, ymin, xmax, y_for_xmax)
        if xmin <= x_for_ymax <= xmax:
            return (x_for_ymax, ymax, xmax, y_for_xmax)

def test():
    assert (2, 1,  2, 5) == extend(1, 1,  5, 5,  2, 3,  2, 4)
    assert (1, 2,  4, 5) == extend(1, 1,  5, 5,  2, 3,  3, 4)
    assert (1, 3,  5, 3) == extend(1, 1,  5, 5,  3, 3,  4, 3)
    assert (1, 1,  5, 5) == extend(1, 1,  5, 5,  2, 2,  3, 3)
    assert (3, 1,  5, 5) == extend(1, 1,  5, 5,  3.5, 2,  4, 3)

if __name__ == '__main__':
    test()

Он не проверяет, содержится ли сегмент в прямоугольнике, и должен работать также, если он находится вне его (возвращает None -implicit-, если нет фактического пересечения сегмента).

Он основан на предположении, что прямоугольник имеет сегменты, параллельные осям.

Answer 3

Одним из вариантов будет определение параметрического представления отрезка линии, варьирующегося по некоторой переменной t, затем определение четырех линейных уравнений, определяющих линии на боковой стороне прямоугольника (растянутые бесконечно во всех направлениях). Идея состоит в том, что когда вы проверяете, где сегмент попадает в эти линии , для каждого направления, в котором вы можете расширить сегмент, вы получите две точки пересечения - одну для горизонтального пересечения и одну для вертикального пересечения. Все, что находится внутри коробки, будет тем, которое вы хотите выбрать.

Для этого вычислите значения параметра t линии, образованной путем расширения сегмента в каждом направлении, где вы попадаете в одну из четырех ограничивающих линий. Я предполагаю, что отрезок линии параметризован так, что t & in; [0, 1]. Затем вы получите (до) четырех значений t, соответствующих параметрам, где линия пересекает ограничивающий прямоугольник - два значения & ge; 1 представляет продолжение линии в одном направлении и два значения & le; 0 представляет расширение линии в другом направлении. Из этих четырех значений вы хотите выбрать значение t & ge; 1 это наименьшее значение t & ge; 0 это наибольшее значение (они представляют параметры линии, которые проходят кратчайшее расстояние в каждом направлении до удара о стену). Когда у вас есть эти два параметра, вставьте значения t обратно в исходную параметризацию, чтобы получить две точки пересечения, которые вы хотите со стенами, а затем определите новый отрезок прямой, который простирается от первого из них до второго.

Обратите внимание, что этот алгоритм в более общем смысле можно использовать для расширения отрезка, чтобы заполнить границы любого выпуклого многоугольника, включая прямоугольники, которые не выровнены по оси. Вам никогда не нужно проверять, содержатся ли какие-либо из найденных вами точек в ограничительной рамке; Вы просто смотрите на значение параметра t, чтобы увидеть, какие из точек пересечения находятся ближе к конечным точкам вашего сегмента.

Надеюсь, это поможет!

Answer 4

Улучшен код андредора - добавлены случаи, когда линия пересекается с верхним и нижним или левым и правым краями. Предоставленный код предназначен для обработки для проверки алгоритма. Первая точка задается щелчком мыши, а вторая точка постоянно обновляется с текущей позицией указателя мыши.

int px = 100, py = 100;

void setup() {
  size(480, 640);
  background(102);
}

void draw() {
  stroke(255);
  rect(0, 0, 480, 640);
  stroke(100);

  if (mousePressed == true) {
    px = mouseX;
    py = mouseY;
  }
  extendLine(0, 0, 480, 640, px, py, mouseX, mouseY);
}

void extendLine(int xmin, int ymin, int xmax, int ymax, int x1, int y1, int x2, int y2) {
    if (y1 == y2) {
        line(xmin, y1, xmax, y1);
        return;
    }
    if(x1 == x2) {
        line(x1, ymin, x1, ymax);
        return;
    }

    int y_for_xmin = y1 + (y2 - y1) * (xmin - x1) / (x2 - x1);
    int y_for_xmax = y1 + (y2 - y1) * (xmax - x1) / (x2 - x1);

    int x_for_ymin = x1 + (x2 - x1) * (ymin - y1) / (y2 - y1);
    int x_for_ymax = x1 + (x2 - x1) * (ymax - y1) / (y2 - y1);

    if (ymin <= y_for_xmin && y_for_xmin <= ymax
     && ymin <= y_for_xmax && y_for_xmax <= ymax) {
       line(xmin, y_for_xmin, xmax, y_for_xmax);
       return;
    } else if (ymin <= y_for_xmin && y_for_xmin <= ymax) {
        if (xmin <= x_for_ymax && x_for_ymax <= xmax) {
            line(xmin, y_for_xmin, x_for_ymax, ymax);
            return;
        }
        else if(xmin <= x_for_ymin && x_for_ymin <= xmax) {
            line(xmin, y_for_xmin, x_for_ymin, ymin);
            return;
        }
    } else if (ymin <= y_for_xmax && y_for_xmax <= ymax){
        if (xmin <= x_for_ymin && x_for_ymin <= xmax){
            line(x_for_ymin, ymin, xmax, y_for_xmax);
            return;
        }
        if(xmin <= x_for_ymax && x_for_ymax <= xmax){
            line(x_for_ymax, ymax, xmax, y_for_xmax);
            return;
        }
    } else if (xmin <= x_for_ymin && x_for_ymin <= xmax
     && xmin <= x_for_ymax && x_for_ymax <= xmax) { 
         line(x_for_ymin, ymin, x_for_ymax, ymax);
         return;
    }
}