E079. Точка пересечения прямых

e-maxx algorithm original: C/C++ #algorithm #emaxx #geometry #math

Task text is translated from Russian for the selected interface language. Code is left unchanged.

Static

Источник: e-maxx.ru/algo, страница PDF 232.

Пусть нам given две прямые, заданные своими коэффициентами

и

. it is required find их

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

Solution

Если две прямые не параллельны, то они пересекаются. Чтобы find точку пересечения, достаточно составить из двух уравнений прямых систему и решить её: Пользуясь формулой Крамера, сразу находим Solution системы, которое и будет искомой точкой пересечения:

Если знаменатель нулевой, т.е. то система решений не имеет (прямые параллельны и не совпадают) или имеет бесконечно много (прямые совпадают). Если необходимо различить эти два случая, надо проверить, что коэффициенты

прямых пропорциональны с тем же коэффициентом пропорциональности, что и коэффициенты

и

, для

чего достаточно посчитать два определителя, если они оба равны нулю, то прямые совпадают:

Implementation

struct pt {

double x, y;

};

struct line {

double a, b, c;

};

const double EPS = 1e-9;

double det (double a, double b, double c, double d) {

return a * d - b * c;

}

bool intersect (line m, line n, pt & res) {

double zn = det (m.a, m.b, n.a, n.b);

if (abs (zn) < EPS)

return false;

res.x = - det (m.c, m.b, n.c, n.b) / zn;

res.y = - det (m.a, m.c, n.a, n.c) / zn;

return true;

}

bool parallel (line m, line n) {

return abs (det (m.a, m.b, n.a, n.b)) < EPS;

}

bool equivalent (line m, line n) {

return abs (det (m.a, m.b, n.a, n.b)) < EPS

&& abs (det (m.a, m.c, n.a, n.c)) < EPS

&& abs (det (m.b, m.c, n.b, n.c)) < EPS;

}

C# solution

auto-draft, review before submit

using System;
using System.Collections.Generic;
using System.Linq;

public static class AlgorithmDraft
{
    // Auto-generated C# draft from the original e-maxx C/C++ listing. Review before production use.
    struct pt {
            double x, y;
    };
    struct line {
            double a, b, c;
    };
    const double EPS = 1e-9;
    double det (double a, double b, double c, double d) {
            return a * d - b * c;
    }
    bool intersect (line m, line n, pt & res) {
            double zn = det (m.a, m.b, n.a, n.b);
            if (abs (zn) < EPS)
                    return false;
            res.x = - det (m.c, m.b, n.c, n.b) / zn;
            res.y = - det (m.a, m.c, n.a, n.c) / zn;
            return true;
    }
    bool parallel (line m, line n) {
            return abs (det (m.a, m.b, n.a, n.b)) < EPS;
    }
    bool equivalent (line m, line n) {
            return abs (det (m.a, m.b, n.a, n.b)) < EPS
                    && abs (det (m.a, m.c, n.a, n.c)) < EPS
                    && abs (det (m.b, m.c, n.b, n.c)) < EPS;
    }
}

C++ solution

matched/original

struct pt {
        double x, y;
};
struct line {
        double a, b, c;
};
const double EPS = 1e-9;
double det (double a, double b, double c, double d) {
        return a * d - b * c;
}
bool intersect (line m, line n, pt & res) {
        double zn = det (m.a, m.b, n.a, n.b);
        if (abs (zn) < EPS)
                return false;
        res.x = - det (m.c, m.b, n.c, n.b) / zn;
        res.y = - det (m.a, m.c, n.a, n.c) / zn;
        return true;
}
bool parallel (line m, line n) {
        return abs (det (m.a, m.b, n.a, n.b)) < EPS;
}
bool equivalent (line m, line n) {
        return abs (det (m.a, m.b, n.a, n.b)) < EPS
                && abs (det (m.a, m.c, n.a, n.c)) < EPS
                && abs (det (m.b, m.c, n.b, n.c)) < EPS;
}

Java solution

auto-draft, review before submit

import java.util.*;
import java.math.*;

public class AlgorithmDraft {
    // Auto-generated Java draft from the original e-maxx C/C++ listing. Review before production use.
    struct pt {
            double x, y;
    };
    struct line {
            double a, b, c;
    };
    const double EPS = 1e-9;
    double det (double a, double b, double c, double d) {
            return a * d - b * c;
    }
    boolean intersect (line m, line n, pt & res) {
            double zn = det (m.a, m.b, n.a, n.b);
            if (abs (zn) < EPS)
                    return false;
            res.x = - det (m.c, m.b, n.c, n.b) / zn;
            res.y = - det (m.a, m.c, n.a, n.c) / zn;
            return true;
    }
    boolean parallel (line m, line n) {
            return abs (det (m.a, m.b, n.a, n.b)) < EPS;
    }
    boolean equivalent (line m, line n) {
            return abs (det (m.a, m.b, n.a, n.b)) < EPS
                    && abs (det (m.a, m.c, n.a, n.c)) < EPS
                    && abs (det (m.b, m.c, n.b, n.c)) < EPS;
    }
}

Материал разбит как Algorithmическая Task: изучить постановку, понять асимптотику и реализовать Algorithm на выбранном языке.

Vacancies for this task

Active vacancies with overlapping task tags are shown.

All vacancies

There are no active vacancies yet.