Узнайте, пересекаются ли 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 <stdarg.h>
template<typename VType, unsigned int dim>
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<dim; ++i){
data[i] = va_arg(l, VType);
}
va_end(l);
}
~vec(){}
VType& operator[](unsigned int i){
return data[i];
}
VType operator[](unsigned int i) const {
return data[i];
}};
template<typename VType, unsigned int dim, bool doDiv>
vec<VType, dim> helpArith1(const vec<VType, dim>& A, long delta){
vec<VType, dim> r(A);
for(unsigned int i=0; i<dim; ++i){
r[i] = doDiv ? (r[i] / delta) : (r[i] * delta);
}
return r;
}
template<typename VType, unsigned int dim>
vec<VType, dim> operator*(const vec<VType, dim>& v, long delta) {
return helpArith1<VType, dim, false>(A, delta);
}
template<typename VType, unsigned int dim>
vec<VType, dim> operator*(long delta, const vec<VType, dim>& v){
return v * delta;
}
template<typename VType,unsigned int dim>
vec<VType, dim> operator/(const vec<VType, dim>& A, long delta) {
return helpArith1<VType, dim, true>(A, delta);
}
template<typename VType, unsigned int dim, bool doSub>
vec<VType, dim> helpArith2(const vec<VType, dim>& A, const vec<VType, dim>& B){
vec<VType, dim> r;
for(unsigned int i=0; i<dim; ++i){
r[i] = doSub ? (A[i]-B[i]):(A[i]+B[i]);
}
return r;
}
template<typename VType, unsigned int dim>
vec<VType, dim> operator+(const vec<VType, dim>& A, const vec<VType, dim>& B){
return helpArith2<VType, dim, false>(A, B);
}
template<typename VType, unsigned int dim>
vec<VType, dim> operator-(const vec<VType, dim>& A, const vec<VType, dim>& B){
return helpArith2<VType, dim, true>(A, B);
}
template<typename VType, unsigned int dim>
bool operator==(const vec<VType, dim>& A, const vec<VType, dim>& B) {
for(unsigned int i==0; i<dim; ++i){
if(A[i]!=B[i]){
return false;
}
}
return true;
}
template<typename VType, unsigned int dim>
bool operator!=(const vec<VType, dim>& A, const vec<VType, dim>& B) {
return !(A==B);
}
#endif
line.h:
#ifndef __MY_LINE__
#define __MY_LINE__
#include "vec.h"unsigned long int ggt(unsigned long int A, unsigned long int B) {
if(A==0) {
if(B==0) {
return 1;
}
return B;
}
while(B!=0) {
unsigned long int temp = A % B;
A = B;
B = temp;
}
return A;
}
#define ABS(n) ( ((n)<0) ? (-n) : (n) )
struct line {
vec<long int, 2> A, B;
explicit line(long int iA_0, long int iA_1, long int iB_0, long int iB_1) :
A(vec<long int, 2>(iA_0<<8, iA_1<<8)),
B(vec<long int, 2>(iB_0<<8, iB_1<<8)){}
vec<long int, 2> slope() const{
vec<long int, 2> temp = A-B;
if(temp[0]<0) {
temp[0] = -1 * temp[0];
temp[1] = -1 * temp[1];
}
return temp/ggt(ABS(temp[0]), ABS(temp[1]));
}
};
bool intersect(line l1, line l2) {
const long int epsilon = 1<<4;
vec<long int, 2> sl1 = l1.slope(), sl2 = l2.slope();
// l2.A + b*sl2 = l1.A + a*sl1
// <=> l2.A - l1.A = a*sl1 - b*sl2 // = (I, II)^T
// I': sl2[1] * I; II': sl2[0] * II
vec<long int, 2> L = l2.A - l1.A, R = sl1;
L[0] = L[0] * sl2[1]; R[0] = R[0] * sl2[1];
L[1] = L[1] * sl2[0]; R[1] = R[1] * sl2[0];
// I' - II'
long int L_SUB = L[0] - L[1], R_SUB = R[0] - R[1];
if(ABS(R_SUB) == 0) {
return ABS(L_SUB) == 0;
}
long int temp = ggt(ABS(L_SUB), ABS(R_SUB));
L_SUB /= temp; R_SUB /= temp;
// R_SUB * a = L_SUB
long int a = L_SUB/R_SUB, b = ((l1.A[0] - l2.A[0])*R_SUB + L_SUB * sl1[0])/R_SUB;
// if the given lines intersect, then {a, b} must be the solution of
// l2.A - l1.A = a*sl1 - b*sl2
L = l2.A - l1.A;
long x = ABS((L[0]- (a*sl1[0]-b*sl2[0]))), y = ABS((L[1]- (a*sl1[1]-b*sl2[1])));
return x<epsilon && y < epsilon;
}
#endif
main.cpp:
#include "line.h"int main(){
line A(0, 0, 6, 0), B(3, 3, 4, -3);
bool temp = intersect(A, B);
return 0;
}
(Я не уверен, что моя функция пересечения работает для всех линий, но с тестовыми данными, которые я использовал до сих пор, она вернулась с правильным результатом.)
Решение
Это возможно. Мы хотим проверить, находятся ли обе конечные точки l1 на разных сторонах l2, и обе конечные точки l2 находятся на противоположных сторонах l1.
Чтобы проверить, на какой стороне l1 = ((A0, B0), (A1, B1)) лежит точка (A, B), мы берем:
- произвольный вектор нормали N, перпендикулярный прямой; один такой вектор (B1-B0, A1-A0)
- вектор P от начала линии до точки (A, B), которая является (A-A0, B-B0)
Затем мы вычисляем скалярное произведение:
N · P = (A-A0, B-B0) · (B1-B0, A1-A0) = (A-A0) * (B1-B0) + (B-B0) * (A1-A0)
Нас интересует только знак: если он положительный, точка находится на одной стороне линии; если это отрицательно, это с другой стороны. Как видите, арифметика с плавающей запятой не требуется.
Мы можем воспользоваться тем, что числа с противоположными знаками при умножении всегда дают отрицательный результат. Таким образом, полное выражение для определения того, пересекаются ли два отрезка ((A0, B0), (A1, B1)) и ((A2, B2), (A3, B3)):
((A2-A0)*(B1-B0) - (B2-B0)*(A1-A0)) * ((A3-A0)*(B1-B0) - (B3-B0)*(A1-A0)) < 0
&&
((A0-A2)*(B3-B2) - (B0-B2)*(A3-A2)) * ((A1-A2)*(B3-B2) - (B1-B2)*(A3-A2)) < 0
Тестовый код
Некоторый код C ++ для проверки приведенного выше расчета:
#include <iostream>
#include <cstdlib>
struct Point {
int x,y;
};
bool isIntersecting(Point& p1, Point& p2, Point& q1, Point& q2) {
return (((q1.x-p1.x)*(p2.y-p1.y) - (q1.y-p1.y)*(p2.x-p1.x))
* ((q2.x-p1.x)*(p2.y-p1.y) - (q2.y-p1.y)*(p2.x-p1.x)) < 0)
&&
(((p1.x-q1.x)*(q2.y-q1.y) - (p1.y-q1.y)*(q2.x-q1.x))
* ((p2.x-q1.x)*(q2.y-q1.y) - (p2.y-q1.y)*(q2.x-q1.x)) < 0);
}
int main(int argc, char* argv[]) {
if(argc != 9) {
std::cout << "Call as " << argv[0] << " <p1.x> <p1.y> <p2.x> "<< "<p2.y> <q1.x> <q1.y> <q2.x> <q2.y>" << std::endl;
return -1;
}
Point p1 = {.x = atoi(argv[1]), .y = atoi(argv[2])};
Point p2 = {.x = atoi(argv[3]), .y = atoi(argv[4])};
Point q1 = {.x = atoi(argv[5]), .y = atoi(argv[6])};
Point q2 = {.x = atoi(argv[7]), .y = atoi(argv[8])};
if(isIntersecting(p1,p2,q1,q2)) {
std::cout << "Segments intersect" << std::endl;
return 1;
}
else {
std::cout << "Segments do not intersect" << std::endl;
return 0;
}
}
Результаты:
$ ./intersection_test 0 0 10 10 0 10 10 0 # example from the comments
Segments intersect
$ ./intersection_test 0 1 2 1 1 2 1 0
Segments intersect
$ ./intersection_test 0 0 0 1 1 1 1 0
Segments do not intersect
$ ./intersection_test 1 1 5 3 3 4 7 2 # q touches but not intersects at p2
Segments do not intersect
$ ./intersection_test 1 1 5 3 3 4 6 2
Segments intersect
Другие решения
Два отрезка линии пересекаются, если их линии пересекаются, а конечные точки каждого отрезка находятся на противоположных сторонах линии других отрезков. По крайней мере, в 2d.
Пересечение двух линий — простой вопрос в 2d.
На какой стороне линии находится точка, тоже легко.
Ни один не требует целочисленной математики.
Я бы оценил дюжину или три строки для некоторого общего кода геометрии, а затем решение для 6-10 строк? Плюс языковой шаблон. И некоторые проверки угловых случаев нулевой длины.
Обратите внимание, я отличаю линии от сегментов.