BRL-CAD
obr.c
Go to the documentation of this file.
1 /* O B R . 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  * Geometric Tools, LLC
8  * Copyright (c) 1998-2013
9 
10  * Boost Software License - Version 1.0 - August 17th, 2003
11  *
12  * Permission is hereby granted, free of charge, to any person or organization
13  * obtaining a copy of the software and accompanying documentation covered by
14  * this license (the "Software") to use, reproduce, display, distribute,
15  * execute, and transmit the Software, and to prepare derivative works of the
16  * Software, and to permit third-parties to whom the Software is furnished to
17  * do so, all subject to the following:
18  *
19  * The copyright notices in the Software and this entire statement, including
20  * the above license grant, this restriction and the following disclaimer,
21  * must be included in all copies of the Software, in whole or in part, and
22  * all derivative works of the Software, unless such copies or derivative
23  * works are solely in the form of machine-executable object code generated by
24  * a source language processor.
25  *
26  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
27  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
28  * FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
29  * SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
30  * FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
31  * ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
32  * DEALINGS IN THE SOFTWARE.
33  *
34  */
35 /** @file obr.c
36  *
37  * This file implements the Rotating Calipers algorithm for finding the
38  * minimum oriented bounding rectangle for a convex hull:
39  *
40  * Shamos, Michael, "Analysis of the complexity of fundamental geometric
41  * algorithms such as area computation, sweep-line algorithms, polygon
42  * intersection, Voronoi diagram construction, and minimum spanning tree."
43  * Phd Thesis, Yale, 1978.
44  *
45  * Godfried T. Toussaint, "Solving geometric problems with the rotating
46  * calipers," Proceedings of IEEE MELECON'83, Athens, Greece, May 1983.
47  *
48  * This is a translation of the Geometric Tools MinBox2 implementation:
49  * http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox2.cpp
50  * http://www.geometrictools.com/LibMathematics/Algebra/Wm5Vector2.inl
51  *
52  */
53 
54 
55 #include "common.h"
56 #include <stdlib.h>
57 
58 #include "bu/malloc.h"
59 #include "bn/chull.h"
60 #include "bn/obr.h"
61 #include "bn/plane_calc.h"
62 #include "bn/tol.h"
63 #include "./bn_private.h"
64 
65 #define F_NONE -1
66 #define F_BOTTOM 0
67 #define F_RIGHT 1
68 #define F_TOP 2
69 #define F_LEFT 3
70 
71 HIDDEN int
72 pnt2d_array_get_dimension(const point2d_t *pnts, int pnt_cnt, point2d_t *p_center, point2d_t *p1, point2d_t *p2)
73 {
74  int i = 0;
75  point2d_t min = V2INIT_ZERO;
76  point2d_t max = V2INIT_ZERO;
77  point2d_t center = V2INIT_ZERO;
78  point2d_t curr_pnt = V2INIT_ZERO;
79  point2d_t min_x_pt = V2INIT_ZERO;
80  point2d_t min_y_pt = V2INIT_ZERO;
81  point2d_t max_x_pt = V2INIT_ZERO;
82  point2d_t max_y_pt = V2INIT_ZERO;
83  point2d_t A = V2INIT_ZERO;
84  point2d_t B = V2INIT_ZERO;
85  fastf_t dmax, dist_minmax;
86 
87  V2MOVE(curr_pnt, pnts[0]);
88  V2MOVE(min_x_pt, curr_pnt);
89  V2MOVE(min_y_pt, curr_pnt);
90  V2MOVE(max_x_pt, curr_pnt);
91  V2MOVE(max_y_pt, curr_pnt);
92 
93  while (i < pnt_cnt) {
94  V2MOVE(curr_pnt, pnts[i]);
95  center[0] += curr_pnt[0];
96  center[1] += curr_pnt[1];
97  V2MINMAX(min, max, curr_pnt);
98  if (min_x_pt[0] > curr_pnt[0]) V2MOVE(min_x_pt, curr_pnt);
99  if (min_y_pt[1] > curr_pnt[1]) V2MOVE(min_y_pt, curr_pnt);
100  if (max_x_pt[0] < curr_pnt[0]) V2MOVE(max_x_pt, curr_pnt);
101  if (max_y_pt[1] < curr_pnt[1]) V2MOVE(max_y_pt, curr_pnt);
102  i++;
103  }
104  center[0] = center[0] / i;
105  center[1] = center[1] / i;
106  V2MOVE(*p_center, center);
107  V2MOVE(*p1, min);
108  V2MOVE(*p2, max);
109  /* If the bbox is nearly a point, return 0 */
110  if (NEAR_ZERO(max[0] - min[0], BN_TOL_DIST) && NEAR_ZERO(max[1] - min[1], BN_TOL_DIST)) return 0;
111 
112  /* Test if the point set is (nearly) a line */
113 
114  /* find the min A and max B with the greatest distance between them */
115  dmax = 0.0;
116  dist_minmax = DIST_PT2_PT2(min_x_pt, max_x_pt);
117  if (dist_minmax > dmax) {
118  V2MOVE(A, min_x_pt);
119  V2MOVE(B, min_x_pt);
120  }
121 #define MAXDIST_AB(_minpt, _maxpt) { \
122  fastf_t md_dist = DIST_PT2_PT2(_minpt, _maxpt); \
123  if (md_dist > dmax) { \
124  dmax = md_dist; \
125  V2MOVE(A, _minpt); \
126  V2MOVE(B, _maxpt); \
127  } \
128 }
129  MAXDIST_AB(min_x_pt, max_x_pt);
130  MAXDIST_AB(min_x_pt, max_y_pt);
131  MAXDIST_AB(min_y_pt, max_x_pt);
132  MAXDIST_AB(min_y_pt, max_y_pt);
133 
134  i = 0;
135  while (i < pnt_cnt) {
136  const struct bn_tol tol = {BN_TOL_MAGIC, BN_TOL_DIST / 2, BN_TOL_DIST *BN_TOL_DIST / 4, 1e-6, 1 - 1e-6};
138  fastf_t pca[2];
139  point_t A_3D, B_3D, curr_pnt_3D;
140  i++;
141  VSET(A_3D, A[0], A[1], 0.0);
142  VSET(B_3D, B[0], B[1], 0.0);
143  V2MOVE(curr_pnt, pnts[i]);
144  VSET(curr_pnt_3D, curr_pnt[0], curr_pnt[1], 0.0);
145  /* If we're off the line, it's 2D. */
146  if (bn_dist_pt2_lseg2(&dist_sq, pca, A_3D, B_3D, curr_pnt_3D, &tol) > 2) return 2;
147  }
148  /* If we've got a line, make sure p1 and p2 are the extreme points */
149  V2MOVE(*p1, A);
150  V2MOVE(*p2, B);
151  return 1;
152 }
153 
154 struct obr_vals {
156  vect2d_t u;
157  vect2d_t v;
160  point2d_t center;
161 };
162 
163 /* The oriented bounding rectangle must be calculated from the points and 2D vectors provided by
164  * the rotating calipers, and the smallest resultant area tracked. Those functions are handled
165  * by this routine.*/
166 HIDDEN void
167 UpdateBox(struct obr_vals *obr, point2d_t left_pnt, point2d_t right_pnt, point2d_t bottom_pnt,
168  point2d_t top_pnt, vect2d_t u)
169 {
170  vect2d_t right_left_diff, top_bottom_diff, left_bottom_diff;
171  vect2d_t U, V, v;
172  fastf_t extent0, extent1, area;
173  V2SET(v, -u[1], u[0]);
174 
175  V2SUB2(right_left_diff, right_pnt, left_pnt);
176  V2SUB2(top_bottom_diff, top_pnt, bottom_pnt);
177  extent0 = 0.5 * V2DOT(u, right_left_diff);
178  extent1 = 0.5 * V2DOT(v, top_bottom_diff);
179  area = extent0 * extent1 * 4;
180 
181  if (area < obr->area) {
182  obr->area = area;
183  V2MOVE(obr->u, u);
184  V2MOVE(obr->v, v);
185  obr->extent0 = extent0;
186  obr->extent1 = extent1;
187  /* Note: translated the following to vmath.h routines...
188  mMinBox.Center = left_pnt + U*extent0 + V*(extent1 - V.Dot(left_bottom_diff));*/
189  V2SUB2(left_bottom_diff, left_pnt, bottom_pnt);
190  V2SCALE(U, u, extent0);
191  V2SCALE(V, v, extent1 - V2DOT(v, left_bottom_diff));
192  V2ADD3(obr->center, left_pnt, U, V);
193  V2SCALE(V, v, extent1);
194  }
195 }
196 
197 /* Three consecutive collinear points will cause a problem (as per a comment in the original code)
198  * Consequently, we're going to have to build the convex hull for all non-trivial inputs in order to
199  * make sure we don't get collinear points from the NMG inputs.*/
200 HIDDEN int
201 bn_obr_calc(const point2d_t *pnts, int pnt_cnt, struct obr_vals *obr)
202 {
203  int i = 0;
204  int dim = 0;
205  int done = 0;
206  int hull_pnt_cnt = 0;
207  point2d_t *hull_pnts = NULL;
208  vect2d_t *edge_unit_vects = NULL;
209  int *visited = NULL;
210  point2d_t center, pmin, pmax;
211  vect2d_t u;
212  vect2d_t vline;
213  dim = pnt2d_array_get_dimension(pnts, pnt_cnt, &center, &pmin, &pmax);
214  switch (dim) {
215  case 0:
216  /* Bound point */
217  V2SET(obr->center, center[0] - BN_TOL_DIST, center[1] - BN_TOL_DIST);
218  V2SET(obr->u, 1 , 0);
219  V2SET(obr->v, 0, 1);
220  obr->extent0 = BN_TOL_DIST;
221  obr->extent1 = BN_TOL_DIST;
222  break;
223  case 1:
224  /* Bound line */
225  V2SUB2(vline, pmax, pmin);
226  obr->extent0 = MAGNITUDE2(vline) * 0.5;
227  obr->extent1 = BN_TOL_DIST;
228  V2SET(obr->center, center[0] / 2, center[1] / 2);
229  V2SUB2(vline, pmax, center);
230  V2UNITIZE(vline);
231  V2SET(obr->u, vline[0], vline[1]);
232  V2SET(obr->v, -vline[1], vline[0]);
233  V2UNITIZE(obr->v);
234  break;
235  case 2:
236  /* Bound convex hull using rotating calipers */
237 
238  /* 1. Get convex hull */
239  hull_pnt_cnt = bn_2d_chull(&hull_pnts, pnts, pnt_cnt);
240 
241  /* 2. Get edge unit vectors */
242  edge_unit_vects = (vect2d_t *)bu_calloc(hull_pnt_cnt + 1, sizeof(fastf_t) * 3, "unit vects for edges");
243  visited = (int *)bu_calloc(hull_pnt_cnt + 1, sizeof(int), "visited flags");
244  for (i = 0; i < hull_pnt_cnt - 1; ++i) {
245  V2SUB2(edge_unit_vects[i], hull_pnts[i + 1], hull_pnts[i]);
246  V2UNITIZE(edge_unit_vects[i]);
247  }
248  V2SUB2(edge_unit_vects[hull_pnt_cnt - 1], hull_pnts[0], hull_pnts[hull_pnt_cnt - 1]);
249  V2UNITIZE(edge_unit_vects[hull_pnt_cnt - 1]);
250 
251  /* 3. Find the points involved with the AABB */
252  /* Find the smallest axis-aligned box containing the points. Keep track */
253  /* of the extremum indices, L (left), R (right), B (bottom), and T (top) */
254  /* so that the following constraints are met: */
255  /* V[L][0] <= V[i][0] for all i and V[(L+1)%N][0] > V[L][0] */
256  /* V[R][0] >= V[i][0] for all i and V[(R+1)%N][0] < V[R][0] */
257  /* V[B][1] <= V[i][1] for all i and V[(B+1)%N][1] > V[B][1] */
258  /* V[T][1] >= V[i][1] for all i and V[(T+1)%N][1] < V[T][1] */
259  {
260  fastf_t xmin = hull_pnts[0][0];
261  fastf_t xmax = xmin;
262  fastf_t ymin = hull_pnts[0][1];
263  fastf_t ymax = ymin;
264  int LIndex = 0;
265  int RIndex = 0;
266  int BIndex = 0;
267  int TIndex = 0;
268  for (i = 1; i < hull_pnt_cnt; ++i) {
269  if (hull_pnts[i][0] <= xmin) {
270  xmin = hull_pnts[i][0];
271  LIndex = i;
272  }
273  if (hull_pnts[i][0] >= xmax) {
274  xmax = hull_pnts[i][0];
275  RIndex = i;
276  }
277 
278  if (hull_pnts[i][1] <= ymin) {
279  ymin = hull_pnts[i][1];
280  BIndex = i;
281  }
282  if (hull_pnts[i][1] >= ymax) {
283  ymax = hull_pnts[i][1];
284  TIndex = i;
285  }
286  }
287 
288  /* Apply wrap-around tests to ensure the constraints mentioned above are satisfied.*/
289  if ((LIndex == (hull_pnt_cnt - 1)) && (hull_pnts[0][0] <= xmin)) {
290  xmin = hull_pnts[0][0];
291  LIndex = 0;
292  }
293 
294  if ((RIndex == (hull_pnt_cnt - 1)) && (hull_pnts[0][0] >= xmax)) {
295  xmax = hull_pnts[0][0];
296  RIndex = 0;
297  }
298 
299  if ((BIndex == (hull_pnt_cnt - 1)) && (hull_pnts[0][1] <= ymin)) {
300  ymin = hull_pnts[0][1];
301  BIndex = 0;
302  }
303 
304  if ((TIndex == (hull_pnt_cnt - 1)) && (hull_pnts[0][1] >= ymax)) {
305  ymax = hull_pnts[0][1];
306  TIndex = 0;
307  }
308 
309  /* initialize with AABB */
310  obr->center[0] = 0.5 * (xmin + xmax);
311  obr->center[1] = 0.5 * (ymin + ymax);
312  V2SET(obr->u, obr->center[0], 0);
313  V2UNITIZE(obr->u);
314  V2SET(obr->v, -obr->u[1], obr->u[0]);
315  V2UNITIZE(obr->v);
316  obr->extent0 = 0.5 * (xmax - xmin);
317  obr->extent1 = 0.5 * (ymax - ymin);
318  obr->area = obr->extent0 * obr->extent1 * 4;
319 
320  /* 3. The rotating calipers algorithm */
321  done = 0;
322  V2SET(u, 1, 0);
323 
324  while (!done) {
325  /* Determine the edge that forms the smallest angle with the current
326  box edges. */
327  int flag = F_NONE;
328  fastf_t maxDot = 0.0;
329  fastf_t dot = 0.0;
330  vect2d_t t, tmp;
331  V2MOVE(t, u);
332 
333 
334  dot = V2DOT(t, edge_unit_vects[BIndex]);
335  /*bu_log("t: %f, %f\n", t[0], t[1]);
336  bu_log("edge_unit_vects[%d]: %f, %f\n", BIndex, edge_unit_vects[BIndex][0], edge_unit_vects[BIndex][1]);
337  bu_log("b_dot: %f\n", dot);*/
338  if (dot > maxDot) {
339  maxDot = dot;
340  flag = F_BOTTOM;
341  }
342 
343  V2SET(t, -u[1], u[0]);
344  dot = V2DOT(t, edge_unit_vects[RIndex]);
345  /*bu_log("t: %f, %f\n", t[0], t[1]);
346  bu_log("edge_unit_vects[%d]: %f, %f\n", BIndex, edge_unit_vects[RIndex][0], edge_unit_vects[RIndex][1]);
347  bu_log("r_dot: %f\n", dot);*/
348  if (dot > maxDot) {
349  maxDot = dot;
350  flag = F_RIGHT;
351  }
352 
353  V2SET(tmp, -t[1], t[0]);
354  V2MOVE(t, tmp);
355  dot = V2DOT(t, edge_unit_vects[TIndex]);
356  /*bu_log("t: %f, %f\n", t[0], t[1]);
357  bu_log("edge_unit_vects[%d]: %f, %f\n", BIndex, edge_unit_vects[TIndex][0], edge_unit_vects[TIndex][1]);
358  bu_log("t_dot: %f\n", dot);*/
359  if (dot > maxDot) {
360  maxDot = dot;
361  flag = F_TOP;
362  }
363 
364  V2SET(tmp, -t[1], t[0]);
365  V2MOVE(t, tmp);
366  dot = V2DOT(t, edge_unit_vects[LIndex]);
367  /*bu_log("t: %f, %f\n", t[0], t[1]);
368  bu_log("edge_unit_vects[%d]: %f, %f\n", BIndex, edge_unit_vects[LIndex][0], edge_unit_vects[LIndex][1]);
369  bu_log("l_dot: %f\n", dot);*/
370  if (dot > maxDot) {
371  maxDot = dot;
372  flag = F_LEFT;
373  }
374 
375  switch (flag) {
376  case F_BOTTOM:
377  if (visited[BIndex]) {
378  done = 1;
379  } else {
380  /* Compute box axes with E[B] as an edge.*/
381  V2MOVE(t, edge_unit_vects[BIndex]);
382  V2MOVE(u, t);
383  UpdateBox(obr, hull_pnts[LIndex], hull_pnts[RIndex],
384  hull_pnts[BIndex], hull_pnts[TIndex], u);
385 
386  /* Mark edge visited and rotate the calipers. */
387  visited[BIndex] = 1;
388  if ((BIndex + 1) == hull_pnt_cnt) {
389  BIndex = 0;
390  } else {
391  BIndex = BIndex + 1;
392  }
393  }
394  break;
395  case F_RIGHT:
396  if (visited[RIndex]) {
397  done = 1;
398  } else {
399  /* Compute box axes with E[R] as an edge. */
400  V2MOVE(t, edge_unit_vects[RIndex]);
401  V2SET(u, t[1], -t[0]);
402  UpdateBox(obr, hull_pnts[LIndex], hull_pnts[RIndex],
403  hull_pnts[BIndex], hull_pnts[TIndex], u);
404 
405  /* Mark edge visited and rotate the calipers. */
406  visited[RIndex] = 1;
407  if ((RIndex + 1) == hull_pnt_cnt) {
408  RIndex = 0;
409  } else {
410  RIndex = RIndex + 1;
411  }
412  }
413  break;
414  case F_TOP:
415  if (visited[TIndex]) {
416  done = 1;
417  } else {
418  /* Compute box axes with E[T] as an edge. */
419  V2MOVE(t, edge_unit_vects[TIndex]);
420  V2SCALE(t, t, -1);
421  V2MOVE(u, t);
422  UpdateBox(obr, hull_pnts[LIndex], hull_pnts[RIndex],
423  hull_pnts[BIndex], hull_pnts[TIndex], u);
424 
425  /* Mark edge visited and rotate the calipers. */
426  visited[TIndex] = 1;
427  if ((TIndex + 1) == hull_pnt_cnt) {
428  TIndex = 0;
429  } else {
430  TIndex = TIndex + 1;
431  }
432 
433  }
434  break;
435  case F_LEFT:
436  if (visited[LIndex]) {
437  done = 1;
438  } else {
439  /* Compute box axes with E[L] as an edge. */
440  V2MOVE(t, edge_unit_vects[LIndex]);
441  V2SET(u, -t[1], t[0]);
442  UpdateBox(obr, hull_pnts[LIndex], hull_pnts[RIndex],
443  hull_pnts[BIndex], hull_pnts[TIndex], u);
444 
445  /* Mark edge visited and rotate the calipers. */
446  visited[LIndex] = 1;
447  if ((LIndex + 1) == hull_pnt_cnt) {
448  LIndex = 0;
449  } else {
450  LIndex = LIndex + 1;
451  }
452 
453  }
454  break;
455  case F_NONE:
456  /* The polygon is a rectangle. */
457  done = 1;
458  break;
459  }
460  }
461  bu_free(visited, "free visited");
462  bu_free(edge_unit_vects, "free visited");
463  bu_free(hull_pnts, "free visited");
464  }
465  }
466  return dim;
467 }
468 
469 int
470 bn_2d_obr(point2d_t *center, vect2d_t *u, vect2d_t *v, const point2d_t *pnts, int pnt_cnt)
471 {
472  struct obr_vals obr;
473  V2SET(obr.v, 0.0, 0.0);
474 
475  V2SET(*center, 0.0, 0.0);
476  V2SET(*u, 0.0, 0.0);
477  V2SET(*v, 0.0, 0.0);
478 
479  if (!pnts) return -1;
480  if (pnt_cnt <= 0) return -1;
481 
482  (void)bn_obr_calc(pnts, pnt_cnt, &obr);
483 
484  V2SET(*center, obr.center[0], obr.center[1]);
485  V2SET(*u, obr.u[0], obr.u[1]);
486  V2UNITIZE(*u);
487  V2SCALE(*u, *u, obr.extent0);
488  V2SET(*v, obr.v[0], obr.v[1]);
489  V2UNITIZE(*v);
490  V2SCALE(*v, *v, obr.extent1);
491 
492  return 0;
493 }
494 
495 int
496 bn_3d_coplanar_obr(point_t *center, vect_t *v1, vect_t *v2, const point_t *pnts, int pnt_cnt)
497 {
498  int ret = 0;
499  point_t origin_pnt;
500  vect_t u_axis, v_axis;
501  point2d_t obr_2d_center;
502  point2d_t obr_2d_v1, obr_2d_v2;
503  point2d_t *points_obr = NULL;
504  point_t *points_obr_3d = NULL;
505  point2d_t *points_tmp = NULL;
506  point_t tmp3d;
507  const point2d_t *const_points_tmp;
508 
509  if (!pnts || pnt_cnt <= 0) return -1;
510 
511  points_obr = (point2d_t *)bu_calloc(3 + 1, sizeof(point2d_t), "points_2d");
512  points_obr_3d = (point_t *)bu_calloc(3 + 1, sizeof(point_t), "points_3d");
513  points_tmp = (point2d_t *)bu_calloc(pnt_cnt + 1, sizeof(point2d_t), "points_2d");
514 
515  ret += coplanar_2d_coord_sys(&origin_pnt, &u_axis, &v_axis, pnts, pnt_cnt);
516  ret += coplanar_3d_to_2d(&points_tmp, (const point_t *)&origin_pnt, (const vect_t *)&u_axis, (const vect_t *)&v_axis, pnts, pnt_cnt);
517  if (ret)
518  return 0;
519 
520  const_points_tmp = (const point2d_t *)points_tmp;
521  ret = bn_2d_obr(&obr_2d_center, &obr_2d_v1, &obr_2d_v2, const_points_tmp, pnt_cnt);
522 
523  /* Set up the 2D point list so converting it will result in useful 3D points */
524  V2MOVE(points_obr[0], obr_2d_center);
525  V2ADD2(points_obr[1], obr_2d_v1, obr_2d_center);
526  V2ADD2(points_obr[2], obr_2d_v2, obr_2d_center);
527 
528  ret = coplanar_2d_to_3d(&points_obr_3d, (const point_t *)&origin_pnt, (const vect_t *)&u_axis, (const vect_t *)&v_axis, (const point2d_t *)points_obr, 3);
529 
530  VMOVE(*center, points_obr_3d[0]);
531 
532  /* Want to be able to add v1 and v2 to the 3D center to get obr points,
533  * so subtract the center out up front */
534  VSUB2(tmp3d, points_obr_3d[1], *center);
535  VMOVE(*v1, tmp3d);
536  VSUB2(tmp3d, points_obr_3d[2], *center);
537  VMOVE(*v2, tmp3d);
538 
539  bu_free(points_obr, "free 2d obr pnts");
540  bu_free(points_obr_3d, "free 3d obr pnts");
541  bu_free(points_tmp, "free 2d pnt projections");
542 
543  return 0;
544 }
545 
546 /*
547  * Local Variables:
548  * mode: C
549  * tab-width: 8
550  * indent-tabs-mode: t
551  * c-file-style: "stroustrup"
552  * End:
553  * ex: shiftwidth=4 tabstop=8
554  */
#define MAXDIST_AB(_minpt, _maxpt)
#define VSET(a, b, c, d)
Definition: color.c:53
Definition: obr.c:154
double dist_sq
dist * dist
Definition: tol.h:74
vect2d_t v
Definition: obr.c:157
#define F_BOTTOM
Definition: obr.c:66
#define BN_TOL_MAGIC
Definition: magic.h:74
Header file for the BRL-CAD common definitions.
fastf_t extent0
Definition: obr.c:158
HIDDEN int pnt2d_array_get_dimension(const point2d_t *pnts, int pnt_cnt, point2d_t *p_center, point2d_t *p1, point2d_t *p2)
Definition: obr.c:72
int bn_3d_coplanar_obr(point_t *center, vect_t *v1, vect_t *v2, const point_t *pnts, int pnt_cnt)
Uses the Rotating Calipers algorithm to find the minimum oriented bounding rectangle for a set of cop...
Definition: obr.c:496
#define HIDDEN
Definition: common.h:86
vect2d_t u
Definition: obr.c:156
int bn_2d_obr(point2d_t *center, vect2d_t *u, vect2d_t *v, const point2d_t *pnts, int pnt_cnt)
Routines for the computation of oriented bounding rectangles 2D and 3D.
Definition: obr.c:470
int bn_dist_pt2_lseg2(fastf_t *dist_sq, fastf_t pca[2], const point_t a, const point_t b, const point_t p, const struct bn_tol *tol)
Find the distance from a point P to a line segment described by the two endpoints A and B...
void * bu_calloc(size_t nelem, size_t elsize, const char *str)
Definition: malloc.c:321
HIDDEN void UpdateBox(struct obr_vals *obr, point2d_t left_pnt, point2d_t right_pnt, point2d_t bottom_pnt, point2d_t top_pnt, vect2d_t u)
Definition: obr.c:167
#define NEAR_ZERO(val, epsilon)
Definition: color.c:55
int coplanar_2d_coord_sys(point_t *origin_pnt, vect_t *u_axis, vect_t *v_axis, const point_t *points_3d, int n)
Find a 2D coordinate system for a set of co-planar 3D points.
Definition: util.c:29
#define BN_TOL_DIST
Definition: tol.h:109
Support for uniform tolerances.
Definition: tol.h:71
#define F_RIGHT
Definition: obr.c:67
#define F_LEFT
Definition: obr.c:69
fastf_t extent1
Definition: obr.c:159
HIDDEN int bn_obr_calc(const point2d_t *pnts, int pnt_cnt, struct obr_vals *obr)
Definition: obr.c:201
int coplanar_3d_to_2d(point2d_t **points_2d, const point_t *origin_pnt, const vect_t *u_axis, const vect_t *v_axis, const point_t *points_3d, int n)
Find 2D coordinates for a set of co-planar 3D points.
Definition: util.c:93
#define A
Definition: msr.c:51
void bu_free(void *ptr, const char *str)
Definition: malloc.c:328
int coplanar_2d_to_3d(point_t **points_3d, const point_t *origin_pnt, const vect_t *u_axis, const vect_t *v_axis, const point2d_t *points_2d, int n)
Find 3D coordinates for a set of 2D points given a coordinate system.
Definition: util.c:113
#define F_NONE
Definition: obr.c:65
double fastf_t
Definition: defines.h:300
fastf_t area
Definition: obr.c:155
#define F_TOP
Definition: obr.c:68
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
point2d_t center
Definition: obr.c:160