pcb 4.1.1
An interactive printed circuit board layout editor.

refine.c

Go to the documentation of this file.
00001 /* GTS - Library for the manipulation of triangulated surfaces
00002  * Copyright (C) 1999 Stéphane Popinet
00003  *
00004  * This library is free software; you can redistribute it and/or
00005  * modify it under the terms of the GNU Library General Public
00006  * License as published by the Free Software Foundation; either
00007  * version 2 of the License, or (at your option) any later version.
00008  *
00009  * This library is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012  * Library General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU Library General Public
00015  * License along with this library; if not, write to the
00016  * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
00017  * Boston, MA 02111-1307, USA.
00018  */
00019 
00020 #include <math.h>
00021 #include "gts.h"
00022 
00031 gboolean gts_vertex_encroaches_edge (GtsVertex * v, GtsEdge * e)
00032 {
00033   GtsPoint * p, * p1, * p2;
00034 
00035   g_return_val_if_fail (v != NULL, FALSE);
00036   g_return_val_if_fail (e != NULL, FALSE);
00037 
00038   p = GTS_POINT (v);
00039   p1 = GTS_POINT (GTS_SEGMENT (e)->v1);
00040   p2 = GTS_POINT (GTS_SEGMENT (e)->v2);
00041 
00042   if ((p1->x - p->x)*(p2->x - p->x) + (p1->y - p->y)*(p2->y - p->y) < 0.0)
00043     return TRUE;
00044   return FALSE;
00045 }
00046 
00057 GtsVertex * gts_edge_is_encroached (GtsEdge * e,
00058                                     GtsSurface * s,
00059                                     GtsEncroachFunc encroaches,
00060                                     gpointer data)
00061 {
00062   GSList * i;
00063 
00064   g_return_val_if_fail (e != NULL, NULL);
00065   g_return_val_if_fail (s != NULL, NULL);
00066   g_return_val_if_fail (encroaches != NULL, NULL);
00067 
00068   i = e->triangles;
00069   while (i) {
00070     GtsFace * f = i->data;
00071     if (GTS_IS_FACE (f) && gts_face_has_parent_surface (f, s)) {
00072       GtsVertex * v = gts_triangle_vertex_opposite (GTS_TRIANGLE (f), e);
00073       if ((* encroaches) (v, e, s, data))
00074         return v;
00075     }
00076     i = i->next;
00077   }
00078 
00079   return NULL;
00080 }
00081 
00082 #define ALREADY_ENCROACHED(c) (GTS_OBJECT (c)->reserved)
00083 
00084 static void vertex_encroaches (GtsVertex * v,
00085                                GtsSurface * surface,
00086                                GtsFifo * encroached,
00087                                GtsEncroachFunc encroaches,
00088                                gpointer data)
00089 {
00090   GSList * triangles, * i;
00091 
00092   g_return_if_fail (v != NULL);
00093   g_return_if_fail (surface != NULL);
00094   g_return_if_fail (encroached != NULL);
00095   g_return_if_fail (encroaches != NULL);
00096 
00097   i = triangles = gts_vertex_triangles (v, NULL);
00098   while (i) {
00099     GtsFace * f = i->data;
00100     if (GTS_IS_FACE (f) && gts_face_has_parent_surface (f, surface)) {
00101       GtsEdge * e = gts_triangle_edge_opposite (i->data, v);
00102       if (!ALREADY_ENCROACHED (e) && 
00103           GTS_IS_CONSTRAINT (e) &&
00104           (* encroaches) (v, e, surface, data)) {
00105         gts_fifo_push (encroached, e);
00106         ALREADY_ENCROACHED (e) = encroached;
00107       }
00108     }
00109     i = i->next;
00110   }
00111   g_slist_free (triangles);
00112 }
00113 
00114 static void make_encroached_fifo (GtsEdge * e, gpointer * datas)
00115 {
00116   GtsFifo * fifo = datas[0];
00117   GtsSurface * s = datas[1];
00118   GtsEncroachFunc encroaches = (GtsEncroachFunc) datas[2];
00119   gpointer data = datas[3];
00120 
00121   if (GTS_IS_CONSTRAINT (e) && 
00122       gts_edge_is_encroached (e, s, encroaches, data)) {
00123     gts_fifo_push (fifo, e);
00124     ALREADY_ENCROACHED (e) = fifo;
00125   }
00126 }
00127 
00128 #define SQUARE_ROOT_TWO 1.41421356237309504880168872420969807856967187
00129 #define DISTANCE_2D(v1, v2) (sqrt ((GTS_POINT (v2)->x - GTS_POINT (v1)->x)*\
00130                                    (GTS_POINT (v2)->x - GTS_POINT (v1)->x) +\
00131                                    (GTS_POINT (v2)->y - GTS_POINT (v1)->y)*\
00132                                    (GTS_POINT (v2)->y - GTS_POINT (v1)->y)))
00133 
00134 /* finds where to split the given edge to avoid infinite cycles. (see
00135    Shewchuk's thesis for details */
00136 static GtsVertex * split_edge (GtsEdge * e,
00137                                GtsSurface * surface)
00138 {
00139   GSList * i = e->triangles;
00140   GtsEdge * c = NULL;
00141 
00142   /* look for constraints touching e */
00143   while (i && !c) {
00144     GtsTriangle * t = i->data;
00145     if (GTS_IS_FACE (t) && 
00146         gts_face_has_parent_surface (GTS_FACE (t), surface)) {
00147       GtsEdge * e1, * e2;
00148       if (t->e1 == e) { e1 = t->e2; e2 = t->e3; }
00149       else if (t->e2 == e) { e1 = t->e1; e2 = t->e3; }
00150       else { e1 = t->e1; e2 = t->e2; }
00151       if (GTS_IS_CONSTRAINT (e1) && !GTS_IS_CONSTRAINT (e2))
00152         c = e1;
00153       else if (GTS_IS_CONSTRAINT (e2) && !GTS_IS_CONSTRAINT (e1))
00154         c = e2;
00155     }
00156     i = i->next;
00157   }
00158   if (c) {
00159     /* use power of two concentric shells */
00160     GtsVertex * v1 = GTS_SEGMENT (e)->v1;
00161     GtsVertex * v2 = GTS_SEGMENT (e)->v2;
00162     gdouble l = DISTANCE_2D (v1, v2);
00163     gdouble nearestpower = 1., split;
00164 
00165     while (l > SQUARE_ROOT_TWO*nearestpower)
00166       nearestpower *= 2.;
00167     while (l < SQUARE_ROOT_TWO*nearestpower/2.)
00168       nearestpower /= 2.;
00169     split = nearestpower/l/2.;
00170 
00171     if (GTS_SEGMENT (c)->v1 == v2 || GTS_SEGMENT (c)->v2 == v2)
00172       split = 1. - split;
00173     return gts_vertex_new (surface->vertex_class,
00174                            (1. - split)*GTS_POINT (v1)->x +
00175                            split*GTS_POINT (v2)->x,
00176                            (1. - split)*GTS_POINT (v1)->y +
00177                            split*GTS_POINT (v2)->y,
00178                            (1. - split)*GTS_POINT (v1)->z +
00179                            split*GTS_POINT (v2)->z);
00180   }
00181   else
00182     return gts_segment_midvertex (GTS_SEGMENT (e), surface->vertex_class);
00183 }
00184 
00185 static gint split_encroached (GtsSurface * surface, 
00186                               GtsFifo * encroached,
00187                               gint steiner_max,
00188                               GtsEncroachFunc encroaches,
00189                               gpointer data)
00190 {
00191   GtsSegment * s;
00192 
00193   while (steiner_max-- != 0 && (s = gts_fifo_pop (encroached))) {
00194     GtsVertex *add_vertex_returned;
00195     GtsVertex * v = split_edge (GTS_EDGE (s), surface);
00196     GtsFace * boundary = gts_edge_is_boundary (GTS_EDGE (s), surface);
00197     GtsFace * f = boundary;
00198 #if 1
00199     GtsEdge * e1 = GTS_EDGE (gts_object_clone (GTS_OBJECT (s)));
00200     GtsEdge * e2 = GTS_EDGE (gts_object_clone (GTS_OBJECT (s)));
00201 
00202     GTS_SEGMENT (e1)->v1 = s->v1;
00203     s->v1->segments = g_slist_prepend (s->v1->segments, e1);
00204     GTS_SEGMENT (e1)->v2 = v;
00205     v->segments = g_slist_prepend (v->segments, e1);
00206 
00207     GTS_SEGMENT (e2)->v1 = v;
00208     v->segments = g_slist_prepend (v->segments, e2);
00209     GTS_SEGMENT (e2)->v2 = s->v2;
00210     s->v2->segments = g_slist_prepend (s->v2->segments, e2);
00211 #else
00212     GtsEdge * e1 = gts_edge_new (GTS_EDGE_CLASS (GTS_OBJECT (s)->klass),
00213                                  s->v1, v);
00214     GtsEdge * e2 = gts_edge_new (GTS_EDGE_CLASS (GTS_OBJECT (s)->klass),
00215                                  v, s->v2);
00216 #endif
00217 
00218     GTS_OBJECT (s)->klass = GTS_OBJECT_CLASS (surface->edge_class);
00219 
00220     if (f == NULL)
00221       f = gts_edge_has_parent_surface (GTS_EDGE (s), surface);
00222     g_assert (f != NULL);
00223     add_vertex_returned = gts_delaunay_add_vertex_to_face (surface, v, f);
00224     g_assert (add_vertex_returned == NULL);
00225 
00226     if (boundary)
00227       gts_object_destroy (GTS_OBJECT (s));
00228 
00229     vertex_encroaches (v, surface, encroached, encroaches, data);
00230 
00231     if (gts_edge_is_encroached (e1, surface, encroaches, data)) {
00232       gts_fifo_push (encroached, e1);
00233       ALREADY_ENCROACHED (e1) = encroached;
00234     }
00235     if (gts_edge_is_encroached (e2, surface, encroaches, data)) {
00236       gts_fifo_push (encroached, e2);
00237       ALREADY_ENCROACHED (e2) = encroached;
00238     }
00239   }
00240 
00241   return steiner_max;
00242 }
00243 
00266 guint gts_delaunay_conform (GtsSurface * surface,
00267                             gint steiner_max,
00268                             GtsEncroachFunc encroaches,
00269                             gpointer data)
00270 {
00271   GtsFifo * encroached;
00272   gpointer datas[4];
00273   guint encroached_number;
00274 
00275   g_return_val_if_fail (surface != NULL, 0);
00276   g_return_val_if_fail (surface != NULL, 0);
00277   g_return_val_if_fail (encroaches != NULL, 0);
00278 
00279   datas[0] = encroached = gts_fifo_new ();
00280   datas[1] = surface;
00281   datas[2] = encroaches;
00282   datas[3] = data;
00283   gts_surface_foreach_edge (surface, (GtsFunc) make_encroached_fifo, datas);
00284 
00285   split_encroached (surface, 
00286                     encroached, 
00287                     steiner_max,
00288                     encroaches, data);
00289   gts_fifo_foreach (encroached, (GtsFunc) gts_object_reset_reserved, NULL);
00290   encroached_number = gts_fifo_size (encroached);
00291   gts_fifo_destroy (encroached);
00292   return encroached_number;
00293 }
00294 
00295 #define EHEAP_PAIR(f) (GTS_OBJECT (f)->reserved)
00296 
00297 static void heap_surface_add_face (GtsSurface * s, GtsFace * f)
00298 {
00299   GtsEHeap * heap = GTS_OBJECT (s)->reserved;
00300   gdouble key = gts_eheap_key (heap, f);
00301 
00302   if (key != 0.)
00303     EHEAP_PAIR (f) = gts_eheap_insert_with_key (heap, f, key);
00304   
00305   if (GTS_SURFACE_CLASS (GTS_OBJECT (s)->klass->parent_class)->add_face)
00306     (* GTS_SURFACE_CLASS (GTS_OBJECT (s)->klass->parent_class)->add_face) 
00307       (s, f);
00308 }
00309 
00310 static void heap_surface_remove_face (GtsSurface * s, GtsFace * f)
00311 {
00312   GtsEHeap * heap = GTS_OBJECT (s)->reserved;
00313 
00314   if (EHEAP_PAIR (f))
00315     gts_eheap_remove (heap, EHEAP_PAIR (f));
00316 
00317   if (GTS_SURFACE_CLASS (GTS_OBJECT (s)->klass->parent_class)->remove_face)
00318     (* GTS_SURFACE_CLASS (GTS_OBJECT (s)->klass->parent_class)->remove_face) 
00319       (s, f);
00320 }
00321 
00322 static void heap_surface_class_init (GtsSurfaceClass * klass)
00323 {
00324   klass->add_face = heap_surface_add_face;
00325   klass->remove_face = heap_surface_remove_face;
00326 }
00327 
00328 static GtsObjectClass * heap_surface_class_new (GtsObjectClass * parent_class)
00329 {
00330   GtsObjectClassInfo heap_surface_info;
00331 
00332   heap_surface_info = parent_class->info;
00333   heap_surface_info.class_init_func = (GtsObjectClassInitFunc)
00334     heap_surface_class_init;
00335   return gts_object_class_new (parent_class,
00336                                &heap_surface_info);
00337 }
00338 
00339 static void make_face_heap (GtsFace * f, GtsEHeap * heap)
00340 {
00341   gdouble key = gts_eheap_key (heap, f);
00342 
00343   if (key != 0.)
00344     EHEAP_PAIR (f) = gts_eheap_insert_with_key (heap, f, key);
00345 }
00346 
00362 guint gts_delaunay_refine (GtsSurface * surface,
00363                            gint steiner_max,
00364                            GtsEncroachFunc encroaches,
00365                            gpointer encroach_data,
00366                            GtsKeyFunc cost,
00367                            gpointer cost_data)
00368 {
00369   GtsObjectClass * heap_surface_class;
00370   GtsObjectClass * original_class;
00371   GtsEHeap * heap;
00372   GtsFifo * encroached;
00373   GtsFace * f;
00374   guint unrefined_number;
00375 
00376   g_return_val_if_fail (surface != NULL, 0);
00377   g_return_val_if_fail (encroaches != NULL, 0);
00378   g_return_val_if_fail (cost != NULL, 0);
00379 
00380   original_class = GTS_OBJECT (surface)->klass;
00381   heap_surface_class = heap_surface_class_new (original_class);
00382   GTS_OBJECT (surface)->klass = heap_surface_class;
00383 
00384   heap = gts_eheap_new (cost, cost_data);
00385   gts_surface_foreach_face (surface, (GtsFunc) make_face_heap, heap);
00386   encroached = gts_fifo_new ();
00387   
00388   GTS_OBJECT (surface)->reserved = heap;
00389 
00390   while (steiner_max-- != 0 && (f = gts_eheap_remove_top (heap, NULL))) {
00391     GtsVertex *add_vertex_returned;
00392     GtsVertex * c = 
00393       GTS_VERTEX (gts_triangle_circumcircle_center (GTS_TRIANGLE (f),
00394                   GTS_POINT_CLASS (surface->vertex_class)));
00395     EHEAP_PAIR (f) = NULL;
00396     g_assert (c != NULL);
00397     add_vertex_returned = gts_delaunay_add_vertex (surface, c, f);
00398     g_assert (add_vertex_returned == NULL);
00399 
00400     vertex_encroaches (c, surface, encroached, encroaches, encroach_data);
00401     if (!gts_fifo_is_empty (encroached)) {
00402       gts_delaunay_remove_vertex (surface, c);
00403       steiner_max = split_encroached (surface, 
00404                                       encroached, 
00405                                       steiner_max, 
00406                                       encroaches, 
00407                                       encroach_data);
00408     }
00409   }
00410 
00411   unrefined_number = gts_eheap_size (heap);
00412   gts_eheap_foreach (heap, (GFunc) gts_object_reset_reserved, NULL);
00413   gts_eheap_destroy (heap);
00414 
00415   gts_fifo_foreach (encroached, (GtsFunc) gts_object_reset_reserved, NULL);
00416   gts_fifo_destroy (encroached);
00417 
00418   GTS_OBJECT (surface)->klass = original_class;
00419   GTS_OBJECT (surface)->reserved = NULL;
00420   g_free (heap_surface_class);
00421 
00422   return unrefined_number;
00423 }