Prototypes for r-tree routines. More...

#include "global.h"

Include dependency graph for rtree.h:

This graph shows which files directly or indirectly include this file:

Functions
rtree_t *	r_create_tree (const BoxType *boxlist[], int N, int manage)
	Create an r-tree from an unsorted list of boxes.
void	r_destroy_tree (rtree_t **rtree)
	Free the memory associated with an rtree.
bool	r_delete_entry (rtree_t rtree, const BoxType which)
void	r_insert_entry (rtree_t rtree, const BoxType which, int manage)
int	r_search (rtree_t rtree, const BoxType starting_region, int(region_in_search)(const BoxType region, void cl), int(rectangle_in_region)(const BoxType box, void cl), void *closure)
	Parameterized search in the rtree.
static int	r_search_pt (rtree_t rtree, const PointType pt, int radius, int(region_in_search)(const BoxType region, void cl), int(rectangle_in_region)(const BoxType box, void cl), void *closure)
int	r_region_is_empty (rtree_t rtree, const BoxType region)
	Special-purpose searches build upon r_search.
void	__r_dump_tree (struct rtree_node *, int)
	Print out the tree.

Detailed Description

Prototypes for r-tree routines.

Author:: This file, rtree.h, was written and is Copyright (c) 2004 harry eaton, it's based on C. Scott's kdtree.h template.

Copyright.

PCB, interactive printed circuit board design

This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.

Contact addresses for paper mail and Email:

harry eaton, 6697 Buttonhole Ct, Columbia, MD 21044 USA

haceaton@aplcomm.jhuapl.edu

Definition in file rtree.h.

Function Documentation

void __r_dump_tree	(	struct rtree_node *	,
		int
	)

Print out the tree.

Definition at line 227 of file rtree.c.

References __r_dump_tree(), rtree_node::box, rtree_node::flags, rtree_node::is_leaf, rtree_node::kids, M_SIZE, rtree_node::manage, rtree_node::u, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by __r_dump_tree(), and ReportDialog().

Here is the call graph for this function:

rtree_t* r_create_tree	(	const BoxType *	boxlist[],
		int	N,
		int	manage
	)

Create an r-tree from an unsorted list of boxes.

Create an rtree from the list of boxes. If 'manage' is true, then the tree will take ownership of 'boxlist' and free it when the tree is destroyed.

The r-tree will keep pointers into it, so don't free the box list until you've called r_destroy_tree.

If you set 'manage' to true, r_destroy_tree will free your boxlist.

Definition at line 425 of file rtree.c.

References __r_tree_is_good(), rtree_node::flags, rtree_node::is_leaf, N, node, rtree_node::parent, r_insert_entry(), and rtree::root.

Referenced by AddPolygonToBuffer(), ComputeCost(), CopyAttachedPolygonToLayer(), CopyPolygon(), CreateNewArcOnLayer(), CreateNewLineOnLayer(), CreateNewPolygonFromRectangle(), CreateNewRat(), CreateNewText(), CreateNewVia(), CreateRouteData(), InsCntr(), InsertHoles(), make_edge_tree(), MoveArcToBuffer(), MoveArcToLayerLowLevel(), MoveLineToBuffer(), MoveLineToLayerLowLevel(), MovePolygonToBuffer(), MovePolygonToLayerLowLevel(), MoveRatToBuffer(), MoveTextToBuffer(), MoveTextToLayerLowLevel(), MoveViaToBuffer(), mtspace_create(), poly_Copy0(), poly_Init(), PolyToPolygonsOnLayer(), RouteOne(), and SetElementBoundingBox().

Here is the call graph for this function:

bool r_delete_entry	(	rtree_t *	rtree,
		const BoxType *	which
	)

Definition at line 1174 of file rtree.c.

References __r_delete(), __r_tree_is_good(), rtree::root, and rtree::size.

Referenced by adjust_tree(), ChangeArcAngles(), ChangeArcClearSize(), ChangeArcSize(), ChangeElementNameSize(), ChangeElementText(), ChangeHole(), ChangeLineClearSize(), ChangeLineSize(), ChangePadClearSize(), ChangePadMaskSize(), ChangePadSize(), ChangePinClearSize(), ChangePinMaskSize(), ChangePinSize(), ChangeTextName(), ChangeTextSize(), ChangeViaClearSize(), ChangeViaMaskSize(), ChangeViaSize(), DestroyArc(), DestroyElement(), DestroyLine(), DestroyPolygon(), DestroyPolygonPoint(), DestroyRat(), DestroyText(), DestroyVia(), FreeRotateBuffer(), FreeRotateElementLowLevel(), InsertPointIntoLine(), InsertPointIntoPolygon(), MirrorBuffer(), MoveArc(), MoveArcToBuffer(), MoveArcToLayerLowLevel(), MoveElementLowLevel(), MoveElementName(), MoveLine(), MoveLinePoint(), MoveLineToBuffer(), MoveLineToLayerLowLevel(), MovePolygon(), MovePolygonPoint(), MovePolygonToBuffer(), MovePolygonToLayerLowLevel(), MoveRatToBuffer(), MoveText(), MoveTextToBuffer(), MoveTextToLayerLowLevel(), MoveVia(), MoveViaToBuffer(), mts_remove_one(), NotifyMode(), PutContour(), r_delete_element(), remove_contour(), RemovePolygonPoint(), RemoveText(), RotateArc(), RotateBuffer(), RotateElementLowLevel(), RotateElementName(), RotateLinePoint(), RotateObject(), RotateText(), RouteAll(), RouteOne(), SetElementBoundingBox(), SwapBuffer(), and UndoChangeAngles().

Here is the call graph for this function:

void r_destroy_tree ( rtree_t ** rtree )

Free the memory associated with an rtree.

Definition at line 481 of file rtree.c.

References __r_destroy_tree().

Referenced by ComputeCost(), DestroyRouteData(), FreeDataMemory(), InsertHoles(), mtspace_destroy(), poly_DelContour(), poly_Free(), and RouteOne().

Here is the call graph for this function:

void r_insert_entry	(	rtree_t *	rtree,
		const BoxType *	which,
		int	manage
	)

Definition at line 1051 of file rtree.c.

References __r_insert_node(), rtree_node::box, rtree::root, rtree::size, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by AddPolygonToBuffer(), adjust_tree(), ChangeArcAngles(), ChangeArcClearSize(), ChangeArcSize(), ChangeElementNameSize(), ChangeElementText(), ChangeHole(), ChangeLineClearSize(), ChangeLineSize(), ChangeTextName(), ChangeTextSize(), ChangeViaClearSize(), ChangeViaMaskSize(), ChangeViaSize(), CopyAttachedPolygonToLayer(), CopyPolygon(), CreateNewArcOnLayer(), CreateNewLineOnLayer(), CreateNewPolygonFromRectangle(), CreateNewRat(), CreateNewText(), CreateNewVia(), DestroyPolygonPoint(), FreeRotateBuffer(), InsCntr(), InsertHoles(), InsertPointIntoLine(), InsertPointIntoPolygon(), make_edge_tree(), MirrorBuffer(), MorphPolygon(), moveable_edge(), MoveArc(), MoveArcToBuffer(), MoveArcToLayerLowLevel(), MoveElementLowLevel(), MoveElementName(), MoveLine(), MoveLinePoint(), MoveLineToBuffer(), MoveLineToLayerLowLevel(), MovePolygon(), MovePolygonPoint(), MovePolygonToBuffer(), MovePolygonToLayerLowLevel(), MoveRatToBuffer(), MoveText(), MoveTextToBuffer(), MoveTextToLayerLowLevel(), MoveVia(), MoveViaToBuffer(), mtspace_add(), NotifyMode(), poly_Copy1(), poly_InclContour(), PolyToPolygonsOnLayer(), PutContour(), r_create_tree(), RD_DrawLine(), RD_DrawThermal(), RD_DrawVia(), RemovePolygonPoint(), RotateArc(), RotateBuffer(), RotateElementName(), RotateLinePoint(), RotateObject(), RotateText(), RouteOne(), SetElementBoundingBox(), SwapBuffer(), and UndoChangeAngles().

Here is the call graph for this function:

int r_region_is_empty	(	rtree_t *	rtree,
		const BoxType *	region
	)

Special-purpose searches build upon r_search.

Returns:: 0 if there are any rectangles in the given region.

Definition at line 665 of file rtree.c.

References __r_region_is_empty_rect_in_reg(), and r_search().

Here is the call graph for this function:

int r_search	(	rtree_t *	rtree,
		const BoxType *	query,
		int()(const BoxType region, void *cl)	check_region,
		int()(const BoxType box, void *cl)	found_rectangle,
		void *	cl
	)

Parameterized search in the rtree.

Calls found_rectangle for each intersection seen and calls check_region with the current sub-region to see whether deeper searching is desired.

Generic search routine.

region_in_search should return true if "what you're looking for" is within the specified region; regions, like rectangles, are closed on top and left and open on bottom and right.

rectangle_in_region should return true if the given rectangle is "what you're looking for".

The search will find all rectangles matching the criteria given by region_in_search and rectangle_in_region and return a count of how many things rectangle_in_region returned true for.

Closure is used to abort the search if desired from within rectangel_in_region.

Look at the implementation of r_region_is_empty for how to abort the search if that is the desired behavior.

Returns:: the number of rectangles found.

Definition at line 612 of file rtree.c.

References __r_search(), __r_tree_is_good(), rtree_node::box, r_arg::check_it, r_arg::closure, r_arg::found_it, rtree::root, rtree::size, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Here is the call graph for this function:

static int r_search_pt	(	rtree_t *	rtree,
		const PointType *	pt,
		int	radius,
		int()(const BoxType region, void *cl)	region_in_search,
		int()(const BoxType box, void *cl)	rectangle_in_region,
		void *	closure
	)		`[inline, static]`

Definition at line 56 of file rtree.h.

References box, r_search(), PointType::X, BoxType::X1, BoxType::X2, PointType::Y, BoxType::Y1, and BoxType::Y2.

Referenced by LookupLOConnectionsToRatEnd(), and LookupPVConnectionsToLOList().

Here is the call graph for this function:

rtree.h File Reference

Functions

Detailed Description

Copyright.

Function Documentation