Functions used to autoplace elements. More...

#include <assert.h>
#include <math.h>
#include <memory.h>
#include <stdlib.h>
#include "global.h"
#include "autoplace.h"
#include "box.h"
#include "compat.h"
#include "data.h"
#include "draw.h"
#include "error.h"
#include "intersect.h"
#include "rtree.h"
#include "macro.h"
#include "mirror.h"
#include "misc.h"
#include "move.h"
#include "mymem.h"
#include "rats.h"
#include "remove.h"
#include "rotate.h"

Include dependency graph for autoplace.c:

Go to the source code of this file.

Data Structures
struct	ElementPtrListType
struct	PerturbationType
struct	r_neighbor_info
	Helper function to compute "closest neighbor" for a box in a rtree. More...
Defines
#define	EXPANDRECTXY(r1, x1, y1, x2, y2)
#define	EXPANDRECT(r1, r2) EXPANDRECTXY(r1, r2->X1, r2->Y1, r2->X2, r2->Y2)
#define	ROTATEBOX(box)
Enumerations
enum	ewhich { SHIFT, ROTATE, EXCHANGE }
Functions
static double	ComputeCost (NetListType *Nets, double T0, double T)
	Compute cost function.
static void	UpdateXY (NetListType *Nets)
	Update the X, Y and group position information stored in the NetList after elements have possibly been moved, rotated, flipped, etc.
static PointerListType	collectSelectedElements ()
	Create a list of selected elements.
static int	__r_find_neighbor_reg_in_sea (const BoxType region, void cl)
	Helper methods for __r_find_neighbor.
static int	__r_find_neighbor_rect_in_reg (const BoxType box, void cl)

static const BoxType *	r_find_neighbor (rtree_t rtree, const BoxType box, direction_t search_direction)
	main r_find_neighbor routine.
PerturbationType	createPerturbation (PointerListType *selected, double T)

void	doPerturb (PerturbationType *pt, bool undo)
bool	AutoPlaceSelected (void)
	Auto-place selected components.
Variables
struct {
double via_cost
double congestion_penalty
double overlap_penalty_min
double overlap_penalty_max
double out_of_bounds_penalty
double overall_area_penalty
double matching_neighbor_bonus
double aligned_neighbor_bonus
double oriented_neighbor_bonus
double m
double gamma
int good_ratio
bool fast
Coord large_grid_size
Coord small_grid_size
}	CostParameter
	Wire cost is manhattan distance (in mils), thus 1 inch = 1000.

Detailed Description

Functions used to autoplace elements.

Author:: This module, autoplace.c, was written by and is Copyright (c) 2001 C. Scott Ananian

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 autoplace.c.

Define Documentation

#define EXPANDRECT	(	r1,
		r2
	)	EXPANDRECTXY(r1, r2->X1, r2->Y1, r2->X2, r2->Y2)

Definition at line 75 of file autoplace.c.

Referenced by ComputeCost().

#define EXPANDRECTXY	(	r1,
		x1,
		y1,
		x2,
		y2
	)

Value:

{ \
  r1->X1=MIN(r1->X1, x1); r1->Y1=MIN(r1->Y1, y1); \
  r1->X2=MAX(r1->X2, x2); r1->Y2=MAX(r1->Y2, y2); \
}

Definition at line 71 of file autoplace.c.

Referenced by ComputeCost().

#define ROTATEBOX ( box )

Value:

{ Coord t;\
    t = (box).X1; (box).X1 = - (box).Y1; (box).Y1 = t;\
    t = (box).X2; (box).X2 = - (box).Y2; (box).Y2 = t;\
    t = (box).X1; (box).X1 =   (box).X2; (box).X2 = t;\
}

Definition at line 251 of file autoplace.c.

Enumeration Type Documentation

enum ewhich

Enumerator:

SHIFT
ROTATE
EXCHANGE

Definition at line 136 of file autoplace.c.

Function Documentation

static int __r_find_neighbor_rect_in_reg	(	const BoxType *	box,
		void *	cl
	)		`[static]`

  ______________ __ trap.y1     __
  \            /               |__| query rect.
   /  __ trap.y2
   |          |
   trap.x1    trap.x2   sides at 45-degree angle

Definition at line 294 of file autoplace.c.

References box, r_neighbor_info::neighbor, ROTATEBOX_TO_NORTH, r_neighbor_info::search_dir, r_neighbor_info::trap, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by r_find_neighbor().

static int __r_find_neighbor_reg_in_sea	(	const BoxType *	region,
		void *	cl
	)		`[static]`

Helper methods for __r_find_neighbor.

  ______________ __ trap.y1     __
  \            /               |__| query rect.
   /  __ trap.y2
   |          |
   trap.x1    trap.x2   sides at 45-degree angle

Definition at line 270 of file autoplace.c.

References region, ROTATEBOX_TO_NORTH, r_neighbor_info::search_dir, r_neighbor_info::trap, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.

Referenced by r_find_neighbor().

bool AutoPlaceSelected ( void )

Auto-place selected components.

Definition at line 779 of file autoplace.c.

References _, AddAllRats(), collectSelectedElements(), ComputeCost(), CostParameter, createPerturbation(), DeleteRats(), doPerturb(), FreePointerListMemory(), INCH_TO_COORD, MAX, Message(), MIL_TO_COORD, MIN, PCBType::NetlistLib, PCB, ProcNetlist(), PointerListType::PtrN, random(), and Redraw().

Referenced by ActionAutoPlaceSelected().

Here is the call graph for this function:

static PointerListType collectSelectedElements ( ) [static]

Create a list of selected elements.

Definition at line 197 of file autoplace.c.

References PCBType::Data, ELEMENT_LOOP, END_LOOP, GetPointerMemory(), PCB, and TEST_FLAG.

Referenced by AutoPlaceSelected().

Here is the call graph for this function:

static double ComputeCost	(	NetListType *	Nets,
		double	T0,
		double	T
	)		`[static]`

Compute cost function.

Note that area overlap cost is correct for SMD devices: SMD devices on opposite sides of the board don't overlap.

Algorithms follow those described in sections 4.1 of "Placement and Routing of Electronic Modules" edited by Michael Pecht Marcel Dekker, Inc. 1993. ISBN: 0-8247-8916-4 TK7868.P7.P57 1993

Definition at line 354 of file autoplace.c.

References __FUNCTION__, abs, bounds, box, BoxListType::BoxN, c, pin_st::Clearance, ComputeIntersectionArea(), NetType::Connection, NetType::ConnectionN, COORD_TO_MIL, CostParameter, PCBType::Data, EAST, ELEMENT_LOOP, END_LOOP, EXPANDRECT, EXPANDRECTXY, FreeBoxListMemory(), FreePointerListMemory(), GetBoxMemory(), GetPointerMemory(), ConnectionType::group, MAKEMAX, MAKEMIN, malloc(), MAX, PCBType::MaxHeight, PCBType::MaxWidth, maxx, maxy, MIN, minx, miny, n, NetListType::Net, NetListType::NetN, NORTH, NSTRCMP, PAD_LOOP, PCB, pin, PIN_LOOP, PointerListType::Ptr, PointerListType::PtrN, r_create_tree(), r_destroy_tree(), r_find_neighbor(), SOUTH, TEST_FLAG, pin_st::Thickness, thickness, ConnectionType::type, UpdateXY(), WEST, pin_st::X, ConnectionType::X, BoxType::X1, BoxType::X2, pin_st::Y, ConnectionType::Y, BoxType::Y1, and BoxType::Y2.

Referenced by AutoPlaceSelected().

Here is the call graph for this function:

PerturbationType createPerturbation	(	PointerListType *	selected,
		double	T
	)

Perturb: 1) flip SMD from solder side to component side or vice-versa.
2) rotate component 90, 180, or 270 degrees.
3) shift component random + or - amount in random direction.
(magnitude of shift decreases over time)
-- Only perturb selected elements (need count/list of selected?) --

Definition at line 646 of file autoplace.c.

References CostParameter, PerturbationType::DX, PerturbationType::DY, PerturbationType::element, EXCHANGE, MAX, PCBType::MaxHeight, PCBType::MaxWidth, MIL_TO_COORD, MIN, PerturbationType::other, ElementType::PadN, PCB, ElementType::PinN, PointerListType::Ptr, PointerListType::PtrN, random(), PerturbationType::rotate, ROTATE, SGN, SHIFT, TEST_FLAG, ElementType::VBox, PerturbationType::which, BoxType::X1, BoxType::X2, BoxType::Y1, and BoxType::Y2.