00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025 #include "matrix.h"
00026 #include "pad-pin-data.h"
00027
00028 static Boolean calculate_transformation(CheapPointType new1_pt,
00029 CheapPointType new2_pt,
00030 CheapPointType old1_pt,
00031 CheapPointType old2_pt,
00032 Boolean reflect,
00033 double angle,
00034 Matrix3x3 new_to_old_mat);
00035 static void transform_pad_pin_data(ElementPadPinData* ppd, int len,
00036 Matrix3x3 trans);
00037 static double calculate_sum_of_distances(ElementPadPinData* ppd_a, int len_a,
00038 ElementPadPinData* ppd_b, int len_b);
00039 static Boolean find_number_block(const ElementPadPinData* ppd, int len,
00040 const PadOrPinType* pp,
00041 int* start, int* end);
00042 static int pad_pin_data_cmp_by_number(const void* va, const void* vb);
00043
00044 ElementPadPinData*
00045 alloc_pad_pin_data_array(ElementTypePtr element, int* len_ptr)
00046 {
00047 int len = element->PadN + element->PinN;
00048 ElementPadPinData* ppd = MyCalloc(len, sizeof(ElementPadPinData),
00049 "alloc_pad_pin_data_array");
00050
00051
00052 int i = 0;
00053 PAD_OR_PIN_LOOP(element);
00054 {
00055 ppd[i].pp = pp;
00056 ppd[i].center
00057 = ppd[i].transformed_center
00058 = pad_or_pin_center(&pp);
00059 i++;
00060 }
00061 END_LOOP;
00062
00063
00064 qsort(ppd, len, sizeof(ElementPadPinData), pad_pin_data_cmp_by_number);
00065
00066
00067 int i_start = 0;
00068 const PadOrPinType* pp_start = &ppd[0].pp;
00069
00070 for (i = 1; i < len + 1; i++) {
00071 if (i == len || pad_or_pin_number_cmp(pp_start, &ppd[i].pp) != 0) {
00072 int shares = i - i_start;
00073 int j;
00074 for (j = i_start; j < i; j++) {
00075 ppd[j].shares = shares;
00076 }
00077
00078 if (i != len) {
00079 i_start = i;
00080 pp_start = &ppd[i].pp;
00081 }
00082 }
00083 }
00084 *len_ptr = len;
00085 return ppd;
00086 }
00087
00088 double
00089 find_non_coincident(const ElementPadPinData* ppd, int len,
00090 int* index1_ptr, int* index2_ptr)
00091 {
00092 int index1 = 0;
00093 const ElementPadPinData* ppd1 = &ppd[index1];
00094 int i;
00095 for (i = 1; i < len; i++) {
00096 double d2 = point_distance2(ppd1->center, ppd[i].center);
00097 if (d2) {
00098 *index1_ptr = index1;
00099 *index2_ptr = i;
00100 return d2;
00101 }
00102 }
00103 return 0;
00104 }
00105
00106 Boolean
00107 find_best_corresponding_pads_or_pins(ElementPadPinData* ppd_a, int len_a,
00108 int index1_a, int index2_a,
00109 Boolean reflect,
00110 ElementPadPinData* ppd_b, int len_b,
00111 int* index1_b_ptr, int* index2_b_ptr)
00112 {
00113 int block1_start = 0;
00114 int block1_end = 0;
00115 int block2_start = 0;
00116 int block2_end = 0;
00117 if (! find_number_block(ppd_b, len_b, &ppd_a[index1_a].pp,
00118 &block1_start, &block1_end)) {
00119 return False;
00120 }
00121 if (! find_number_block(ppd_b, len_b, &ppd_a[index2_a].pp,
00122 &block2_start, &block2_end)) {
00123 return False;
00124 }
00125
00126 Boolean min_set = False;
00127 double min_sum_of_distances = 0;
00128 int min_index1_b = 0;
00129 int min_index2_b = 0;
00130
00131 int i;
00132 for (i = block1_start; i < block1_end; i++) {
00133 int j;
00134 for (j = block2_start; j < block2_end; j++) {
00135
00136 if (i != j) {
00137 int k;
00138 for (k = 0; k < 4; k++) {
00139
00140 double angle = k * M_PI / 2;
00141 Matrix3x3 trans;
00142 if (calculate_transformation(ppd_a[index1_a].center,
00143 ppd_a[index2_a].center,
00144 ppd_b[i].center,
00145 ppd_b[j].center,
00146 reflect, angle,
00147 trans)) {
00148
00149 transform_pad_pin_data(ppd_a, len_a, trans);
00150
00151 double sd = calculate_sum_of_distances(ppd_a, len_a,
00152 ppd_b, len_b);
00153 if (! min_set || sd < min_sum_of_distances) {
00154 min_set = True;
00155 min_sum_of_distances = sd;
00156 min_index1_b = i;
00157 min_index2_b = j;
00158 }
00159 }
00160 }
00161 }
00162 }
00163 }
00164 if (min_set) {
00165 debug_log("Best corresponding pads/pins found.\n");
00166 *index1_b_ptr = min_index1_b;
00167 *index2_b_ptr = min_index2_b;
00168 } else {
00169 debug_log("No best corresponding pads/pins found.\n");
00170 }
00171 return min_set;
00172 }
00173
00174 static void
00175 transform_pad_pin_data(ElementPadPinData* ppd, int len,
00176 Matrix3x3 trans)
00177 {
00178 int i;
00179 for (i = 0; i < len; i++) {
00180 Vector3x1 v;
00181 point_to_vec(ppd[i].center, v);
00182 Vector3x1 t;
00183 multiply_matrix_vector(trans, v, t);
00184 ppd[i].transformed_center = vec_to_point(t);
00185 }
00186 }
00187
00188
00189
00190
00191 static double
00192 calculate_sum_of_distances(ElementPadPinData* ppd_a, int len_a,
00193 ElementPadPinData* ppd_b, int len_b)
00194 {
00195
00196 int i;
00197 for (i = 0; i < len_b; i++) {
00198 ppd_b[i].taken = False;
00199 }
00200
00201 double sum_d2 = 0;
00202 for (i = 0; i < len_a; i++) {
00203 int block_b_start = 0;
00204 int block_b_end = 0;
00205 ElementPadPinData* a = &ppd_a[i];
00206 if (find_number_block(ppd_b, len_b, &a->pp,
00207 &block_b_start, &block_b_end)) {
00208 Boolean min_set = False;
00209 double min_d2 = 0;
00210 int min_index = 0;
00211 int j;
00212 for (j = block_b_start; j < block_b_end; j++) {
00213 ElementPadPinData* b = &ppd_b[j];
00214 if (! b->taken) {
00215 double d2 = point_distance2(a->transformed_center,
00216 b->transformed_center);
00217 if (! min_set || d2 < min_d2) {
00218 min_set = True;
00219 min_d2 = d2;
00220 min_index = j;
00221 }
00222 }
00223 }
00224 if (min_set) {
00225 ppd_b[min_index].taken = True;
00226 sum_d2 += min_d2;
00227 }
00228 }
00229 }
00230 return sum_d2;
00231 }
00232
00233 Boolean
00234 calculate_transformation(CheapPointType new1_pt, CheapPointType new2_pt,
00235 CheapPointType old1_pt, CheapPointType old2_pt,
00236 Boolean reflect,
00237 double angle,
00238 Matrix3x3 new_to_old_mat)
00239 {
00240 Matrix3x3 t;
00241
00242
00243 Matrix3x3 new_to_origin_mat;
00244 make_translation_matrix(new_to_origin_mat, -new1_pt.X, -new1_pt.Y);
00245 if (reflect) {
00246
00247
00248 make_reflection_matrix_y_axis(t);
00249 multiply_matrix_matrix_inplace(t, new_to_origin_mat);
00250 }
00251
00252 Matrix3x3 result;
00253
00254 copy_matrix(new_to_origin_mat, result);
00255
00256 make_rotation_matrix(t, angle);
00257 multiply_matrix_matrix_inplace(t, result);
00258
00259 make_translation_matrix(t, old1_pt.X, old1_pt.Y);
00260 multiply_matrix_matrix_inplace(t, result);
00261
00262 copy_matrix(result, new_to_old_mat);
00263 return True;
00264 }
00265
00266 static Boolean
00267 find_number_block(const ElementPadPinData* ppd, int len,
00268 const PadOrPinType* pp,
00269 int* start, int* end)
00270 {
00271 int i;
00272 for (i = 0; i < len; i++) {
00273 if (pad_or_pin_number_cmp(&ppd[i].pp, pp) == 0) {
00274 int j;
00275 for (j = i + 1; j < len; j++) {
00276 if (pad_or_pin_number_cmp(&ppd[j].pp, pp) != 0) {
00277 break;
00278 }
00279 }
00280 *start = i;
00281 *end = j;
00282 return True;
00283 }
00284 }
00285 return False;
00286 }
00287
00288 static int
00289 pad_pin_data_cmp_by_number(const void* va, const void* vb)
00290 {
00291 const ElementPadPinData* a = (const ElementPadPinData*)va;
00292 const ElementPadPinData* b = (const ElementPadPinData*)vb;
00293 return pad_or_pin_number_cmp(&a->pp, &b->pp);
00294 }