6 * PCB, interactive printed circuit board design
7 * Copyright (C) 1994,1995,1996 Thomas Nau
8 * Copyright (C) 1998,1999,2000,2001,2002,2003,2004 harry eaton
10 * This program is free software; you can redistribute it and/or modify
11 * it under the terms of the GNU General Public License as published by
12 * the Free Software Foundation; either version 2 of the License, or
13 * (at your option) any later version.
15 * This program is distributed in the hope that it will be useful,
16 * but WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
18 * GNU General Public License for more details.
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
24 * Contact addresses for paper mail and Email:
25 * harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA
26 * haceaton@aplcomm.jhuapl.edu
30 /* this file, rtree.c, was written and is
31 * Copyright (c) 2004, harry eaton
34 /* implements r-tree structures.
35 * these should be much faster for the auto-router
36 * because the recursive search is much more efficient
37 * and that's where the auto-router spends all its time.
58 #ifdef HAVE_LIBDMALLOC
66 /* All rectangles are closed on the bottom left and open on the
67 * top right. i.e. they contain one corner point, but not the other.
70 /* the number of entries in each rtree node
71 * 4 - 7 seem to be pretty good settings
75 /* it seems that sorting the leaf order slows us down
76 * but sometimes gives better routes
81 #define DELETE_BY_POINTER
82 typedef long long bigun
;
86 const BoxType
*bptr
; /* pointer to the box */
87 BoxType bounds
; /* copy of the box for locality of reference */
92 BoxType box
; /* bounds rectangle of this node */
93 struct rtree_node
*parent
; /* parent of this node, NULL = root */
96 unsigned is_leaf
:1; /* this is a leaf node */
97 unsigned manage
:31; /* true==should free 'rect.bptr' if node is destroyed */
102 struct rtree_node
*kids
[M_SIZE
+ 1]; /* when not leaf */
103 Rentry rects
[M_SIZE
+ 1]; /* when leaf */
109 __r_node_is_good (struct rtree_node
*node
)
113 Boolean last
= False
;
117 for (i
= 0; i
< M_SIZE
; i
++)
119 if (node
->flags
.is_leaf
)
121 if (!node
->u
.rects
[i
].bptr
)
126 /* check that once one entry is empty, all the rest are too */
127 if (node
->u
.rects
[i
].bptr
&& last
)
129 /* check that the box makes sense */
130 if (node
->box
.X1
> node
->box
.X2
)
132 if (node
->box
.Y1
> node
->box
.Y2
)
134 /* check that bounds is the same as the pointer */
135 if (node
->u
.rects
[i
].bounds
.X1
!= node
->u
.rects
[i
].bptr
->X1
)
137 if (node
->u
.rects
[i
].bounds
.Y1
!= node
->u
.rects
[i
].bptr
->Y1
)
139 if (node
->u
.rects
[i
].bounds
.X2
!= node
->u
.rects
[i
].bptr
->X2
)
141 if (node
->u
.rects
[i
].bounds
.Y2
!= node
->u
.rects
[i
].bptr
->Y2
)
143 /* check that entries are within node bounds */
144 if (node
->u
.rects
[i
].bounds
.X1
< node
->box
.X1
)
146 if (node
->u
.rects
[i
].bounds
.X2
> node
->box
.X2
)
148 if (node
->u
.rects
[i
].bounds
.Y1
< node
->box
.Y1
)
150 if (node
->u
.rects
[i
].bounds
.Y2
> node
->box
.Y2
)
155 if (!node
->u
.kids
[i
])
160 /* make sure all children are the same type */
162 kind
= node
->u
.kids
[i
]->flags
.is_leaf
;
163 else if (kind
!= node
->u
.kids
[i
]->flags
.is_leaf
)
165 /* check that once one entry is empty, all the rest are too */
166 if (node
->u
.kids
[i
] && last
)
168 /* check that entries are within node bounds */
169 if (node
->u
.kids
[i
]->box
.X1
< node
->box
.X1
)
171 if (node
->u
.kids
[i
]->box
.X2
> node
->box
.X2
)
173 if (node
->u
.kids
[i
]->box
.Y1
< node
->box
.Y1
)
175 if (node
->u
.kids
[i
]->box
.Y2
> node
->box
.Y2
)
180 /* check that we're completely in the parent's bounds */
183 if (node
->parent
->box
.X1
> node
->box
.X1
)
185 if (node
->parent
->box
.X2
< node
->box
.X2
)
187 if (node
->parent
->box
.Y1
> node
->box
.Y1
)
189 if (node
->parent
->box
.Y2
< node
->box
.Y2
)
192 /* make sure overflow is empty */
193 if (!node
->flags
.is_leaf
&& node
->u
.kids
[i
])
195 if (node
->flags
.is_leaf
&& node
->u
.rects
[i
].bptr
)
201 /* check the whole tree from this node down for consistency */
203 __r_tree_is_good (struct rtree_node
*node
)
209 if (!__r_node_is_good (node
))
211 if (node
->flags
.is_leaf
)
213 for (i
= 0; i
< M_SIZE
; i
++)
215 if (!__r_tree_is_good (node
->u
.kids
[i
]))
222 /* print out the tree */
224 __r_dump_tree (struct rtree_node
*node
, int depth
)
236 (node
->box
.X2
- node
->box
.X1
) * (double) (node
->box
.Y2
- node
->box
.Y1
);
238 for (i
= 0; i
< depth
; i
++)
240 if (!node
->flags
.is_leaf
)
242 printf ("p=0x%p node X(%d, %d) Y(%d, %d)\n", (void *) node
,
243 node
->box
.X1
, node
->box
.X2
, node
->box
.Y1
, node
->box
.Y2
);
245 gdk_gc_set_line_attributes (Output
.fgGC
, 4,
246 GDK_LINE_SOLID
, GDK_CAP_ROUND
,
249 if (depth
< max_layer
+ 1)
250 gdk_gc_set_foreground (Output
.fgGC
, (LAYER_PTR (depth
)->Color
));
252 gdk_gc_set_foreground (Output
.fgGC
, PCB
->WarnColor
);
253 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
254 node
->box
.X1
, node
->box
.Y1
, node
->box
.X2
, node
->box
.Y1
);
255 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
256 node
->box
.X2
, node
->box
.Y1
, node
->box
.X2
, node
->box
.Y2
);
257 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
258 node
->box
.X2
, node
->box
.Y2
, node
->box
.X1
, node
->box
.Y2
);
259 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
260 node
->box
.X1
, node
->box
.Y2
, node
->box
.X1
, node
->box
.Y1
);
266 gdk_gc_set_line_attributes (Output
.fgGC
, 2,
267 GDK_LINE_SOLID
, GDK_CAP_ROUND
,
269 gdk_gc_set_foreground (Output
.fgGC
, PCB
->MaskColor
);
270 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
271 node
->box
.X1
, node
->box
.Y1
, node
->box
.X2
, node
->box
.Y1
);
272 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
273 node
->box
.X2
, node
->box
.Y1
, node
->box
.X2
, node
->box
.Y2
);
274 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
275 node
->box
.X2
, node
->box
.Y2
, node
->box
.X1
, node
->box
.Y2
);
276 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
277 node
->box
.X1
, node
->box
.Y2
, node
->box
.X1
, node
->box
.Y1
);
279 printf ("p=0x%p leaf manage(%02x) X(%d, %d) Y(%d, %d)\n", (void *) node
,
280 node
->flags
.manage
, node
->box
.X1
, node
->box
.X2
, node
->box
.Y1
,
282 for (j
= 0; j
< M_SIZE
; j
++)
284 if (!node
->u
.rects
[j
].bptr
)
287 (node
->u
.rects
[j
].bounds
.X2
-
288 node
->u
.rects
[j
].bounds
.X1
) *
289 (double) (node
->u
.rects
[j
].bounds
.Y2
-
290 node
->u
.rects
[j
].bounds
.Y1
);
293 gdk_gc_set_line_attributes (Output
.fgGC
, 1,
294 GDK_LINE_SOLID
, GDK_CAP_ROUND
,
296 gdk_gc_set_foreground (Output
.fgGC
, PCB
->ViaSelectedColor
);
297 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
298 node
->u
.rects
[j
].bounds
.X1
, node
->u
.rects
[j
].bounds
.Y1
,
299 node
->u
.rects
[j
].bounds
.X2
, node
->u
.rects
[j
].bounds
.Y1
);
300 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
301 node
->u
.rects
[j
].bounds
.X2
, node
->u
.rects
[j
].bounds
.Y1
,
302 node
->u
.rects
[j
].bounds
.X2
, node
->u
.rects
[j
].bounds
.Y2
);
303 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
304 node
->u
.rects
[j
].bounds
.X2
, node
->u
.rects
[j
].bounds
.Y2
,
305 node
->u
.rects
[j
].bounds
.X1
, node
->u
.rects
[j
].bounds
.Y2
);
306 XDrawCLine (Output
.top_window
->window
, Output
.fgGC
,
307 node
->u
.rects
[j
].bounds
.X1
, node
->u
.rects
[j
].bounds
.Y2
,
308 node
->u
.rects
[j
].bounds
.X1
, node
->u
.rects
[j
].bounds
.Y1
);
310 for (i
= 0; i
< depth
+ 1; i
++)
312 printf ("entry 0x%p X(%d, %d) Y(%d, %d)\n",
313 (void *) (node
->u
.rects
[j
].bptr
),
314 node
->u
.rects
[j
].bounds
.X1
, node
->u
.rects
[j
].bounds
.X2
,
315 node
->u
.rects
[j
].bounds
.Y1
, node
->u
.rects
[j
].bounds
.Y2
);
319 for (i
= 0; i
< M_SIZE
; i
++)
321 __r_dump_tree (node
->u
.kids
[i
], depth
+ 1);
323 printf ("average box area is %g\n", area
/ count
);
327 /* Sort the children or entries of a node
328 * according to the largest side.
332 cmp_box (const BoxType
* a
, const BoxType
* b
)
334 /* compare two box coordinates so that the __r_search
335 * will fail at the earliest comparison possible.
336 * It needs to see the biggest X1 first, then the
337 * smallest X2, the biggest Y1 and smallest Y2
357 sort_node (struct rtree_node
*node
)
359 if (node
->flags
.is_leaf
)
361 register Rentry
*r
, *i
, temp
;
363 for (r
= &node
->u
.rects
[1]; r
->bptr
; r
++)
367 while (i
>= &node
->u
.rects
[0])
369 if (cmp_box (&i
->bounds
, &r
->bounds
))
380 register struct rtree_node
**r
, **i
, *temp
;
382 for (r
= &node
->u
.kids
[1]; *r
; r
++)
386 while (i
>= &node
->u
.kids
[0])
388 if (cmp_box (&(*i
)->box
, &(*r
)->box
))
402 /* set the node bounds large enough to encompass all
403 * of the children's rectangles
406 adjust_bounds (struct rtree_node
*node
)
411 assert (node
->u
.kids
[0]);
412 if (node
->flags
.is_leaf
)
414 node
->box
= node
->u
.rects
[0].bounds
;
415 for (i
= 1; i
< M_SIZE
+ 1; i
++)
417 if (!node
->u
.rects
[i
].bptr
)
419 MAKEMIN (node
->box
.X1
, node
->u
.rects
[i
].bounds
.X1
);
420 MAKEMAX (node
->box
.X2
, node
->u
.rects
[i
].bounds
.X2
);
421 MAKEMIN (node
->box
.Y1
, node
->u
.rects
[i
].bounds
.Y1
);
422 MAKEMAX (node
->box
.Y2
, node
->u
.rects
[i
].bounds
.Y2
);
427 node
->box
= node
->u
.kids
[0]->box
;
428 for (i
= 1; i
< M_SIZE
+ 1; i
++)
430 if (!node
->u
.kids
[i
])
432 MAKEMIN (node
->box
.X1
, node
->u
.kids
[i
]->box
.X1
);
433 MAKEMAX (node
->box
.X2
, node
->u
.kids
[i
]->box
.X2
);
434 MAKEMIN (node
->box
.Y1
, node
->u
.kids
[i
]->box
.Y1
);
435 MAKEMAX (node
->box
.Y2
, node
->u
.kids
[i
]->box
.Y2
);
440 /* create an r-tree from an unsorted list of boxes.
441 * the r-tree will keep pointers into
442 * it, so don't free the box list until you've called r_destroy_tree.
443 * if you set 'manage' to true, r_destroy_tree will free your boxlist.
446 r_create_tree (const BoxType
* boxlist
[], int N
, int manage
)
449 struct rtree_node
*node
;
453 rtree
= calloc (1, sizeof (*rtree
));
454 /* start with a single empty leaf node */
455 node
= calloc (1, sizeof (*node
));
456 node
->flags
.is_leaf
= 1;
459 /* simple, just insert all of the boxes! */
460 for (i
= 0; i
< N
; i
++)
463 r_insert_entry (rtree
, boxlist
[i
], manage
);
466 assert (__r_tree_is_good (rtree
->root
));
472 __r_destroy_tree (struct rtree_node
*node
)
476 if (node
->flags
.is_leaf
)
477 for (i
= 0; i
< M_SIZE
; i
++)
479 if (!node
->u
.rects
[i
].bptr
)
481 if (node
->flags
.manage
& flag
)
482 free ((void *) node
->u
.rects
[i
].bptr
);
486 for (i
= 0; i
< M_SIZE
; i
++)
488 if (!node
->u
.kids
[i
])
490 __r_destroy_tree (node
->u
.kids
[i
]);
495 /* free the memory associated with an rtree. */
497 r_destroy_tree (rtree_t
** rtree
)
500 __r_destroy_tree ((*rtree
)->root
);
507 int (*check_it
) (const BoxType
* region
, void *cl
);
508 int (*found_it
) (const BoxType
* box
, void *cl
);
512 /* most of the auto-routing time is spent in this routine
513 * so some careful thought has been given to maximizing the speed
517 __r_search (struct rtree_node
*node
, const BoxType
* query
, r_arg
* arg
)
520 /** assert that starting_region is well formed */
521 assert (query
->X1
<= query
->X2
&& query
->Y1
<= query
->Y2
);
522 assert (node
->box
.X1
< query
->X2
&& node
->box
.X2
> query
->X1
&&
523 node
->box
.Y1
< query
->Y2
&& node
->box
.Y2
> query
->X1
);
525 /** assert that node is well formed */
526 assert (__r_node_is_good (node
));
528 /* the check for bounds is done before entry. This saves the overhead
529 * of building/destroying the stack frame for each bounds that fails
530 * to intersect, which is the most common condition.
532 if (node
->flags
.is_leaf
)
535 if (arg
->found_it
) /* test this once outside of loop */
537 register int seen
= 0;
538 for (i
= 0; node
->u
.rects
[i
].bptr
; i
++)
540 if ((node
->u
.rects
[i
].bounds
.X1
< query
->X2
) &&
541 (node
->u
.rects
[i
].bounds
.X2
> query
->X1
) &&
542 (node
->u
.rects
[i
].bounds
.Y1
< query
->Y2
) &&
543 (node
->u
.rects
[i
].bounds
.Y2
> query
->Y1
) &&
544 arg
->found_it (node
->u
.rects
[i
].bptr
, arg
->closure
))
551 register int seen
= 0;
552 for (i
= 0; node
->u
.rects
[i
].bptr
; i
++)
554 if ((node
->u
.rects
[i
].bounds
.X1
< query
->X2
) &&
555 (node
->u
.rects
[i
].bounds
.X2
> query
->X1
) &&
556 (node
->u
.rects
[i
].bounds
.Y1
< query
->Y2
) &&
557 (node
->u
.rects
[i
].bounds
.Y2
> query
->Y1
))
564 /* not a leaf, recurse on lower nodes */
568 struct rtree_node
**n
;
569 for (n
= &node
->u
.kids
[0]; *n
; n
++)
571 if ((*n
)->box
.X1
>= query
->X2
||
572 (*n
)->box
.X2
<= query
->X1
||
573 (*n
)->box
.Y1
>= query
->Y2
|| (*n
)->box
.Y2
<= query
->Y1
||
574 !arg
->check_it (&(*n
)->box
, arg
->closure
))
576 seen
+= __r_search (*n
, query
, arg
);
583 struct rtree_node
**n
;
584 for (n
= &node
->u
.kids
[0]; *n
; n
++)
586 if ((*n
)->box
.X1
>= query
->X2
||
587 (*n
)->box
.X2
<= query
->X1
||
588 (*n
)->box
.Y1
>= query
->Y2
|| (*n
)->box
.Y2
<= query
->Y1
)
590 seen
+= __r_search (*n
, query
, arg
);
596 /* Parameterized search in the rtree.
597 * Returns the number of rectangles found.
598 * calls found_rectangle for each intersection seen
599 * and calls check_region with the current sub-region
600 * to see whether deeper searching is desired
603 r_search (rtree_t
* rtree
, const BoxType
* query
,
604 int (*check_region
) (const BoxType
* region
, void *cl
),
605 int (*found_rectangle
) (const BoxType
* box
, void *cl
), void *cl
)
609 if (!rtree
|| rtree
->size
< 1)
614 if (query
->X2
< query
->X1
|| query
->Y2
< query
->Y1
)
617 /* check this box. If it's not touched we're done here */
618 if (rtree
->root
->box
.X1
>= query
->X2
||
619 rtree
->root
->box
.X2
<= query
->X1
||
620 rtree
->root
->box
.Y1
>= query
->Y2
621 || rtree
->root
->box
.Y2
<= query
->Y1
)
623 arg
.check_it
= check_region
;
624 arg
.found_it
= found_rectangle
;
626 return __r_search (rtree
->root
, query
, &arg
);
630 arg
.check_it
= check_region
;
631 arg
.found_it
= found_rectangle
;
633 return __r_search (rtree
->root
, &rtree
->root
->box
, &arg
);
637 /*------ r_region_is_empty ------*/
639 __r_region_is_empty_rect_in_reg (const BoxType
* box
, void *cl
)
641 jmp_buf *envp
= (jmp_buf *) cl
;
642 longjmp (*envp
, 1); /* found one! */
645 /* return 0 if there are any rectangles in the given region. */
647 r_region_is_empty (rtree_t
* rtree
, const BoxType
* region
)
654 r
= r_search (rtree
, region
, NULL
, __r_region_is_empty_rect_in_reg
, &env
);
655 assert (r
== 0); /* otherwise longjmp would have been called */
656 return 1; /* no rectangles found */
664 /* split the node into two nodes putting clusters in each
665 * use the k-means clustering algorithm
668 find_clusters (struct rtree_node
*node
)
670 float total_a
, total_b
;
671 float a_X
, a_Y
, b_X
, b_Y
;
672 Boolean belong
[M_SIZE
+ 1];
673 struct centroid center
[M_SIZE
+ 1];
674 int clust_a
, clust_b
, tries
;
675 int a_manage
= 0, b_manage
= 0;
676 int i
, old_ax
, old_ay
, old_bx
, old_by
;
677 struct rtree_node
*new_node
;
680 for (i
= 0; i
< M_SIZE
+ 1; i
++)
682 if (node
->flags
.is_leaf
)
683 b
= &(node
->u
.rects
[i
].bounds
);
685 b
= &(node
->u
.kids
[i
]->box
);
686 center
[i
].x
= 0.5 * (b
->X1
+ b
->X2
);
687 center
[i
].y
= 0.5 * (b
->Y1
+ b
->Y2
);
688 /* adding 1 prevents zero area */
689 center
[i
].area
= 1. + (float) (b
->X2
- b
->X1
) * (float) (b
->Y2
- b
->Y1
);
691 /* starting 'A' cluster center */
694 /* starting 'B' cluster center */
695 b_X
= center
[M_SIZE
].x
;
696 b_Y
= center
[M_SIZE
].y
;
697 /* don't allow the same cluster centers */
698 if (b_X
== a_X
&& b_Y
== a_Y
)
703 for (tries
= 0; tries
< M_SIZE
; tries
++)
709 clust_a
= clust_b
= 0;
710 for (i
= 0; i
< M_SIZE
+ 1; i
++)
714 dist1
= SQUARE (a_X
- center
[i
].x
) + SQUARE (a_Y
- center
[i
].y
);
715 dist2
= SQUARE (b_X
- center
[i
].x
) + SQUARE (b_Y
- center
[i
].y
);
716 if (dist1
* (clust_a
+ M_SIZE
/ 2) < dist2
* (clust_b
+ M_SIZE
/ 2))
727 /* kludge to fix degenerate cases */
728 if (clust_a
== M_SIZE
+ 1)
729 belong
[M_SIZE
/ 2] = False
;
730 else if (clust_b
== M_SIZE
+ 1)
731 belong
[M_SIZE
/ 2] = True
;
732 /* compute new center of gravity of clusters */
733 total_a
= total_b
= 0;
734 a_X
= a_Y
= b_X
= b_Y
= 0;
735 for (i
= 0; i
< M_SIZE
+ 1; i
++)
739 a_X
+= center
[i
].x
* center
[i
].area
;
740 a_Y
+= center
[i
].y
* center
[i
].area
;
741 total_a
+= center
[i
].area
;
745 b_X
+= center
[i
].x
* center
[i
].area
;
746 b_Y
+= center
[i
].y
* center
[i
].area
;
747 total_b
+= center
[i
].area
;
754 if (old_ax
== (int) a_X
&& old_ay
== (int) a_Y
&&
755 old_bx
== (int) b_X
&& old_by
== (int) b_Y
)
758 /* Now 'belong' has the partition map */
759 new_node
= calloc (1, sizeof (*new_node
));
760 new_node
->parent
= node
->parent
;
761 new_node
->flags
.is_leaf
= node
->flags
.is_leaf
;
762 clust_a
= clust_b
= 0;
763 if (node
->flags
.is_leaf
)
765 int flag
, a_flag
, b_flag
;
766 flag
= a_flag
= b_flag
= 1;
767 for (i
= 0; i
< M_SIZE
+ 1; i
++)
771 node
->u
.rects
[clust_a
++] = node
->u
.rects
[i
];
772 if (node
->flags
.manage
& flag
)
778 new_node
->u
.rects
[clust_b
++] = node
->u
.rects
[i
];
779 if (node
->flags
.manage
& flag
)
788 for (i
= 0; i
< M_SIZE
+ 1; i
++)
791 node
->u
.kids
[clust_a
++] = node
->u
.kids
[i
];
794 node
->u
.kids
[i
]->parent
= new_node
;
795 new_node
->u
.kids
[clust_b
++] = node
->u
.kids
[i
];
799 node
->flags
.manage
= a_manage
;
800 new_node
->flags
.manage
= b_manage
;
801 assert (clust_a
!= 0);
802 assert (clust_b
!= 0);
803 if (node
->flags
.is_leaf
)
804 for (; clust_a
< M_SIZE
+ 1; clust_a
++)
805 node
->u
.rects
[clust_a
].bptr
= NULL
;
807 for (; clust_a
< M_SIZE
+ 1; clust_a
++)
808 node
->u
.kids
[clust_a
] = NULL
;
809 adjust_bounds (node
);
811 adjust_bounds (new_node
);
812 sort_node (new_node
);
816 /* split a node according to clusters
819 split_node (struct rtree_node
*node
)
822 struct rtree_node
*new_node
;
825 assert (node
->flags
.is_leaf
? (void *) node
->u
.rects
[M_SIZE
].
826 bptr
: (void *) node
->u
.kids
[M_SIZE
]);
827 new_node
= find_clusters (node
);
828 if (node
->parent
== NULL
) /* split root node */
830 struct rtree_node
*second
;
832 second
= calloc (1, sizeof (*second
));
834 if (!second
->flags
.is_leaf
)
835 for (i
= 0; i
< M_SIZE
; i
++)
836 if (second
->u
.kids
[i
])
837 second
->u
.kids
[i
]->parent
= second
;
838 node
->flags
.is_leaf
= 0;
839 node
->flags
.manage
= 0;
840 second
->parent
= new_node
->parent
= node
;
841 node
->u
.kids
[0] = new_node
;
842 node
->u
.kids
[1] = second
;
843 for (i
= 2; i
< M_SIZE
+ 1; i
++)
844 node
->u
.kids
[i
] = NULL
;
845 adjust_bounds (node
);
848 assert (__r_tree_is_good (node
));
852 for (i
= 0; i
< M_SIZE
; i
++)
853 if (!node
->parent
->u
.kids
[i
])
855 node
->parent
->u
.kids
[i
] = new_node
;
857 assert (__r_node_is_good (node
));
858 assert (__r_node_is_good (new_node
));
863 assert (__r_node_is_good (node
->parent
));
865 sort_node (node
->parent
);
868 split_node (node
->parent
);
872 contained (struct rtree_node
*node
, const BoxType
* query
)
874 if (node
->box
.X1
> query
->X1
|| node
->box
.X2
< query
->X2
||
875 node
->box
.Y1
> query
->Y1
|| node
->box
.Y2
< query
->Y2
)
882 penalty (struct rtree_node
*node
, const BoxType
* query
)
886 /* Compute the area penalty for inserting here and return.
887 * The penalty is the increase in area necessary
888 * to include the query->
890 score
= (MAX (node
->box
.X2
, query
->X2
) - MIN (node
->box
.X1
, query
->X1
));
892 (MAX (node
->box
.Y2
, query
->Y2
) - MIN (node
->box
.Y1
, query
->Y1
));
894 ((long long) node
->box
.X2
-
895 node
->box
.X1
) * ((long long) node
->box
.Y2
- node
->box
.Y1
);
900 __r_insert_node (struct rtree_node
*node
, const BoxType
* query
,
901 int manage
, Boolean force
)
905 assert (__r_node_is_good (node
));
907 /* Ok, at this point we must already enclose the query or we're forcing
908 * this node to expand to enclose it, so if we're a leaf, simply store
912 if (node
->flags
.is_leaf
)
918 register int flag
= 1;
920 for (i
= 0; i
< M_SIZE
; i
++)
922 if (!node
->u
.rects
[i
].bptr
)
926 node
->flags
.manage
|= flag
;
930 for (i
= 0; i
< M_SIZE
; i
++)
931 if (!node
->u
.rects
[i
].bptr
)
934 /* the node always has an extra space available */
935 node
->u
.rects
[i
].bptr
= query
;
936 node
->u
.rects
[i
].bounds
= *query
;
937 /* first entry in node determines initial bounding box */
942 MAKEMIN (node
->box
.X1
, query
->X1
);
943 MAKEMAX (node
->box
.X2
, query
->X2
);
944 MAKEMIN (node
->box
.Y1
, query
->Y1
);
945 MAKEMAX (node
->box
.Y2
, query
->Y2
);
952 /* we must split the node */
959 struct rtree_node
*best_node
;
960 long long score
, best_score
;
964 MAKEMIN (node
->box
.X1
, query
->X1
);
965 MAKEMAX (node
->box
.X2
, query
->X2
);
966 MAKEMIN (node
->box
.Y1
, query
->Y1
);
967 MAKEMAX (node
->box
.Y2
, query
->Y2
);
970 /* this node encloses it, but it's not a leaf, so descend the tree */
972 /* First check if any children actually encloses it */
973 assert (node
->u
.kids
[0]);
974 for (i
= 0; i
< M_SIZE
; i
++)
976 if (!node
->u
.kids
[i
])
978 if (contained (node
->u
.kids
[i
], query
))
980 __r_insert_node (node
->u
.kids
[i
], query
, manage
, False
);
986 /* see if there is room for a new leaf node */
987 if (node
->u
.kids
[0]->flags
.is_leaf
&& i
< M_SIZE
)
989 struct rtree_node
*new_node
;
990 new_node
= calloc (1, sizeof (*new_node
));
991 new_node
->parent
= node
;
992 new_node
->flags
.is_leaf
= True
;
993 node
->u
.kids
[i
] = new_node
;
994 new_node
->u
.rects
[0].bptr
= query
;
995 new_node
->u
.rects
[0].bounds
= *query
;
996 new_node
->box
= *query
;
998 new_node
->flags
.manage
= 1;
1003 /* Ok, so we're still here - look for the best child to push it into */
1004 best_score
= penalty (node
->u
.kids
[0], query
);
1005 best_node
= node
->u
.kids
[0];
1006 for (i
= 1; i
< M_SIZE
; i
++)
1008 if (!node
->u
.kids
[i
])
1010 score
= penalty (node
->u
.kids
[i
], query
);
1011 if (score
< best_score
)
1014 best_node
= node
->u
.kids
[i
];
1017 __r_insert_node (best_node
, query
, manage
, True
);
1024 r_insert_entry (rtree_t
* rtree
, const BoxType
* which
, int man
)
1027 assert (which
->X1
<= which
->X2
);
1028 assert (which
->Y1
<= which
->Y2
);
1029 /* recursively search the tree for the best leaf node */
1030 assert (rtree
->root
);
1031 __r_insert_node (rtree
->root
, which
, man
,
1032 rtree
->root
->box
.X1
> which
->X1
1033 || rtree
->root
->box
.X2
< which
->X2
1034 || rtree
->root
->box
.Y1
> which
->Y1
1035 || rtree
->root
->box
.Y2
< which
->Y2
);
1040 __r_delete (rtree_t
* seed
, struct rtree_node
*node
, const BoxType
* query
)
1042 int i
, flag
, mask
, a
;
1044 /* the tree might be inconsistent during delete */
1045 if (query
->X1
< node
->box
.X1
|| query
->Y1
< node
->box
.Y1
1046 || query
->X2
> node
->box
.X2
|| query
->Y2
> node
->box
.Y2
)
1048 if (!node
->flags
.is_leaf
)
1050 for (i
= 0; i
< M_SIZE
; i
++)
1052 /* if this is us being removed, free and copy over */
1053 if (node
->u
.kids
[i
] == (struct rtree_node
*) query
)
1055 free ((void *) query
);
1056 for (; i
< M_SIZE
; i
++)
1058 node
->u
.kids
[i
] = node
->u
.kids
[i
+ 1];
1059 if (!node
->u
.kids
[i
])
1062 /* nobody home here now ? */
1063 if (!node
->u
.kids
[0])
1067 /* wow, the root is empty! */
1068 node
->flags
.is_leaf
= 1;
1069 /* changing type of node, be sure it's all zero */
1070 for (i
= 1; i
< M_SIZE
+ 1; i
++)
1071 node
->u
.rects
[i
].bptr
= NULL
;
1074 return (__r_delete (seed
, node
->parent
, &node
->box
));
1077 /* propegate boundary adjust upward */
1080 adjust_bounds (node
);
1081 node
= node
->parent
;
1085 if (node
->u
.kids
[i
])
1087 if (__r_delete (seed
, node
->u
.kids
[i
], query
))
1095 /* leaf node here */
1098 for (i
= 0; i
< M_SIZE
; i
++)
1100 #ifdef DELETE_BY_POINTER
1101 if (!node
->u
.rects
[i
].bptr
|| node
->u
.rects
[i
].bptr
== query
)
1103 if (node
->u
.rects
[i
].bounds
.X1
== query
->X1
&&
1104 node
->u
.rects
[i
].bounds
.X2
== query
->X2
&&
1105 node
->u
.rects
[i
].bounds
.Y1
== query
->Y1
&&
1106 node
->u
.rects
[i
].bounds
.Y2
== query
->Y2
)
1112 if (!node
->u
.rects
[i
].bptr
)
1113 return False
; /* not at this leaf */
1114 if (node
->flags
.manage
& a
)
1116 free ((void *) node
->u
.rects
[i
].bptr
);
1117 node
->u
.rects
[i
].bptr
= NULL
;
1119 /* squeeze the manage flags together */
1120 flag
= node
->flags
.manage
& mask
;
1121 mask
= (~mask
) << 1;
1122 node
->flags
.manage
= flag
| ((node
->flags
.manage
& mask
) >> 1);
1123 /* remove the entry */
1124 for (; i
< M_SIZE
; i
++)
1126 node
->u
.rects
[i
] = node
->u
.rects
[i
+ 1];
1127 if (!node
->u
.rects
[i
].bptr
)
1130 if (!node
->u
.rects
[0].bptr
)
1133 __r_delete (seed
, node
->parent
, &node
->box
);
1137 /* propagate boundary adjustment upward */
1140 adjust_bounds (node
);
1141 node
= node
->parent
;
1147 r_delete_entry (rtree_t
* rtree
, const BoxType
* box
)
1153 r
= __r_delete (rtree
, rtree
->root
, box
);
1157 assert (__r_tree_is_good (rtree
->root
));
1163 __r_sub (struct rtree_node
*node
, const BoxType
* b
, const BoxType
* a
,
1168 if (node
->flags
.is_leaf
)
1170 for (i
= 0; i
< M_SIZE
; i
++)
1171 if (node
->u
.rects
[i
].bptr
== b
)
1173 node
->u
.rects
[i
].bptr
= a
;
1174 assert (a
->X1
== node
->u
.rects
[i
].bounds
.X1
);
1175 assert (a
->X2
== node
->u
.rects
[i
].bounds
.X2
);
1176 assert (a
->Y1
== node
->u
.rects
[i
].bounds
.Y1
);
1177 assert (a
->Y2
== node
->u
.rects
[i
].bounds
.Y2
);
1182 for (i
= 0; i
< M_SIZE
; i
++)
1183 if (node
->u
.kids
[i
] && __r_sub (node
->u
.kids
[i
], b
, a
, e
))
1190 r_substitute (rtree_t
* rtree
, const BoxType
* before
, const BoxType
* after
)
1194 if (before
== after
)
1196 if (setjmp (env
) == 0)
1197 __r_sub (rtree
->root
, before
, after
, &env
);