Проверить пересекаются ли отрезки, что я делаю не так?

Question

[Biaci_Anj]

Программа должна определять, где пресекаются отрезки, если не пресекаются, то возвращать null.
К сожалению, метод не работает с некоторыми отрезками, например с тем, что сейчас указан в ней.
Буду очень благодарен, если поможете понять, как нужно отредактировать условие.
Point intersection() {
double x1 = 0; // first line start
double y1 = 0;

double x2 = 1; // first line end
double y2 = 1;

double x3 = -1; // second line start
double y3 =-1;

double x4 = -2; // second line end
double y4 = 2;

if (x1 >= x2) {
double temp;
temp = x1;
x1 = x2;
x2 = temp;

temp = y1;
y1 = y2;
y2 = temp;
}
if (x3 >= x4) {
double temp;
temp = x3;
x3 = x4;
x4 = temp;

temp = y3;
y3 = y4;
y4 = temp;
}

double k1;
if (y2 == y1) k1 = 0;
else {
k1 = (y2-y1) / (x2-x1);
}
double k2;
if (y3 == y4) k2 = 0;
else {
k2 = (y4 - y3) / (x4 - x3);
}
if (k1 == k2) return null; // параллельные

double b1 = y1 - k1 * x1;
double b2 = y3 - k2 * x3;

if (b1 == b2) return new Point(0, b1);
double leftPart = k1 + -k2;
double rightPart = b2 + -b1;
double x = rightPart / leftPart;
double y = k1 * x + b1;

return new Point(x, y);
}

Еще один пример отрезка, который выдает неправильный результат:
Начало x 0, y 3
Конец x 4, y 0

И
Начало x -1. y -3
Конец х 1, y 1

Comments

[Николай Савельев]

отредактируй код тэгом. невозможно читать

[User700]

Во-первых, отрезки или прямые?

Answer 1

[AlexHell]

В википедии есть формула и пояснения https://en.wikipedia.org/wiki/Intersection_(Euclid...

а по вашему коду точно не разбирал

вкратце как надо:
* создаются уравнения прямых через 2 точки
* проверяются пересечения двух уравнений прямых - есть ли точка пересечения (может не быть)
* проверяется принадлежность точки пересечения каждому отрезку (или явно или лучше параметрически) (может быть в уравнении но не в диапазоне отрезка)

однако так делать нельзя изза погрешности double if (y2 == y1) k1 = 0; обычно проверяют через if(Abs(y2 - y1) < epsilon) (скажем 0.0001 но зависит от задач)