Точка в треугольнике

Question

Даны координаты вершин треугольника, координаты точки D, требуется определить и вывести положение точки D относительно треугольника.

#include <stdio.h>
 
struct point {
  double x, y;
};
 
struct triangle {
  struct point a, b, c;
};
 
int direction(struct point pt, struct point a, struct point b) {

  return ((a.x - pt.x) * (b.y - a.y) - (b.x - a.x) * (a.y - pt.y));
}
 
int is_inside(struct point pt, struct triangle tri) {
  int directions[] = {
    direction(pt, tri.a, tri.b),
    direction(pt, tri.b, tri.c),
    direction(pt, tri.c, tri.a)
  };
 #define d direction 
 return directions[0]*directions[1]>=0&&directions[0]*directions[2]>=0&&directions[1]*directions[2]>=0;
}
 
int main() {
  struct point pt;
  struct triangle tri;
 
  scanf(
    "%lf %lf %lf %lf %lf %lf %lf %lf", 
    &tri.a.x, &tri.a.y, 
    &tri.b.x, &tri.b.y, 
    &tri.c.x, &tri.c.y, 
    &pt.x, &pt.y
  );
  
  printf("%d", is_inside(pt, tri));
}

Код работает на 90%, а должен на 100. Подскажите, в чем ошибка?

Answer 1

В общем алгоритм сам правильный, но если вы уверены, что код работает не на 100 процентов правильно, значит единственное что мне в голову пришло это переполнение.

Посмотрим на строчку:

return directions[0] * directions[1] >= 0 && directions[0] * directions[2] >= 0 && directions[1] * directions[2] >= 0;

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

Так что рекомендую лучше писать вот так:

return (directions[0] >= 0 && directions[1] >= 0 && directions[2] >= 0) ||
       (directions[0] <= 0 && directions[1] <= 0 && directions[2] <= 0);

Но т.к. координаты точек это переменные типа double, то чтобы не было опять токи переполнения, нужно использовать или long long int или везде уже использовать double. Я выберу второй вариант дли примера т.к. он более точный, тем более по смыслу подходит больше, т.к. используете координаты точек типа double.

Я немного переделал вашу функцию is_inside:

int is_inside(struct point pt, struct triangle tri) {
    double eps = 1e-7;
    double dirs[] = {
      direction(pt, tri.a, tri.b),
      direction(pt, tri.b, tri.c),
      direction(pt, tri.c, tri.a)
    };
    return isValid(dirs[0], dirs[1], eps) == 1 && 
           isValid(dirs[0], dirs[2], eps) == 1 && 
           isValid(dirs[1], dirs[2], eps) == 1;
}

И добавил функцию isValid, которая проверяет является ли умножение двух double >= 0 :

int isValid(double x, double y, double eps) {
    return fabs(x * y) < eps || (x * y) > 0;
}

БЛОГ НА HUSL

Точка в треугольнике

Ответы (1 шт):