space_partition.h 8.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303
  1. /*************************************/
  2. /* Auteur : Rémi Synave */
  3. /* Date de création : 01/11/07 */
  4. /* Date de modification : 15/03/15 */
  5. /* Version : 0.4 */
  6. /*************************************/
  7. /*************************************/
  8. /* Auteur : Romain Leguay */
  9. /* Nguyen Haiduong */
  10. /* Marianne Fichoux */
  11. /* Date de modification : 06/06/09 */
  12. /* Version : 0.2 */
  13. /*************************************/
  14. /***************************************************************************/
  15. /* This file is part of a2ri. */
  16. /* */
  17. /* a2ri is free software: you can redistribute it and/or modify it */
  18. /* under the terms of the GNU Lesser General Public License as published */
  19. /* by the Free Software Foundation, either version 3 of the License, or */
  20. /* (at your option) any later version. */
  21. /* */
  22. /* a2ri is distributed in the hope that it will be useful, */
  23. /* but WITHOUT ANY WARRANTY; without even the implied warranty of */
  24. /* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the */
  25. /* GNU Lesser General Public License for more details. */
  26. /* */
  27. /* You should have received a copy of the GNU Lesser General Public */
  28. /* License along with a2ri. */
  29. /* If not, see <http://www.gnu.org/licenses/>. */
  30. /***************************************************************************/
  31. #ifndef SPACE_PARTITION__H
  32. #define SPACE_PARTITION__H
  33. #include <stdio.h>
  34. #include <stdlib.h>
  35. #include "point.h"
  36. #include "geometry.h"
  37. #include "util.h"
  38. #define REJECT_ZERO_LENGTH 0
  39. #define ACCEPT_ZERO_LENGTH 1
  40. typedef struct
  41. {
  42. point3d *list_point;
  43. int nb_point;
  44. } sp_depth,
  45. *pt_sp_depth;
  46. typedef struct
  47. {
  48. sp_depth *z;
  49. } sp_height;
  50. typedef struct
  51. {
  52. sp_height *y;
  53. } sp_width;
  54. /**
  55. structure de partition de l'espace avec un tableau à 3 dimensions contenant des listes de points
  56. */
  57. typedef struct
  58. {
  59. point3d ptmin,
  60. ptmax;
  61. int nb_part_x,
  62. nb_part_y,
  63. nb_part_z;
  64. sp_width *x;
  65. } space_partition;
  66. /**
  67. Initialisation d'une partition de l'espace
  68. @param sp la partition de l'espace
  69. @return aucun
  70. */
  71. void space_partition_init (
  72. space_partition * sp);
  73. /**
  74. Création d'une nouvelle partition de l'espace
  75. @param sp la partition de l'espace
  76. @param min coin inférieur
  77. @param max coin supérieur
  78. @param nbpartx nombre de partition en X
  79. @param nbparty nombre de partition en Y
  80. @param nbpartz nombre de partition en Z
  81. @return aucun
  82. */
  83. void space_partition_new (
  84. space_partition * sp,
  85. const point3d * const min,
  86. const point3d * const max,
  87. int nbpartx,
  88. int nbparty,
  89. int nbpartz);
  90. /**
  91. Désallocation mémoire de la partition de l'espace
  92. @param sp la partition de l'espace
  93. @return aucun
  94. */
  95. void space_partition_free (
  96. space_partition * sp);
  97. /**
  98. Affichage simple d'une partition de l'espace
  99. @param sp la partition de l'espace
  100. @return aucun
  101. */
  102. void space_partition_display (
  103. const space_partition * const sp);
  104. /**
  105. Affichage detaillé d'une partition de l'espace
  106. @param sp la partition de l'espace
  107. @return aucun
  108. */
  109. void space_partition_display_detail (
  110. const space_partition * const sp);
  111. /**
  112. Affichage detaillé d'une partition de l'espace
  113. @param sp la partition de l'espace
  114. @return aucun
  115. */
  116. void space_partition_display_high_detail (
  117. const space_partition * const sp);
  118. /**
  119. Calcule les numeros de cases du point
  120. @param sp la partition de l'espace
  121. @param p le point
  122. @param x le numéro de case en X
  123. @param y le numéro de case en Y
  124. @param z le numéro de case en Z
  125. @return aucun
  126. **/
  127. void space_partition_get_XYZ (
  128. const space_partition * const sp,
  129. const point3d * const p,
  130. int *x,
  131. int *y,
  132. int *z);
  133. /**
  134. Ajout d'un point dans la partition de l'espace
  135. @param sp la partition de l'espace
  136. @param p le point à ajouter
  137. @return aucun
  138. */
  139. void space_partition_add_point (
  140. space_partition * sp,
  141. const point3d * const p);
  142. /**
  143. Calcule le point moyen d'une cellule
  144. @param sp la partition de l'espace
  145. @param cell_x numéro de la cellule en X
  146. @param cell_y numéro de la cellule en Y
  147. @param cell_z numéro de la cellule en Z
  148. @param aucun
  149. */
  150. point3d space_partition_get_average (
  151. const space_partition * const sp,
  152. int cell_x,
  153. int cell_y,
  154. int cell_z);
  155. /**
  156. Calcule le point milieu d'une cellule
  157. @param sp la partition de l'espace
  158. @param cell_x numéro de la cellule en X
  159. @param cell_y numéro de la cellule en Y
  160. @param cell_z numéro de la cellule en Z
  161. @param aucun
  162. */
  163. point3d space_partition_get_middle (
  164. const space_partition * const sp,
  165. int cell_x,
  166. int cell_y,
  167. int cell_z);
  168. /**
  169. Retourne le nombre total de points de la partition de l'espace
  170. @param sp la partition de l'espace
  171. @return le nombre de points
  172. */
  173. int space_partition_nb_points (
  174. const space_partition * const sp);
  175. /**
  176. Retourne les cases adjacentes à celle contenant le point passé en paramètre est à une distance maximum de distance
  177. @param sp la partition de l'espace
  178. @param pt le point servant à sélectionner la case centrale
  179. @param distance profondeur de la sélection
  180. @param list liste des cases sélectionnées
  181. @param size taille de la liste retournée
  182. @return aucun
  183. **/
  184. void space_partition_get_neighbour (
  185. const space_partition * const sp,
  186. const point3d * const pt,
  187. int distance,
  188. pt_sp_depth ** list,
  189. int *size);
  190. /**
  191. Retourne le point le plus proche d'un point donné
  192. @param sp la partition de l'espace
  193. @param pt le point dont on cherche le point le plus proche dans la partition de l'espace
  194. @param near_pt point le plus proche de la partition de l'espace
  195. @param length longueur entre les deux points
  196. @return un pointeur vers le point de la partition le plus paroche de celui recherche
  197. */
  198. point3d * space_partition_nearest_point (
  199. const space_partition * const sp,
  200. const point3d * const pt,
  201. point3d * near_pt,
  202. double *length,
  203. int acceptzerolength);
  204. /**
  205. Retourne un pointeur vers le point de la partition s'il existe
  206. @param sp la partition de l'espace
  207. @param pt le point que l'on cherche dans la partition
  208. @return un pointeur vers le point cherché, NULL sinon
  209. */
  210. point3d * space_partition_contains_point (
  211. const space_partition * const sp,
  212. const point3d * const pt);
  213. /**
  214. Enlève les outliers
  215. @param sp la partition de l'espace
  216. @return aucun
  217. */
  218. void space_partition_remove_outliers (
  219. space_partition * sp);
  220. /**
  221. retourne une liste de pointeur sur des point3d contenus dans les cellules passées en paramètre
  222. @param sp la partition de l'espace
  223. @param listcellx liste des index des cellules en X
  224. @param listcelly liste des index des cellules en Y
  225. @param listcellz liste des index des cellules en Z
  226. @param sizelist taille de la liste des cellules
  227. @param listpoint liste des pointeurs vers les point3d
  228. @param sizelistpoint taille de la liste de pointeur
  229. @return aucun
  230. **/
  231. void space_partition_get_points_cells (
  232. const space_partition * const sp,
  233. const int * const listcellx,
  234. const int * const listcelly,
  235. const int * const listcellz,
  236. int sizelist,
  237. pt_point3d ** listpoint,
  238. int *sizelistpoint);
  239. /**
  240. Calcule la Bounding Box de la liste de points
  241. @param sp la partition de l'epace
  242. @param list la list de point
  243. @param size nombre de points
  244. @param xmin cellule minimale en X
  245. @param ymin cellule minimale en Y
  246. @param zmin cellule minimale en Z
  247. @param xmax cellule maximale en X
  248. @param ymax cellule maximale en Y
  249. @param zmax cellule maximale en Z
  250. **/
  251. void space_partition_bounding_box (
  252. const space_partition * const sp,
  253. const point3d * const list,
  254. int size,
  255. int *xmin,
  256. int *ymin,
  257. int *zmin,
  258. int *xmax,
  259. int *ymax,
  260. int *zmax);
  261. /**
  262. Retourne les cases adjacentes et elle-même à celle contenant le point passé en paramètre est à une distance maximum de distance
  263. @param sp la partition de l'espace
  264. @param pt le point servant à sélectionner la case centrale
  265. @param list liste des cases sélectionnées
  266. @param size taille de la liste retournée
  267. @return aucun
  268. **/
  269. void space_partition_get_list_near_point (
  270. const space_partition * const sp,
  271. const point3d * const pt,
  272. pt_sp_depth ** list,
  273. int *size);
  274. #endif