degate  0.1.2
TangencyCheck.cc
Go to the documentation of this file.
00001 /* -*-c++-*-
00002 
00003   This file is part of the IC reverse engineering tool degate.
00004 
00005   Copyright 2008, 2009, 2010 by Martin Schobert
00006 
00007   Degate is free software: you can redistribute it and/or modify
00008   it under the terms of the GNU General Public License as published by
00009   the Free Software Foundation, either version 3 of the License, or
00010   any later version.
00011 
00012   Degate is distributed in the hope that it will be useful,
00013   but WITHOUT ANY WARRANTY; without even the implied warranty of
00014   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00015   GNU General Public License for more details.
00016 
00017   You should have received a copy of the GNU General Public License
00018   along with degate. If not, see <http://www.gnu.org/licenses/>.
00019 
00020 */
00021 
00022 #include <degate.h>
00023 #include <TangencyCheck.h>
00024 
00025 /**
00026  * Calculate the parameter for a linear function f(x) = m*x + n.
00027  * @return Returns if the parameter can be calculated.
00028  */
00029 bool get_line_function_for_wire(degate::Line_shptr l, double * m, double * n) {
00030   assert(l != NULL);
00031   assert(m != NULL);
00032   assert(n != NULL);
00033 
00034   int d_y = l->get_to_y() - l->get_from_y();
00035   int d_x = l->get_to_x() - l->get_from_x();
00036 
00037   if(abs(d_x) == 0) return false;
00038   else {
00039     *m = static_cast<double>(d_y) / static_cast<double>(d_x);
00040     *n = l->get_from_y() - l->get_from_x() * *m;
00041     return true;
00042   }
00043 }
00044 
00045 
00046 bool degate::check_object_tangency(Circle_shptr o1,
00047                                    Circle_shptr o2) {
00048 
00049   int dx = o1->get_x() - o1->get_x();
00050   int dy = o2->get_y() - o1->get_y();
00051   return (sqrt(dx*dx + dy*dy) <= (o1->get_diameter() + o2->get_diameter()) / 2.0);
00052 }
00053 
00054 bool degate::check_object_tangency(Line_shptr o1,
00055                                    Line_shptr o2) {
00056   double m1, n1, m2, n2;
00057   bool ret1 = get_line_function_for_wire(o1, &m1, &n1);
00058   bool ret2 = get_line_function_for_wire(o2, &m2, &n2);
00059 
00060   if(ret1 && ret2) {
00061 
00062     double xi = - (n1 - n2) / (m1 - m2);
00063     double yi = n1 + m1 * xi;
00064 
00065     return( (o1->get_from_x() - xi)*(xi - o1->get_to_x()) >= 0 &&
00066             (o2->get_from_x() - xi)*(xi - o2->get_to_x()) >= 0 &&
00067             (o1->get_from_y() - yi)*(yi - o1->get_to_y()) >= 0 &&
00068             (o2->get_from_y() - yi)*(yi - o2->get_to_y()) >= 0);
00069   }
00070   else if(!ret1 && !ret2) {
00071     return o1->get_from_x() == o2->get_from_x();
00072   }
00073   else {
00074     Line_shptr v = ret1 ? o2 : o1;
00075     Line_shptr l = ret1 ? o1 : o2;
00076 
00077     BoundingBox const & b = v->get_bounding_box();
00078 
00079     if((l->get_from_x() > b.get_max_x() &&
00080         l->get_to_x()   > b.get_max_x()) ||
00081        // no intersection (line is to right of rectangle).
00082 
00083        (l->get_from_x() > b.get_min_x() &&
00084         l->get_to_x()   > b.get_min_x()) ||
00085        // no intersection (line is to left of rectangle).
00086 
00087        (l->get_from_y() > b.get_min_y() &&
00088         l->get_to_y()   > b.get_min_y()) ||
00089        // no intersection (line is above rectangle).
00090 
00091        (l->get_from_y() > b.get_max_y() &&
00092         l->get_to_y()   > b.get_max_y())
00093        //no intersection (line is below rectangle).
00094        )
00095       return false;
00096     else
00097       return true;
00098 
00099   }
00100 
00101   return false;
00102 }
00103 
00104 bool degate::check_object_tangency(Rectangle_shptr o1,
00105                                    Rectangle_shptr o2) {
00106   return o1->get_bounding_box().intersects(o2->get_bounding_box());
00107 }
00108 
00109 bool degate::check_object_tangency(Circle_shptr o1,
00110                                    Line_shptr o2) {
00111   BoundingBox const & b = o1->get_bounding_box();
00112 
00113   Rectangle_shptr r(new Rectangle(b.get_min_x(), b.get_max_x(),
00114                                   b.get_min_y(), b.get_max_y()));
00115 
00116   return check_object_tangency(o2, r);
00117 }
00118 
00119 bool degate::check_object_tangency(Circle_shptr o1,
00120                                    Rectangle_shptr o2) {
00121   return o1->get_bounding_box().intersects(o2->get_bounding_box());
00122 }
00123 
00124 bool degate::check_object_tangency(Line_shptr l,
00125                                    Rectangle_shptr r) {
00126 
00127 
00128   // http://stackoverflow.com/questions/99353/how-to-test-if-a-line-segment-intersects-an-axis-aligned-rectange-in-2d
00129 
00130   // Let the segment endpoints be p1=(x1 y1) and p2=(x2 y2).
00131   // Let the rectangle's corners be (xBL yBL) and (xTR yTR).
00132 
00133   int x1, x2, y1, y2;
00134 
00135   if(l->get_from_x() < l->get_to_x()) {
00136     x1 = l->get_from_x();
00137     y1 = l->get_from_y();
00138     x2 = l->get_to_x();
00139     y2 = l->get_to_y();
00140   }
00141   else {
00142     x2 = l->get_from_x();
00143     y2 = l->get_from_y();
00144     x1 = l->get_to_x();
00145     y1 = l->get_to_y();
00146   }
00147 
00148   // F(x y) = (y2-y1)x + (x1-x2)y + (x2*y1-x1*y2)
00149 
00150   int dy = y2 - y1;
00151   int dx = x1 - x2;
00152   int i = x2 * y1 - x1 * y2;
00153 
00154   // Calculate F(x,y) for each corner of the rectangle.
00155   // If any of the values f[i] is 0, the corner is on the line.
00156   int f1 = dy * r->get_min_x() + dx * r->get_min_y() + i;
00157   if(f1 == 0) return true;
00158   int f2 = dy * r->get_min_x() + dx * r->get_max_y() + i;
00159   if(f2 == 0) return true;
00160   int f3 = dy * r->get_max_x() + dx * r->get_min_y() + i;
00161   if(f3 == 0) return true;
00162   int f4 = dy * r->get_max_x() + dx * r->get_max_y() + i;
00163   if(f4 == 0) return true;
00164 
00165   /* If all corners are "below" or "above" the line, the
00166      objects can't intersect. */
00167   if((f1 < 0 && f2 < 0 && f3 < 0 && f4 < 0) ||
00168      (f1 > 0 && f2 > 0 && f3 > 0 && f4 > 0)) {
00169     return false;
00170   }
00171 
00172   /*
00173     Project the endpoint onto the x axis, and check if the
00174     segment's shadow intersects the polygon's shadow. Repeat on the y axis:
00175   */
00176   if( (x1 > r->get_max_x() &&
00177        x2 > r->get_max_x()) &&
00178       // no intersection (line is to right of rectangle).
00179 
00180       !(x1 > r->get_min_x() &&
00181         x2 > r->get_min_x()) &&
00182       // no intersection (line is to left of rectangle).
00183 
00184       !(y1 > r->get_max_y() &&
00185         y2 > r->get_max_y()) &&
00186       // no intersection (line is above rectangle).
00187 
00188       !(y1 < r->get_min_y() &&
00189         y2 < r->get_min_y())
00190       //no intersection (line is below rectangle).
00191       ) {
00192     return false;
00193   }
00194 
00195   else // there is an intersection
00196     return true;
00197 }
00198 
00199 bool degate::check_object_tangency(PlacedLogicModelObject_shptr o1,
00200                                    PlacedLogicModelObject_shptr o2) {
00201   if(o1 == NULL || o2 == NULL)
00202     throw InvalidPointerException("You passed an invalid shared pointer.");
00203 
00204   if(!o1->get_bounding_box().intersects(o2->get_bounding_box()))
00205     return false;
00206 
00207   Circle_shptr c1, c2;
00208   Line_shptr l1, l2;
00209   Rectangle_shptr r1, r2;
00210 
00211   c1 = std::dynamic_pointer_cast<Circle>(o1);
00212   l1 = std::dynamic_pointer_cast<Line>(o1);
00213   r1 = std::dynamic_pointer_cast<Rectangle>(o1);
00214   c2 = std::dynamic_pointer_cast<Circle>(o2);
00215   l2 = std::dynamic_pointer_cast<Line>(o2);
00216   r2 = std::dynamic_pointer_cast<Rectangle>(o2);
00217 
00218   if(c1 && c2)
00219     return check_object_tangency(c1, c2);
00220   else if(l1 && l2) {
00221 
00222     bool ret= check_object_tangency(l1, l2);
00223     std::cout << "Check l1/l2: " << ret << std::endl;
00224     return ret;
00225   }
00226   else if(r1 && r2)
00227     return check_object_tangency(r1, r2);
00228 
00229   else if(c1 && l2)
00230     return check_object_tangency(c1, l2);
00231   else if(l1 && c2)
00232     return check_object_tangency(c2, l1);
00233 
00234   else if(c1 && r2)
00235     return check_object_tangency(c1, r2);
00236   else if(r1 && c2)
00237     return check_object_tangency(c2, r1);
00238 
00239 
00240   else if(l1 && r2)
00241     return check_object_tangency(l1, r2);
00242   else if(r1 && l2)
00243     return check_object_tangency(l2, r1);
00244 
00245   assert(1==0);
00246 }