Узнайте, пересекаются ли 2 линии [дубликаты]
Возможный дубликат:
Как определить, где пересекаются два отрезка?
Определение, пересекаются ли два отрезка?
Даны две линии l1 = ((A0, B0), (A1, B1)) и l2 = ((A2, B2), (A3, B3)); Ax, Bx - целые числа, а (Ax, Bx) указывают начало и конец линий.
Существует ли алгоритм, использующий только целочисленную арифметику, которая определяет, пересекаются ли l1 и l2? (Требуется только логический ответ.)
Мой собственный подход должен был вычислить точку около точки пересечения с арифметикой с фиксированной точкой. Решение (a, b) затем было подставлено в следующие уравнения:
I: абс ((A0 + a * (A1-A0)) - (A2 + b * (A3-A2))) < толерантность
II: абс ((B0 + a * (B1-B0)) - (B2 + b * (B3-B2))) < толерантность
Мой метод должен вернуть true, если и я, и II оценивают как true.
Мой C ++ - Код:
vec.h:
#ifndef __MY_VECTOR__
#define __MY_VECTOR__
#include
template
class vec {
private:
VType data[dim];
public:
vec(){}
vec(VType v0, ...){
data[0] = v0;
va_list l;
va_start(l, v0);
for(unsigned int i=1; i