C-检查多边形是否为凸

Question

我需要检查多边形是否为凸我知道这里有问题，但是我需要检查代码，是否正确

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int check_figure(float* x_points[], float* y_points[]);
int main(void) {
  int n;
  scanf("%i", &n);
  int i = 0;
  float **x_points = NULL, **y_points = NULL;
  x_points = (float**) malloc(sizeof(float*) * (n + 1));
  if (x_points == NULL) {
    return 0;
  }
  y_points = (float**) malloc(sizeof(float*) * (n + 1));
  if (y_points == NULL) {
    return 0;
  }
  for (i = 0; i < n; i++) {
    x_points[i] = (float*) malloc((n + 1) * sizeof(float));
    scanf("%f", x_points[i]);
    y_points[i] = (float*) malloc((n + 1) * sizeof(float));
    scanf("%f", y_points[i]);
  }
  for (i = 0; i < n - 1; i++) {
    if ((x_points[i] == NULL) || (y_points[i] == NULL)) {
      return 0;
    }
  }
  x_points[n] = NULL;
  y_points[n] = NULL;
  int convex = check_figure(x_points, y_points);
  if (convex == 1) {
    printf("%s", "true");
  } else {
    printf("%s", "false");
  }
  free(x_points);
  free(y_points);
  //free(convex);
  return 0;
}
int check_figure(float *x_points[], float *y_points[]) {
  float first = 0, booll = 1, sign = 0, result = 0;
  int i = 0;
  //int *convex = (int*)malloc(sizeof(int));
  int convex;
  while (1) {
    if (x_points[i] != NULL) {
      i++;
    } else {
      break;
    }
  }
  first = *x_points[i - 1] * *y_points[0] - *y_points[i - 1] * *x_points[0];
  sign = first / fabsf(first);
  int k;
  for (k = 0; k < i - 2; k++) {
    result = *x_points[k] * *y_points[k + 1] - *x_points[k + 1] * *y_points[k];
    booll = booll * sign * result / fabsf(result);
    if (booll < 0) {
      convex = 0;
      return convex;
    } else {
      convex = 1;
      return convex;
    }
  }
}

有一个样本，例如i输入4，然后i输入0,2;2，-2;0,0;-2，-2;它使我归还我，但是多边形不是凸...我真的无法得到

Answer 1

如果其所有角度均匀或180度（嗯，那不是角度），多边形是凸的确保所有角度都是急性或180度。

在两个维度上，这并不难，您只需确保多边形总是以相同的方式缠绕，然后测试片段AB和BC之间的角度，您可以通过旋转VEC2（a -b）90度创建另一个向量朝多边形的中间（总是相同的旋转，因为它总是以相同的方式缠绕。可以通过翻转x和y值来完成90度旋转，然后根据您的方式否定一个值之一然后，如果该旋转载体的点产物和Vec2（C-B）的向量为正，则是急性，如果是负，则是钝的，如果它是0，则是直线。在三个维度上也不是那么难，但是您必须沿着与原始角度相同的平面旋转。

查看您的代码，我不知道该如何确定角度是否急性。在某个时候，您需要一个角度或角度的角度，或一个角度的余弦（通过点乘积在此方法中获得），或某种程度上与角度相关的内容。还有更多直接的方法可以做到这一点，这只是一个相对表现的方法。