алгоритм — процедура C ++ для определения, пересекаются ли два сегмента

Question

алгоритм — процедура C ++ для определения, пересекаются ли два сегмента

В последнее время я немного работаю с вычислительной геометрией и пытаюсь найти способ проверить, пересекаются ли два отрезка. Я подумал, что могу использовать направление против часовой стрелки (CCW для краткости), чтобы определить это. Вот мой код до сих пор:

struct point { double x, y };

double CCW(point a, point b, point c)
{ return (b.x-a.x)*(c.y-a.y) - (b.y-a.y)*(c.x-a.x); }

int intersect(point a, point b, point c, point d)
{ return (CCW(a,b,c)*CCW(a,b,d)<0 && CCW(c,d,b)*CCW(c,d,a)<0); }

Приведенный выше код работал для тестовых случаев, которые я ввел, и он довольно читабелен и очень прост в реализации. Но после поиска в Интернете я нашел другой способ решения проблемы пересечения отрезков. Код похож на мой, но у него есть еще if заявления, которые моя реализация опускает. Вот код:

struct line { point s, e; };

int middle(int a, int b, int c) {
int t;
if ( a > b ) {
t = a;
a = b;
b = t;
}
if ( a <= c && c <= b ) return 1;
return 0;
}

int intersect(line a, line b) {
if ( ( CCW(a.s, a.e, b.s) * CCW(a.s, a.e, b.e) < 0 ) &&
( CCW(b.s, b.e, a.s) * CCW(b.s, b.e, a.e) < 0 ) ) return 1;

if ( CCW(a.s, a.e, b.s) == 0 && middle(a.s.x, a.e.x, b.s.x) && middle(a.s.y, a.e.y, b.s.y) ) return 1;
if ( CCW(a.s, a.e, b.e) == 0 && middle(a.s.x, a.e.x, b.e.x) && middle(a.s.y, a.e.y, b.e.y) ) return 1;
if ( CCW(b.s, b.e, a.s) == 0 && middle(b.s.x, b.e.x, a.s.x) && middle(b.s.y, b.e.y, a.s.y) ) return 1;
if ( CCW(b.s, b.e, a.e) == 0 && middle(b.s.x, b.e.x, a.e.x) && middle(b.s.y, b.e.y, a.e.y) ) return 1;

return 0;
}

Может ли кто-нибудь объяснить, в чем разница между двумя реализациями, а какая безопаснее? Заранее спасибо.

6

algorithm c++computational-geometry geometry segments

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Функция, которую вы нашли, также проверяет случай, когда отрезки находятся внутри одной и той же линии. В этом случае становится одномерной задачей выяснить, перекрываются ли два отрезка. В этом случае ваш код вернет false. Является ли это предпочтительным или нет, зависит от приложения.

Пример:

point a={1,0}, b={3,0}, c={2,0}, d={4,0};

intersect(a,b,c,d); // your function will return false,
// but the one you found will return true

Функция, которую вы нашли, также рассматривает случаи, когда конечная точка одного отрезка находится вдоль другого отрезка:

Пример:

point a={1,0}, b={3,0}, c={2,0}, d={2,3};

intersect(a,b,c,d); // your function will return false,
// but the one you found will return true

3