Перейти к основному содержимому

Найдите пересечение двух линий в Java

· 3 мин. чтения

Задача: Наибольшая подстрока без повторений

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

ANDROMEDA 42

1. Обзор​

В этом кратком руководстве мы покажем, как найти точку пересечения двух линий, определенных линейными функциями в форме пересечения наклона.

2. Математическая формула пересечения​

Любая прямая линия (кроме вертикальной) на плоскости может быть задана линейной функцией:

y = mx + b

где m — наклон, а b — точка пересечения с осью y.

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

Допустим, у нас есть две линии. Первая функция определяет первую строку:

y = m1x + b1

И вторая функция определяет вторую строку:

y = m2x + b2

./36055d20682141f4adf58c682a682ad8.png

Мы хотим найти точку пересечения этих линий. Очевидно, что для точки пересечения верно равенство:

y1 = y2

Заменим переменные y : 

m1x + b1 = m2x + b2

Из приведенного выше уравнения мы можем найти координату x : 

x(m1 - m2) = b2 - b1
x = (b2 - b1) / (m1 - m2)

Наконец, мы можем найти y-координату точки пересечения:

y = m1x + b1

Теперь перейдем к части реализации.

3. Реализация Java​

Во- первых, у нас есть четыре входных переменных — m1, b1 для первой строки и m2, b2 для второй строки.

Во-вторых, мы преобразуем рассчитанную точку пересечения в объект типа java.awt.Point .

Наконец, линии могут быть параллельными, поэтому давайте сделаем возвращаемое значение Optional<Point> :

public Optional<Point> calculateIntersectionPoint(
    double m1, 
    double b1, 
    double m2, 
    double b2) {

    if (m1 == m2) {
        return Optional.empty();
    }

    double x = (b2 - b1) / (m1 - m2);
    double y = m1 * x + b1;

    Point point = new Point();
    point.setLocation(x, y);
    return Optional.of(point);
}

Теперь давайте выберем некоторые значения и протестируем метод для параллельных и непараллельных линий.

Например, возьмем ось x ( y = 0 ) в качестве первой линии, а линию, определяемую y = x – 1 , в качестве второй линии.

Для второй линии наклон m равен 1 , что означает 45 градусов, а точка пересечения y равна -1 , что означает, что линия пересекает ось y в точке (0, -1).

Интуитивно понятно, что точка пересечения второй линии с осью x должна быть (1,0 ):

./911a710cddbab9dbeb25723fb0c451e1.png

Давайте проверим это.

Во-первых, давайте удостоверимся, что Point присутствует, так как линии не параллельны, а затем проверим значения x и y :

@Test
public void givenNotParallelLines_whenCalculatePoint_thenPresent() {
    double m1 = 0;
    double b1 = 0;
    double m2 = 1;
    double b2 = -1;

    Optional<Point> point = service.calculateIntersectionPoint(m1, b1, m2, b2);

    assertTrue(point.isPresent());
    assertEquals(point.get().getX(), 1, 0.001);
    assertEquals(point.get().getY(), 0, 0.001);
}

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

./ee475e7f321c8f5b9a22732b348701bf.png

@Test
public void givenParallelLines_whenCalculatePoint_thenEmpty() {
    double m1 = 1;
    double b1 = 0;
    double m2 = 1;
    double b2 = -1;

    Optional<Point> point = service.calculateIntersectionPoint(m1, b1, m2, b2);

    assertFalse(point.isPresent());
}

4. Вывод​

В этом уроке мы показали, как вычислить точку пересечения двух линий.

Как обычно, полный исходный код доступен на GitHub .