BRL-CAD
bn_chull.c
Go to the documentation of this file.
1 /* B N _ C H U L L . C
2  * BRL-CAD
3  *
4  * Copyright (c) 2013-2014 United States Government as represented by
5  * the U.S. Army Research Laboratory.
6  *
7  * This library is free software; you can redistribute it and/or
8  * modify it under the terms of the GNU Lesser General Public License
9  * version 2.1 as published by the Free Software Foundation.
10  *
11  * This library is distributed in the hope that it will be useful, but
12  * WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14  * Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License along with this file; see the file named COPYING for more
18  * information.
19  */
20 
21 #include "common.h"
22 
23 #include <stdlib.h>
24 #include <stdio.h>
25 #include <string.h>
26 
27 #include "bu.h"
28 #include "vmath.h"
29 #include "bn.h"
30 #include "plot3.h"
31 
32 HIDDEN
33 void plot_chull(int test_num, const point_t *pnt_array, int pnt_cnt)
34 {
35  int i = 0;
36  struct bu_vls name;
37  FILE *plot_file = NULL;
38  bu_vls_init(&name);
39  bu_vls_printf(&name, "chull_test_%.3d.pl", test_num);
40  plot_file = fopen(bu_vls_addr(&name), "w");
41  pl_color(plot_file, 0, 255, 0);
42  for (i = 0; i < pnt_cnt; i++) {
43  pdv_3move(plot_file, pnt_array[i]);
44  if (i < pnt_cnt - 1) {
45  pdv_3cont(plot_file, pnt_array[i+1]);
46  } else {
47  pdv_3cont(plot_file, pnt_array[0]);
48  }
49  }
50  fclose(plot_file);
51  bu_vls_free(&name);
52 }
53 
54 
55 int
56 main(int argc, const char **argv)
57 {
58  int i = 0;
59  int retval = 0;
60  int do_plotting = 0;
61 
62  if (argc == 2 && BU_STR_EQUAL(argv[1], "-p")) do_plotting = 1;
63 
64  /* 2D input */
65  {
66  point2d_t test1_points[4+1] = {{0}};
67  point2d_t test1_results[5+1] = {{0}};
68  int n = 4;
69  point2d_t *hull_polyline = NULL;
70  point2d_t *hull_pnts = NULL;
71 
72  V2SET(test1_points[0], 1.5, 1.5);
73  V2SET(test1_points[1], 3.0, 2.0);
74  V2SET(test1_points[2], 2.0, 2.5);
75  V2SET(test1_points[3], 1.0, 2.0);
76 
77  V2SET(test1_results[0], 1.0, 2.0);
78  V2SET(test1_results[1], 1.5, 1.5);
79  V2SET(test1_results[2], 3.0, 2.0);
80  V2SET(test1_results[3], 2.0, 2.5);
81  V2SET(test1_results[4], 1.0, 2.0);
82 
83  retval = bn_polyline_2d_chull(&hull_polyline, (const point2d_t *)test1_points, n);
84  if (!retval) return -1;
85  bu_log("Test #001: polyline_2d_hull - 4 point test:\n");
86  for (i = 0; i < retval; i++) {
87  bu_log(" expected[%d]: (%f, %f)\n", i, V2ARGS(test1_results[i]));
88  bu_log(" actual[%d]: (%f, %f)\n", i, V2ARGS(hull_polyline[i]));
89  if (!NEAR_ZERO(test1_results[i][0] - hull_polyline[i][0], SMALL_FASTF) ||
90  !NEAR_ZERO(test1_results[i][1] - hull_polyline[i][1], SMALL_FASTF)) {
91  retval = 0;
92  }
93  }
94  if (!retval) {return -1;} else {bu_log("Test #001 Passed!\n");}
95 
96 
97  retval = bn_2d_chull(&hull_pnts, (const point2d_t *)test1_points, n);
98  if (!retval) return -1;
99  bu_log("Test #002: 2d_hull - 4 point test:\n");
100  for (i = 0; i < retval; i++) {
101  bu_log(" expected[%d]: (%f, %f)\n", i, V2ARGS(test1_results[i]));
102  bu_log(" actual[%d]: (%f, %f)\n", i, V2ARGS(hull_pnts[i]));
103  if (!NEAR_ZERO(test1_results[i][0] - hull_pnts[i][0], SMALL_FASTF) ||
104  !NEAR_ZERO(test1_results[i][1] - hull_pnts[i][1], SMALL_FASTF) ) {
105  retval = 0;
106  }
107  }
108  if (!retval) {return -1;} else {bu_log("Test #002 Passed!\n");}
109  }
110 
111  /* Triangle input */
112  {
113  point2d_t test1_points[3+1] = {{0}};
114  point2d_t test1_results[4+1] = {{0}};
115  int n = 3;
116  point2d_t *hull_pnts = NULL;
117 
118  V2SET(test1_points[0], 1.0, 0.0);
119  V2SET(test1_points[1], 3.0, 0.0);
120  V2SET(test1_points[2], 2.0, 4.0);
121 
122  V2SET(test1_results[0], 1.0, 0.0);
123  V2SET(test1_results[1], 3.0, 0.0);
124  V2SET(test1_results[2], 2.0, 4.0);
125  V2SET(test1_results[3], 1.0, 0.0);
126 
127  retval = bn_2d_chull(&hull_pnts, (const point2d_t *)test1_points, n);
128  if (!retval) return -1;
129  bu_log("Test #002: 2d_hull - triangle test:\n");
130  for (i = 0; i < retval; i++) {
131  bu_log(" expected[%d]: (%f, %f)\n", i, V2ARGS(test1_results[i]));
132  bu_log(" actual[%d]: (%f, %f)\n", i, V2ARGS(hull_pnts[i]));
133  if (!NEAR_ZERO(test1_results[i][0] - hull_pnts[i][0], SMALL_FASTF) ||
134  !NEAR_ZERO(test1_results[i][1] - hull_pnts[i][1], SMALL_FASTF) ) {
135  retval = 0;
136  }
137  }
138  if (!retval) {return -1;} else {bu_log("Triangle Test Passed!\n");}
139 
140  }
141 
142  /* 3D input */
143  {
144  point_t test3_points[17+1] = {{0}};
145  point_t *test3_hull_pnts = NULL;
146  VSET(test3_points[0], -0.5, 0.5, 0.5);
147  VSET(test3_points[1], 0.5, -0.5, 0.5);
148  VSET(test3_points[2], 0.5, 0.5, 0.5);
149  VSET(test3_points[3], -0.5, -0.5, 0.5);
150  VSET(test3_points[4], 0.5, 0.5, 0.5);
151  VSET(test3_points[5], -0.5, -0.5, 0.5);
152  VSET(test3_points[6], -0.5, 0.5, 0.5);
153  VSET(test3_points[7], 0.5, -0.5, 0.5);
154  VSET(test3_points[8], 0.1666666666666666574148081, 0.1666666666666666574148081, 0.5);
155  VSET(test3_points[9], -0.1666666666666666574148081, -0.1666666666666666574148081, 0.5);
156  VSET(test3_points[10], -0.3888888888888888950567946, -0.05555555555555555247160271, 0.5);
157  VSET(test3_points[11], -0.3518518518518518600757261, 0.09259259259259258745267118, 0.5);
158  VSET(test3_points[12], -0.4629629629629629095077803, -0.01851851851851851749053424, 0.5);
159  VSET(test3_points[13], 0.05555555555555555247160271, 0.3888888888888888950567946, 0.5);
160  VSET(test3_points[14], 0.3888888888888888950567946, 0.05555555555555555247160271, 0.5);
161  VSET(test3_points[15], 0.3518518518518518600757261, 0.2407407407407407273769451, 0.5);
162  VSET(test3_points[16], -0.05555555555555555247160271, -0.05555555555555555247160271, 0.5);
163  retval = bn_3d_coplanar_chull(&test3_hull_pnts, (const point_t *)test3_points, 17);
164  bu_log("Test #003: 3d_hull - points in XY plane at Z=0.5, duplicate points:\n");
165  for (i = 0; i < retval; i++) {
166  bu_log(" actual[%d]: (%f, %f, %f)\n", i, test3_hull_pnts[i][0], test3_hull_pnts[i][1], test3_hull_pnts[i][2]);
167  }
168  if (do_plotting) {
169  const point_t *const_test3_hull_pnts = (const point_t *)test3_hull_pnts;
170  plot_chull(3, const_test3_hull_pnts, retval);
171  }
172 
173  }
174 
175  {
176  point_t test4_points[17+1] = {{0}};
177  point_t *test4_hull_pnts = NULL;
178  VSET(test4_points[0],-0.2615997126297299746333636,0.9692719821506950994560725,1.113297221058902053414386);
179  VSET(test4_points[1],-0.6960082873702697625617475,-0.3376479821506951362053428,0.791972778941099408989146);
180  VSET(test4_points[2],0.08930731496876459507561208,0.2282231541335035251982788,0.5408368359872989250547448);
181  VSET(test4_points[3],-1.046915314968769772363544,0.4034008458664972707197194,1.364433164012702537348787);
182  VSET(test4_points[4],0.08930731496876459507561208,0.2282231541335035251982788,0.5408368359872989250547448);
183  VSET(test4_points[5],-1.046915314968769772363544,0.4034008458664972707197194,1.364433164012702537348787);
184  VSET(test4_points[6],-0.2615997126297299746333636,0.9692719821506950994560725,1.113297221058902053414386);
185  VSET(test4_points[7],-0.6960082873702697625617475,-0.3376479821506951362053428,0.791972778941099408989146);
186  VSET(test4_points[8],-0.2894335616770786212548217,0.2866157180445003671565019,0.8153689453291005362345345);
187  VSET(test4_points[9],-0.6681744383229220041187091,0.3450082819554983748489008,1.089901054670902258436627);
188  VSET(test4_points[10],-0.6588964886404735654679143,0.5725603699908965449338893,1.189210479914168061554847);
189  VSET(test4_points[11],-0.5295568798643752739252477,0.628946878032363931865234,1.13080291854799019901634);
190  VSET(test4_points[12],-0.6558038387463227536500199,0.6484110660026961570068238,1.222313621661925475692101);
191  VSET(test4_points[13],-0.1539086531126804824332055,0.4947036181095669227225642,0.823167667458433838234555);
192  VSET(test4_points[14],-0.2987115113595283921732459,0.05906363000910182931013637,0.7160595200858336228932899);
193  VSET(test4_points[15],-0.1662792526892814537475829,0.1913008340623683078973727,0.6907551004674108430236856);
194  VSET(test4_points[16],-0.5419274794409739692824246,0.3255440939851655945957987,0.9983903515569694242515197);
195  retval = bn_3d_coplanar_chull(&test4_hull_pnts, (const point_t *)test4_points, 17);
196  bu_log("Test #004: 3d_hull - points in tilted plane, duplicate points:\n");
197  for (i = 0; i < retval; i++) {
198  bu_log(" actual[%d]: (%f, %f, %f)\n", i, test4_hull_pnts[i][0], test4_hull_pnts[i][1], test4_hull_pnts[i][2]);
199  }
200  if (do_plotting) {
201  const point_t *const_test4_hull_pnts = (const point_t *)test4_hull_pnts;
202  plot_chull(4, const_test4_hull_pnts, retval);
203  }
204  }
205 
206  {
207  point_t test5_points[9+1] = {{0}};
208  point_t *test5_hull_pnts = NULL;
209  VSET(test5_points[0],-0.2894335616770786212548217,0.2866157180445003671565019,0.8153689453291005362345345);
210  VSET(test5_points[1],-0.6681744383229220041187091,0.3450082819554983748489008,1.089901054670902258436627);
211  VSET(test5_points[2],-0.6588964886404735654679143,0.5725603699908965449338893,1.189210479914168061554847);
212  VSET(test5_points[3],-0.5295568798643752739252477,0.628946878032363931865234,1.13080291854799019901634);
213  VSET(test5_points[4],-0.6558038387463227536500199,0.6484110660026961570068238,1.222313621661925475692101);
214  VSET(test5_points[5],-0.1539086531126804824332055,0.4947036181095669227225642,0.823167667458433838234555);
215  VSET(test5_points[6],-0.2987115113595283921732459,0.05906363000910182931013637,0.7160595200858336228932899);
216  VSET(test5_points[7],-0.1662792526892814537475829,0.1913008340623683078973727,0.6907551004674108430236856);
217  VSET(test5_points[8],-0.5419274794409739692824246,0.3255440939851655945957987,0.9983903515569694242515197);
218  retval = bn_3d_coplanar_chull(&test5_hull_pnts, (const point_t *)test5_points, 9);
219  bu_log("Test #005: 3d_hull - points from test 4 sans square corners, no duplicate points:\n");
220  for (i = 0; i < retval; i++) {
221  bu_log(" actual[%d]: (%f, %f, %f)\n", i, test5_hull_pnts[i][0], test5_hull_pnts[i][1], test5_hull_pnts[i][2]);
222  }
223  if (do_plotting) {
224  const point_t *const_test5_hull_pnts = (const point_t *)test5_hull_pnts;
225  plot_chull(5, const_test5_hull_pnts, retval);
226  }
227 
228  }
229 
230  return 0;
231 }
232 
233 
234 /** @} */
235 /*
236  * Local Variables:
237  * mode: C
238  * tab-width: 8
239  * indent-tabs-mode: t
240  * c-file-style: "stroustrup"
241  * End:
242  * ex: shiftwidth=4 tabstop=8
243  */
void bu_vls_init(struct bu_vls *vp)
Definition: vls.c:56
void bu_log(const char *,...) _BU_ATTR_PRINTF12
Definition: log.c:176
void pdv_3move(register FILE *plotfp, const fastf_t *pt)
Definition: plot3.c:618
#define VSET(a, b, c, d)
Definition: color.c:53
int main(int argc, const char **argv)
Definition: bn_chull.c:56
#define SMALL_FASTF
Definition: defines.h:342
Header file for the BRL-CAD common definitions.
#define HIDDEN
Definition: common.h:86
void bu_vls_free(struct bu_vls *vp)
Definition: vls.c:248
HIDDEN void plot_chull(int test_num, const point_t *pnt_array, int pnt_cnt)
Definition: bn_chull.c:33
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
void pdv_3cont(register FILE *plotfp, const fastf_t *pt)
Definition: plot3.c:630
char * bu_vls_addr(const struct bu_vls *vp)
Definition: vls.c:111
void pl_color(register FILE *plotfp, int r, int g, int b)
Definition: plot3.c:325
int bn_3d_coplanar_chull(point_t **hull, const point_t *points_3d, int n)
Find 3D coplanar point convex hull for unordered co-planar point sets.
Definition: chull.c:151
void bu_vls_printf(struct bu_vls *vls, const char *fmt,...) _BU_ATTR_PRINTF23
Definition: vls.c:694
int bn_polyline_2d_chull(point2d_t **hull, const point2d_t *polyline, int n)
Routines for the computation of convex hulls in 2D and 3D.
Definition: chull.c:46
Definition: vls.h:56
int bn_2d_chull(point2d_t **hull, const point2d_t *points_2d, int n)
Find 2D convex hull for unordered co-planar point sets.
Definition: chull.c:124
#define BU_STR_EQUAL(s1, s2)
Definition: str.h:126