[xiph-commits] r10158 - trunk/planarity
xiphmont at svn.xiph.org
xiphmont at svn.xiph.org
Fri Oct 14 23:50:47 PDT 2005
Author: xiphmont
Date: 2005-10-14 23:50:44 -0700 (Fri, 14 Oct 2005)
New Revision: 10158
Modified:
trunk/planarity/graph_arrange.c
trunk/planarity/graph_generate.c
trunk/planarity/graph_generate_mesh2.c
trunk/planarity/graph_region.c
trunk/planarity/graph_region.h
trunk/planarity/version.h
Log:
Improve generation of partitioned graphs.
Modified: trunk/planarity/graph_arrange.c
===================================================================
--- trunk/planarity/graph_arrange.c 2005-10-14 17:29:00 UTC (rev 10157)
+++ trunk/planarity/graph_arrange.c 2005-10-15 06:50:44 UTC (rev 10158)
@@ -142,10 +142,7 @@
acc+=del;
}
acc-=perarc/2;
-
-
}
-
}
@@ -217,7 +214,6 @@
region_line_to(657,232);
region_line_to(460,232);
region_close_line();
- region_layout(g);
}
void arrange_region_rainbow(graph *g){
@@ -227,7 +223,6 @@
region_line_to(660,500);
region_arc_to(200,500,M_PI);
region_close_line();
- region_layout(g);
}
void arrange_region_dashed_circle(graph *g){
@@ -248,7 +243,6 @@
region_new_area(x1,y1,3);
region_arc_to(x2,y2,M_PI/10);
}
- region_layout(g);
}
void arrange_region_bifur(graph *g){
@@ -265,9 +259,6 @@
region_line_to(bw/2-130,bh-60);
region_arc_to(bw/2+130,bh-60,M_PI*.25);
region_line_to(bw-21,bh-60);
-
- region_layout(g);
-
}
void arrange_region_dairyqueen(graph *g){
@@ -293,8 +284,6 @@
region_arc_to(x1,y2,-M_PI/2);
region_line_to(50,bh/2);
region_close_line();
-
- region_layout(g);
}
void arrange_region_cloud(graph *g){
@@ -315,8 +304,6 @@
region_arc_to(x2,y2,M_PI*.7);
}
region_close_arc(M_PI*.7);
-
- region_layout(g);
}
void arrange_region_ring(graph *g){
@@ -327,7 +314,6 @@
region_init();
region_circle(bw/2,bh/2,radius,3);
region_circle(bw/2,bh/2,radius*.4,1);
- region_layout(g);
}
void arrange_region_storm(graph *g){
@@ -351,8 +337,6 @@
}
region_circle(bw/2,bh/2,radius*.2,0);
-
- region_layout(g);
}
void arrange_region_target(graph *g){
@@ -363,9 +347,8 @@
region_init();
region_circle(bw/2,bh/2,radius,3);
region_circle(bw/2,bh/2,radius*.5,1);
+ region_split_here();
region_circle(bw/2,bh/2,radius*.35,3);
-
- region_layout(g);
}
void arrange_region_plus(graph *g){
@@ -384,8 +367,6 @@
region_arc_to(143,216,-M_PI*2/10);
region_line_to(316,216);
region_close_line();
-
- region_layout(g);
}
void arrange_region_hole3(graph *g){
@@ -400,7 +381,6 @@
region_line_to(313,349);
region_line_to(487,349);
region_close_line();
- region_layout(g);
}
void arrange_region_hole4(graph *g){
@@ -416,7 +396,6 @@
region_line_to(475,375);
region_line_to(325,375);
region_close_line();
- region_layout(g);
}
void arrange_region_ovals(graph *g){
@@ -428,21 +407,19 @@
region_line_to(530,437);
region_arc_to(270,437,-M_PI*.99);
region_close_line();
+ region_split_here();
region_new_area(80,263,2);
region_arc_to(230,263,-M_PI*.99);
region_line_to(230,337);
region_arc_to(80,337,-M_PI*.99);
region_close_line();
+ region_split_here();
region_new_area(570,263,2);
region_arc_to(720,263,-M_PI*.99);
region_line_to(720,337);
region_arc_to(570,337,-M_PI*.99);
region_close_line();
-
-
- region_layout(g);
-
-
+ region_split_here();
}
Modified: trunk/planarity/graph_generate.c
===================================================================
--- trunk/planarity/graph_generate.c 2005-10-14 17:29:00 UTC (rev 10157)
+++ trunk/planarity/graph_generate.c 2005-10-15 06:50:44 UTC (rev 10158)
@@ -235,6 +235,17 @@
gi->gen(g,ordernum);
}
+ // clear out overloaded flags
+ {
+ vertex *v = g->verticies;
+ while(v){
+ v->active=0;
+ v->selected=0;
+ v->grabbed=0;
+ v=v->next;
+ }
+ }
+
g->objective_mult = gi->objective_mult;
g->intersection_mult = gi->intersection_mult;
}
Modified: trunk/planarity/graph_generate_mesh2.c
===================================================================
--- trunk/planarity/graph_generate_mesh2.c 2005-10-14 17:29:00 UTC (rev 10157)
+++ trunk/planarity/graph_generate_mesh2.c 2005-10-15 06:50:44 UTC (rev 10158)
@@ -49,6 +49,8 @@
graph *g;
int width;
int height;
+ int active_current;
+ int active_max;
} mesh;
// check for intersections with other edges
@@ -59,16 +61,20 @@
while(ge){
double xo,yo;
- // edges that share a vertex don't intersect by definition
- if(ge->A!=e->A && ge->A!=e->B && ge->B!=e->A && ge->B!=e->B)
- if(intersects(ge->A->orig_x,ge->A->orig_y,
- ge->B->orig_x,ge->B->orig_y,
- e->A->orig_x,e->A->orig_y,
- e->B->orig_x,e->B->orig_y,
- &xo,&yo)){
- count++;
- if(count>intersections)return 1;
- }
+ // edges that aren't in this region don't exist (for
+ // now) by definition
+ if(ge->A->active == m->active_current || ge->B->active == m->active_current){
+ // edges that share a vertex don't intersect by definition
+ if(ge->A!=e->A && ge->A!=e->B && ge->B!=e->A && ge->B!=e->B)
+ if(intersects(ge->A->orig_x,ge->A->orig_y,
+ ge->B->orig_x,ge->B->orig_y,
+ e->A->orig_x,e->A->orig_y,
+ e->B->orig_x,e->B->orig_y,
+ &xo,&yo)){
+ count++;
+ if(count>intersections)return 1;
+ }
+ }
ge=ge->next;
}
return 0;
@@ -108,7 +114,8 @@
vertex *v = m->g->verticies;
while(v){
- if(v!=e->A && v!=e->B && sq_line_distance(e,v)<16)return 1;
+ if(v->active == m->active_current)
+ if(v!=e->A && v!=e->B && sq_line_distance(e,v)<16)return 1;
v=v->next;
}
@@ -179,19 +186,22 @@
static void prepopulate(mesh *m,int length_limit){
// sort all verticies in ascending order by their number of potential edges
int i=0;
+ int num=0;
insort index[m->g->vertex_num];
vertex *v=m->g->verticies;
while(v){
- index[i].v=v;
- index[i].metric = select_available(m,v,0,0);
- i++;
+ if(v->active == m->active_current){
+ index[num].v=v;
+ index[num].metric = select_available(m,v,0,0);
+ num++;
+ }
v=v->next;
}
- qsort(index,m->g->vertex_num,sizeof(*index),insort_c);
+ qsort(index,num,sizeof(*index),insort_c);
// populate in ascending order
- for(i=0;i<m->g->vertex_num;i++){
+ for(i=0;i<num;i++){
int intersections=0;
int edges=0;
v = index[i].v;
@@ -311,7 +321,7 @@
// filter out already-walked edges
while(v){
- if(v->grabbed && v->selected){ // grabbed is also overloaded to mean not walked
+ if(v->grabbed && v->selected){ // grabbed is also overloaded to mean walked
v->selected = 0;
count--;
}
@@ -343,7 +353,7 @@
if(count){
vertex *v = m->g->verticies;
while(v){
- if(v->selected && random_yes(dense_128)){
+ if(v->active == m->active_current && v->selected && random_yes(dense_128)){
add_edge(m->g,v,current);
v->selected=0;
}
@@ -425,51 +435,47 @@
g->objective = 0;
g->objective_lessthan = 0;
-
+ m->active_max=0;
}
static void generate_mesh2(mesh *m, int density_128, float length_limit){
vertex *v;
+ int i;
length_limit*=50;
length_limit*=length_limit;
- if(have_region())
- prepopulate(m,0);
+ for(i=0;i<=m->active_max;i++){
+ m->active_current=i;
- /* connect the graph into as few discrete sections as possible */
- v = m->g->verticies;
- while(v){
- v->grabbed = 0;
+ if(have_region())
+ prepopulate(m,0);
+
+ /* connect the graph into as few discrete sections as possible */
+ v = m->g->verticies;
+ while(v){
+ v->grabbed = 0;
+ v=v->next;
+ }
+
+ v = m->g->verticies;
+ // make sure we walk all verticies
+ while(v){
+ if(v->active == m->active_current && !v->grabbed)
+ span_depth_first2(m, m->g->verticies, length_limit);
+ v=v->next;
+ }
+
+ if(!have_region())
+ prepopulate(m,length_limit);
+
+ /* now iterate the whole mesh adding random edges */
+ v=m->g->verticies;
+ while(v){
+ random_populate(m, v, density_128, length_limit);
v=v->next;
+ }
}
-
- v = m->g->verticies;
- // make sure we walk all verticies
- while(v){
- if(!v->grabbed)
- span_depth_first2(m, m->g->verticies, length_limit);
- v=v->next;
- }
-
- if(!have_region())
- prepopulate(m,length_limit);
-
- /* now iterate the whole mesh adding random edges */
- v=m->g->verticies;
- while(v){
- random_populate(m, v, density_128, length_limit);
- v=v->next;
- }
-
- /* clear out overloaded flags */
- v=m->g->verticies;
- while(v){
- v->grabbed=0;
- v=v->next;
- }
-
- deselect_verticies(m->g);
}
void generate_freeform(graph *g, int order){
@@ -529,7 +535,6 @@
min = 12;
break;
case 12: // target
- dens=128;
min = 14;
break;
}
@@ -566,5 +571,6 @@
arrange_region_target(g); break; //108
}
+ m.active_max=region_layout(g);
generate_mesh2(&m,dens,0);
}
Modified: trunk/planarity/graph_region.c
===================================================================
--- trunk/planarity/graph_region.c 2005-10-14 17:29:00 UTC (rev 10157)
+++ trunk/planarity/graph_region.c 2005-10-15 06:50:44 UTC (rev 10158)
@@ -38,6 +38,8 @@
typedef struct region_segment {
int layout; /* 0 no layout, 1 left, 2 right, 3 layout-only */
int cont; /* is this continuous from last line? */
+ int split; /* are we splitting the graph into interntionally
+ seperate regions here? */
float x1;
float y1;
@@ -64,6 +66,7 @@
int layout;
int cont;
+ int split_next;
} region;
static region r;
@@ -93,9 +96,11 @@
ret->x2=x2;
ret->y2=y2;
ret->cont = r->cont;
+ ret->split = r->split_next;
r->l=ret;
-
+ r->split_next=0;
+
return ret;
}
@@ -604,6 +609,7 @@
region_segment *n=new_segment(&layout_adj,rint(x1),rint(y1),rint(x2),rint(y2));
n->layout=3;
n->cont=(s->cont || endpath_adj);
+ n->split = s->split;
if(radius){
// circle; radius variable is treated as a flag
@@ -670,10 +676,11 @@
memset(&layout_adj,0,sizeof(layout_adj));
}
-void region_layout(graph *g){
+int region_layout(graph *g){
// count up the total length of the region segments used in layout
float length=0,acc=0,ldel;
int num_adj=g->vertex_num;
+ int activenum=0;
region_segment *l;
vertex *v = g->verticies;
@@ -714,6 +721,8 @@
float snap_del = l->cont ? l->length/num_placed : l->length/(num_placed-1);
float snap_acc=l->cont?snap_del:0;
+ if(l->split)activenum++;
+
if(l->radius==0){
float x1 = l->x1;
float y1 = l->y1;
@@ -729,6 +738,7 @@
if(snap_acc)
acc+=ldel;
snap_acc+=snap_del;
+ v->active=activenum;
v=v->next;
}
}else{
@@ -746,6 +756,7 @@
if(snap_acc)
acc+=ldel;
snap_acc+=snap_del;
+ v->active=activenum;
v=v->next;
}
}
@@ -753,6 +764,7 @@
acc-=l->length;
l=l->next;
}
+ return activenum;
}
void region_circle(int x,int y, float rad, int layout){
@@ -802,7 +814,11 @@
r.y=r.oy;
r.cont=0;
}
-
+
+void region_split_here(){
+ r.split_next=1;
+}
+
int region_intersects(edge *e){
region_segment *s=r.l;
Modified: trunk/planarity/graph_region.h
===================================================================
--- trunk/planarity/graph_region.h 2005-10-14 17:29:00 UTC (rev 10157)
+++ trunk/planarity/graph_region.h 2005-10-15 06:50:44 UTC (rev 10158)
@@ -27,7 +27,7 @@
extern void region_init();
extern int region_intersects(edge *e);
-extern void region_layout(graph *g);
+extern int region_layout(graph *g);
extern void region_circle(int x,int y, float rad, int layout);
extern void region_new_area(int x, int y, int layout);
extern void region_line_to(int x,int y);
@@ -35,3 +35,4 @@
extern void region_close_line();
extern void region_close_arc(float rad);
extern int have_region();
+extern void region_split_here();
Modified: trunk/planarity/version.h
===================================================================
--- trunk/planarity/version.h 2005-10-14 17:29:00 UTC (rev 10157)
+++ trunk/planarity/version.h 2005-10-15 06:50:44 UTC (rev 10158)
@@ -1,2 +1,2 @@
#define VERSION "$Id$ "
-/* DO NOT EDIT: Automated versioning hack [Fri Oct 14 08:19:48 EDT 2005] */
+/* DO NOT EDIT: Automated versioning hack [Sat Oct 15 02:46:25 EDT 2005] */
More information about the commits
mailing list