C言語で二次元の点集合について点集合を含む最小の凸多角形（凸包）を構築するプログラムを作成したい

Question

前提・実現したいこと

　与えられた4つ以上の２次元座標の集合（csvファイル）についてgraham’s scanという方法を用いてすべての点集合を含みかつ凸（凸包）な多角形のの頂点をcsvファイルに書き込む形で出力するプログラムを作成したいです。
プログラム全体の大まかな流れは以下の通りです。

図１全体の流れ

次に、凸包探索の方法について説明します。

(c)でソートされた点の集合を小さい番号から検証していきます。
ここでは一般的に点 Pn, Pn+1, Pn+2 について考ると経路 PnPn+1 から見たとき，経路Pn+1Pn+2 が直進または時計回り (clockwise) の曲り道になる場合と，反時計回り (counter　clockwise) の曲り道になる場合が存在します。前者の場合，点 Pn+1 は凸包内部の点（頂点になりえない点）であるため，Pn+1をリストから削除し，Pn−1, Pn, Pn+1(元は Pn+2 だった点) について同様の処理を行います。Pn+1, Pn+2, Pn+3 について処理を行う。後者の場合、Pn+1, Pn+2, Pn+3について同様の処理を行います。この作業を繰り返し凸包を計算します。

発生している問題・エラーメッセージ

コンパイルはできたものの実行するとmain関数内のリスト構造を選択ソートする際のプログラム、void sortlist(void)　が動作しておらずコードを見直したがどこが間違えているのか分からなかった。

./a.out
input ok
find bottom ok. pos=(0.000000,0.000000)
swapnode ok
0.000000,0.000000
0.500000,1.400000
1.000000,1.000000
-0.500000,1.500000
2.000000,2.000000
0.000000,1.000000
1.000000,0.000000
0.800000,0.300000
0x7fffbd56b6f0, 0x7fffbd56b6f0, 1
^Z

該当のソースコード

#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

typedef struct { //座標の構造体

  double x, y;
} point;

typedef struct node {
  point data;
  struct node *next;
  struct node *pre;
} node;

node root = {{0,0}, NULL, NULL};

int addNode(point a) {
 // リストの末尾要素の次は常にNULLになるように設計してある。
  node *c;
  node *newNode = (node *)malloc(sizeof(node));
  if (newNode == NULL) {
    printf("メモリの確保に失敗しました\n");
    exit(1);
  }
  newNode->data = a;
  c = &root;
  while (c->next) c = c->next;
 
  newNode->next = NULL;
  newNode->pre = c;
  c->next = newNode;
   return 1;
}

node *find_bottom(void) {
  node *min = root.next;
  for (node *n = root.next->next; n; n = n->next) {
    if ((n->data.y < min->data.y) || (min->data.y == n->data.y && n->data.x < min->data.x)) {
   // yが最小、またはyが同じ場合よりxが小さい方を抽出
   min = n;
      }
  }
  return min;
}

int delete_node(int num) {

  if (num < 1) return 0;

  int pos = 1;
  node *preNode = &root; /* root は0番目のノード */
  node *delete_target;

  while (pos < num) {
    if (preNode == NULL) {
    return 0;
    }
    preNode = preNode->next;
    pos++;
  }
  delete_target = preNode->next;
  preNode->next = delete_target->next;
  
  if (delete_target->next != &root) 
  delete_target->next->pre = preNode;

  free(delete_target);
  return 1;
}

//角度を求める
double theta(node *point1, node *point2) {
  double dx = point2->data.x - point1->data.x;
  double dy = point2->data.y - point1->data.y;
  return atan2(dy, dx);
}
//距離を求める
double distance(point a, point b) {
  double x = a.x - b.x;
  double y = a.y - b.y;
  x = x * x;
  y = y * y;
  return x + y;
}
//時計回りかどうかを判定
float checkclockwise(node *point1, node *point2, node *point3) {
  return (point2->data.x - point1->data.x) * (point3->data.y - point2->data.y) -//y->x
         (point2->data.y - point1->data.y) * (point3->data.x - point2->data.x);
}

void delete_theta(void) {
  node *min = root.next, *n = min->next;

  for (int i = 2; n->next != &root; i++) {
 //同じ角度だったら
  if (theta(min, n) == theta(min, n->next)) {
   //基準から近い方を消す
    if (distance(min->data, n->data) > distance(min->data, n->data)) {
      delete_node(i + 1);
      i--;
    } else {
      n = n->next;
      delete_node(i);
      i--;
    }
  } else {
    n = n->next;
   }
  }
}

int swapNode(node *n1, node *n2) {
 node *tmp;
 if (n1 == NULL || n2 == NULL) {
  printf("n1 or n2 is NULL\n");
  exit(1);
 }

 n1->pre->next = n2;
 n2->pre->next = n1;

 tmp = n1->pre;
 n1->pre = n2->pre;
 n2->pre = tmp;

 n1->next->pre = n2;
 if (n2->next != NULL)
  n2->next->pre = n1;

 tmp = n1->next;
 n1->next = n2->next;
 n2->next = tmp;

 return 0;
}

void sortlist(void) {
 // 選択ソート
 node *n1;
 node *minimum = root.next;
 for (n1=root.next->next; n1->next; n1=n1->next) {
  node *n2;
  int d;
  for (n2=n1->next; n2; n2=n2->next){
   if (theta(minimum,n1)>theta(minimum,n2)){
    swapNode(n1,n2);
    // n1が元n2の連結の位置に行き、n2が元n1の連結の位置に行ったため戻す
    n1 = n2;
   }
   printf("%p, %p, %d\n",n1,n2,n1==n2);
   getc(stdin);
  }
  
 }
}

void convex_hull(void) {
  node *prevNode = root.next->next, *node = prevNode->next,
       *nextNode = node->next;
  int i = 3;
  //凸包探索開始
  while (nextNode != &root) {
 //時計回りかどうかの判定
 if (checkclockwise(prevNode, node, nextNode) > 0) {
   //時計回りだったら次の点を探す
   prevNode = node;
   node = nextNode;
   ;
   nextNode = nextNode->next;
   i++;
 } else {
   //反時計回りだったら1個前の点にする
   prevNode = prevNode->pre;
   node = node->pre;
   delete_node(i);
   i--;
 }
  }
}

int main(void) {
  point a;
  int idx = 0;
  root.next = root.pre = NULL;

  FILE *input = fopen("points.csv", "r");

  if (input == NULL) {
 printf("開くのに失敗しました。");
 return 1;
  }

  //座標をリストに追加していく
  while (fscanf(input, "%lf,%lf", &a.x, &a.y) != EOF) {
    addNode(a);
  }

  fclose(input);
  printf("input ok\n");

  // Yが一番小さいノードを基準P0にするため取得（複数あった場合はXの小さいものを選ぶ）
  node *minnode = find_bottom();
  printf("find bottom ok. pos=(%lf,%lf)\n", minnode->data.x, minnode->data.y);
  //基準を先頭にする
  swapNode(root.next, minnode);
  printf("swapnode ok\n");
  //基準との角度で並び替え
  for(node *n=root.next;n;n=n->next)
 printf("%lf,%lf\n",n->data.x,n->data.y);
 
 //ここまでオッケー
  sortlist();
  printf("sortlist ok\n");
  for(node *n=root.next->next;n;n=n->next)
 printf("%lf\n",theta(root.next,n));
  //同じ角度のものを消す
  delete_theta();
  printf("delete theta ok\n");

  convex_hull();
  printf("convex hull ok\n");

  FILE *output = fopen("output.csv", "w");
  if (output == NULL) {
 printf("開くのに失敗しました。");
 return 1;
  }

  node *n = root.next;

  while (n != &root) {
 fprintf(output, "%lf, %lf\n", n->data.x, n->data.y);
 *n = *n->next;
  }

  fclose(output);

  return 0;
}

試したこと

printf("OK")などでデバッグを試みた

補足情報（FW/ツールのバージョンなど）

開発環境
Visual Studio Code
Ubunts 20.04

参考文献
[1]https://www.youtube.com/watch?v=B2AJoQSZf4M
「 Convex Hull Algorithm - Graham Scan and Jarvis March tutorial」

input用のcsvファイルです

-0.5,1.5
0.5,1.4
1.0,1.0
0.0,0.0
2.0,2.0
0.0,1.0
1.0,0.0
0.8,0.3

ここにより詳細な情報を記載してください。

Comments

[jimbe]

> printf("OK")などでデバッグを試みた

その結果、どの様に表示されたのでしょう。

Answer 1

98行目の

  if (theta(min, n) == theta(min, n->next)) {

にあるn->nextがリストの最後でNULLになってますね。
そしてtheta関数内の point2->data.xがNULL参照を起こして落ちてます。

Comments

[退会済みユーザー]

あと補足ですが、ubuntuでgdbが使えるのであればvscodeからデバッグするのがおすすめです。

Answer 2

双方向リストの最後は next==NULL なのでしょうか、それとも next==&root なのでしょうか。

Answer 3

例外で停止するようなプログラムをプリントデバッグする場合には適当なタイミングでフラッシュしないと、コードは実行されてもメッセージが画面に出力されないまま終了してしまう場合があります。
手元で試したところでは、ちゃんとフラッシュすれば「sortlist ok」も出力されます。(環境によって結果が変わる類のバグの可能性もありますが)
それを踏まえてもう一度デバッグしてみるといいと思います。