Parent

Execution

Author

Manuela Ruiz (mruiz@lcc.uma.es)

This class gathers the current grammar, constraints and goals in order to execute them (with Krishnamurti algorithms) and produce designs

Attributes

grammar[RW]

A Grammar object

current_shape[RW]

A CurrentLabelledShape object (the current design)

show_labels[RW]

True if we want the labels to appear in the current shape

execution_history[RW]

An array of pairs [rule_id, transformation] applied to the axiom, in order of application

file_axiom[RW]
backtracking_steps[RW]
show_backtracking_steps[RW]
constraints[RW]

An array of Constraint objects

goals[RW]

An array of Goals objects

timeout[R]

Timeout seconds for the backtracking algorithm If nil or 0, then no timeout will be considered

timeout_reached[RW]

True if the timeout has been reached

beginning_time[R]

Time when the last backtracking process started

Public Class Methods

new(grammar, current_shape) click to toggle source
grammar

the grammar to apply

current_shape

shape in which to store the design

     # File lib/main-structures.rb, line 437
437:         def initialize(grammar, current_shape)

438:                 @grammar= grammar

439:                 @current_shape = current_shape

440:                 @show_labels = true

441:                 @execution_history = Array.new

442:                 @file_axiom = false

443:                 @backtracking_steps = 0

444:                 @show_backtracking_steps = false

445:                 @constraints = Array.new

446:                 @goals = Array.new

447:                 

448:                 @timeout = nil

449:                 @timeout_reached = false

450:                 @beginning_time = 0

451:         end

Public Instance Methods

add_constraint(constraint) click to toggle source
Constraint

A Constraint object to add

return

true iff the Constraint was not added yet

Adds a Constraint to the project

     # File lib/main-structures.rb, line 518
518:         def add_constraint(constraint)

519:                 name = constraint.name

520:                 found = false

521:                 i = 0

522:                 size = @constraints.length

523:                 while i < size && !found

524:                         if @constraints[i].name == name

525:                                 found = true

526:                         end

527:                         i+=1

528:                 end

529:                 if !found   

530:                         @constraints.push constraint

531:                         Shade.project.saved = false

532:                 end

533:                 return !found

534:         end
add_goal(goal) click to toggle source
Goal

A Goal object to add

return

true iff the Goal was not added yet

Adds a Goal to the project

     # File lib/main-structures.rb, line 540
540:         def add_goal(goal)

541:                 name = goal.name

542:                 found = false

543:                 i = 0

544:                 size = @goals.length

545:                 while i < size && !found

546:                         if @goals[i].name == name

547:                                 found = true

548:                         end

549:                         i+=1

550:                 end

551:                 if !found   

552:                         @goals.push goal

553:                         Shade.project.saved = false

554:                 end

555:                 

556:                 return !found

557:         end
apply_goal_rules_random(show_backtracking_steps, timeout, n_max_rules) click to toggle source
show_backtracking_steps

true iff we want to see the steps

timeout

timeout for the backtracking algorithm. If it is zero, no timeout will be taken into account

return

true if the goals have been achieved

      # File lib/main-structures.rb, line 1317
1317:         def apply_goal_rules_random(show_backtracking_steps, timeout, n_max_rules)

1318:                 

1319:                 #Enable garbage collector

1320:                 GC.enable

1321:                 if !@goals.empty?

1322:                         t1 = Time.now

1323:                         reset #We need to start from the begining

1324:                         

1325:                         @backtracking_steps = 0

1326:                         @show_backtracking_steps = show_backtracking_steps

1327:                         

1328:                         if timeout != 0

1329:                           @timeout = timeout

1330:                           @timeout_reached = false

1331:                           @beginning_time = Time.now

1332:                           success = backtracking_goals(show_backtracking_steps, n_max_rules)

1333:                           if @timeout_reached

1334:                                  UI.messagebox("Timeout reached")

1335:                           end

1336:                           @timeout = nil

1337:                         else

1338:                           @timeout = nil

1339:                           success = backtracking_goals(show_backtracking_steps, n_max_rules)

1340:                         end

1341:                         

1342:                         @show_backtracking_steps = false

1343:                         t2 = Time.now

1344:                         #puts "Elapsed time: #{t2 - t1}"

1345:                 else

1346:                         success = 1

1347:                 end

1348:                 return success

1349:         end
apply_n_rules_random(n_rules, show_backtracking_steps) click to toggle source
n_rules

number of random rules to apply

show_backtracking_steps

true iff we want to see the steps

return

true if the desired number of rules has been applied

      # File lib/main-structures.rb, line 1240
1240:         def apply_n_rules_random(n_rules, show_backtracking_steps)

1241:                 reset #We need to start from the begining

1242:                 

1243:                 @backtracking_steps = 0

1244:                 @show_backtracking_steps = show_backtracking_steps

1245:                 

1246:                 t1 = Time.now

1247:                 success = backtracking(0, n_rules, show_backtracking_steps)

1248:                 t2 = Time.now

1249:                 

1250:                 #puts "Elapsed time: #{t2 - t1}"

1251:                 

1252:                 @show_backtracking_steps = false

1253:                 

1254:                 return success

1255:         end
apply_rule(rule_id, transformation = nil, print = false) click to toggle source
rule_id

internal id of the rule to apply to the current shape

transformation

optional argument; when it is specified, the possible transformations of the rule corresponding to rule_id are not computed

Applies the specified rule to the current shape.

      # File lib/main-structures.rb, line 833
 833:         def apply_rule(rule_id, transformation = nil, print = false)

 834:                 applied = nil

 835:                 rule = @grammar.search_rule_by_id(rule_id)

 836:                 

 837:                 #By deffinition, all our alpha shapes have at least three distinct labelled points that form a triangle, since in the initialization of

 838:                 #shapes, an Error is raised when this condition does not hold.

 839:                 

 840:                 #If there are labels in alpha that do not exist in the current shape, then the rule cannot be applied

 841:                 possible = true

 842:                 @current_shape.p.each_key { |layer_name|

 843:                         

 844:                         current_labels = @current_shape.p[layer_name]

 845:                         alpha_labels = rule.alpha.p[layer_name]

 846:                         if alpha_labels

 847:                                 alpha_labels.reset_iterator

 848:                                 

 849:                                 while (possible && (alpha_label_node = alpha_labels.get_next))

 850:                                         current_label_node = current_labels.get_node(alpha_label_node.key)

 851:                                         if !current_label_node 

 852:                                                 #If an alpha label value do not exist in the current shape, then the rule cannot be applied

 853:                                                 possible = false

 854:                                         elsif current_label_node.list.size < alpha_label_node.list.size

 855:                                                 #If for a given value of an alpha label, there are less points in the current shape than in the alpha shape,

 856:                                                 #then the rule cannot be applied

 857:                                                 possible = false

 858:                                         end

 859:                                 end

 860:                         end

 861:                         

 862:                 }     

 863:                 

 864:                 #If the rule can by this moment be applied

 865:                 if possible

 866:                         if transformation

 867:                                 flag_s= @current_shape.shape_expression(rule.alpha.transform(transformation),Constants::SUBSHAPE, Constants::SEGMENTS)

 868:                                 flag_p = @current_shape.shape_expression(rule.alpha.transform(transformation),Constants::SUBSHAPE, Constants::POINTS)

 869:                                 if (flag_s && flag_p) #The transformed alpha is a subshape of the current shape

 870:                                         #Apply the rule

 871:                                         @execution_history.push [rule_id, transformation, @current_shape.clone]

 872:                                         t_alpha_minus_beta = rule.alpha_minus_beta.transform(transformation)

 873:                                         t_beta_minus_alpha = rule.beta_minus_alpha.transform(transformation)

 874:                                         

 875:                                         @current_shape.shape_expression(t_alpha_minus_beta, Constants::DIFFERENCE, Constants::SEGMENTS)

 876:                                         @current_shape.shape_expression(t_alpha_minus_beta, Constants::DIFFERENCE, Constants::POINTS)

 877:                                         

 878:                                         @current_shape.shape_expression(t_beta_minus_alpha, Constants::UNION, Constants::SEGMENTS)

 879:                                         @current_shape.shape_expression(t_beta_minus_alpha, Constants::UNION, Constants::POINTS)

 880:                                         

 881:                                         applied = true

 882:                                         

 883:                                         

 884:                                         

 885: 

 886:                                         #We see if the Constraints are complied

 887:                                         i = 0

 888:                                         size = @constraints.size

 889:                                         complied = true

 890:                                         while i < size && complied

 891:                                                 complied = @constraints[i].satisfied?()

 892:                                                 i += 1

 893:                                         end

 894:                                         

 895:                                         if !complied

 896: 

 897:                                                 undo

 898:                                                 applied = false

 899: 

 900:                                         end        

 901:                                 else

 902:                                         #puts "Not a subshape. Transformation: #{transformation}. Flag s: #{flag_s}. Flag p: #{flag_p}"

 903:                                         puts "Not a subshape"

 904:                                 end

 905:                                 

 906:                                 

 907:                         else

 908:                                 #Choose first layer with at least three points in the left shape (we need it in order to compute the transformation)

 909:                                 found = false

 910:                                 i = 0

 911:                                 layer_name = "Layer0"

 912:                                 #TODO: put a while

 913:                                 rule.alpha.p.each_key {|l_n|

 914:                                         

 915:                                         if !found

 916:                                                 if (rule.alpha.p[l_n])

 917:                                                         n_points = 0

 918:                                                         rule.alpha.p[l_n].reset_iterator

 919:                                                         while (n = rule.alpha.p[l_n].get_next)

 920:                                                                 n_points += n.list.size

 921:                                                         end

 922:                                                         found = (n_points > 2)

 923:                                                         if found

 924:                                                                 layer_name = l_n

 925:                                                                 #puts layer_name

 926:                                                         end

 927:                                                 end

 928:                                         end

 929:                                         

 930:                                         i += 1

 931:                                 }

 932:                                 #We suppose that there is always one non-empty layer

 933:                                 possible_ts = possible_transformations(rule, layer_name, nil, true)

 934:                                 #possible_ts = first_possible_transformation(rule)

 935:                                 

 936:                                 if !possible_ts.empty? #Then the rule can be applied to the current shape

 937:                                         #puts "#{possible_ts.length} possible transformations of rule #{rule_id}"

 938:                                         #Randomly choose the transformation to apply

 939:                                         i = rand(possible_ts.size)

 940:                                         chosen_transformation = possible_ts[i]

 941:                                         

 942:                                         #Apply the rule

 943:                                         @execution_history.push [rule_id, chosen_transformation, @current_shape.clone]

 944:                                         t_alpha_minus_beta = rule.alpha_minus_beta.transform(chosen_transformation)

 945:                                         t_beta_minus_alpha = rule.beta_minus_alpha.transform(chosen_transformation)

 946: 

 947:                                         @current_shape.shape_expression(t_alpha_minus_beta, Constants::DIFFERENCE, Constants::SEGMENTS)

 948:                                         @current_shape.shape_expression(t_alpha_minus_beta, Constants::DIFFERENCE, Constants::POINTS)

 949:                                         

 950:                                         @current_shape.shape_expression(t_beta_minus_alpha, Constants::UNION, Constants::SEGMENTS)

 951:                                         @current_shape.shape_expression(t_beta_minus_alpha, Constants::UNION, Constants::POINTS)

 952:                                                                                 

 953:                                         applied = true

 954:                                         

 955:                                         #We see if the Constraints are complied

 956:                                         j = 0

 957:                                         size = @constraints.size

 958:                                         complied = true

 959:                                         while j < size && complied

 960:                                                 complied = @constraints[j].satisfied?()

 961:                                                 j += 1

 962:                                         end

 963:                                         

 964:                                         if !complied

 965:                                                 possible_ts.delete_at i

 966:                                                 undo

 967:                                                 applied = false

 968:                                         end        

 969:                                         

 970:                                         while (!possible_ts.empty? && !complied)

 971:                                                 

 972:                                                 i = rand(possible_ts.size)

 973:                                                 chosen_transformation = possible_ts[i]

 974:                                                 #Apply the rule

 975:                                                 @execution_history.push [rule_id, chosen_transformation, @current_shape.clone]

 976:                                                 t_alpha_minus_beta = rule.alpha_minus_beta.transform(chosen_transformation)

 977:                                                 t_beta_minus_alpha = rule.beta_minus_alpha.transform(chosen_transformation)

 978:                                                 

 979:                                                 @current_shape.shape_expression(t_alpha_minus_beta, Constants::DIFFERENCE, Constants::SEGMENTS)

 980:                                                 @current_shape.shape_expression(t_alpha_minus_beta, Constants::DIFFERENCE, Constants::POINTS)

 981:                                                 

 982:                                                 @current_shape.shape_expression(t_beta_minus_alpha, Constants::UNION, Constants::SEGMENTS)

 983:                                                 @current_shape.shape_expression(t_beta_minus_alpha, Constants::UNION, Constants::POINTS)

 984:                                                 

 985:                                                 applied = true

 986:                                                 

 987:                                                 #We see if the Constraints are complied

 988:                                                 j = 0

 989:                                                 size = @constraints.size

 990:                                                 complied = true

 991:                                                 while j < size && complied

 992:                                                         complied = @constraints[j].satisfied?()

 993:                                                         j += 1

 994:                                                 end

 995:                                                 

 996:                                                 if !complied

 997:                                                         possible_ts.delete_at i

 998:                                                         undo

 999:                                                         applied = false

1000:                                                 end       

1001: 

1002:                                         end

1003:                                 end

1004:                         end

1005:                         

1006:                         if applied 

1007:                                 @current_shape.create_pi

1008:                                 if Shade.using_sketchup

1009:                                         @current_shape.refresh(@show_labels)

1010:                                         if @show_backtracking_steps

1011:                                                 Sketchup.active_model.active_view.refresh

1012:                                                 sleep(Constants::DELAY_TIME)

1013:                                         end

1014:                                 end

1015:                         end

1016:                         

1017:                 end

1018:                 

1019:                 return applied

1020:         end
apply_rule_random() click to toggle source

Applies a random rule to the current shape

      # File lib/main-structures.rb, line 1161
1161:         def apply_rule_random()

1162:                 rules_index = Array.new

1163:                 for i in 0..(@grammar.rules.size-1)

1164:                         rules_index[i] = i

1165:                 end

1166:                 

1167:                 applied = false

1168:                 

1169:                 while (!applied && !rules_index.empty?)

1170:                         random_rule_index = rules_index[rand(rules_index.size)]

1171:                         random_rule_id = @grammar.rules[random_rule_index].rule_id

1172:                         applied = self.apply_rule(random_rule_id)

1173:                         

1174:                         if !applied

1175:                                 rules_index.delete random_rule_index

1176:                         end

1177:                 end

1178:                 return applied

1179:                 

1180:         end
backtracking(n_applied, n_total, show_backtracking_steps) click to toggle source
n_applied

number of applied rules before calling this method

n_total

number of rules to applu

show_backtracking_steps

true iff we want to see the backtracking steps

Applies rules in a backtracking process, until the solution is reached or the solution space is empty, thus there is no possible solution. returns true if the solution has been reached

      # File lib/main-structures.rb, line 1264
1264:         def backtracking(n_applied, n_total, show_backtracking_steps)

1265:                 if n_total > 0 #If we have some rules to apply...

1266:                         

1267:                         # Generate brothers (possible next steps) of this level

1268:                         brothers = brothers()

1269:                         

1270:                         # Do backtracking with the generated brothers

1271:                         solution = false

1272:                         while brothers.length > 0 && !solution #While more brothers are available and the solution is not reached...

1273:                                 

1274:                                 #We randomly choose the brother to apply

1275:                                 brother = brothers[rand(brothers.size)]

1276:                                 

1277:                                 #brother[0] is the rule id; brother[1] is the transformation

1278:                                 #Now we have the information to apply the rule

1279:                                 applied = apply_rule(brother[0], brother[1])

1280:                                 

1281:                                 @backtracking_steps += 1

1282:                                 

1283:                                 if !applied #The step is not feasible

1284:                                         #Delete our current brother

1285:                                         brothers.delete brother

1286:                                 else #The step is feasible

1287:                                         if n_applied == n_total - 1 #If we have applied the number of desired rules...

1288:                                                 #Then we have the solution!

1289:                                                 solution = true

1290:                                         else #If we have not reached the number of rules to apply...

1291:                                                 #We need to apply the remaining number of rules

1292:                                                 solution = backtracking(n_applied + 1, n_total, show_backtracking_steps)

1293: 

1294:                                                 if !solution #If we do not reach the solution with this brother...

1295:                                                         @show_backtracking_steps = false

1296:                                                         #Undo the last step (the one of the last brother applied)

1297:                                                         undo

1298:                                                         @show_backtracking_steps = show_backtracking_steps

1299:                                                         #Delete our current brother

1300:                                                         brothers.delete brother

1301:                                                 end

1302:                                         end

1303:                                 end

1304:                         end  

1305:                 else #If the number of rules to apply is zero, we can always satisfy the request ;-)

1306:                         solution = true

1307:                 end

1308:                 

1309:                 #Finally, return the solution

1310:                 return solution

1311:         end
backtracking_goals(show_backtracking_steps, n_max_rules) click to toggle source
show_backtracking_steps

true iff we want to see the backtracking steps

Applies rules in a backtracking process, until the goals are satisfied or the solution space is empty, thus there is no possible solution. returns true if the solution has been reached

      # File lib/main-structures.rb, line 1356
1356:         def backtracking_goals(show_backtracking_steps, n_max_rules)

1357:                 

1358:                 if !self.goals_satisfied?() #If we have not reached the solution...

1359:                         

1360:                         GC.start

1361:                         # Generate brothers (possible next steps) of this level

1362:                         #puts "Calculando brothers"

1363:                         a_brothers = brothers()

1364:                         

1365:                         # Do backtracking with the generated brothers

1366:                         solution = false

1367:                         while ((a_brothers.length > 0) && (!solution)) #While more brothers are available and the solution is not reached...

1368:                                 

1369:                                 

1370:                                 #We randomly choose the brother to apply

1371:                                 brother = a_brothers[rand(a_brothers.size)]

1372:                                 

1373:                                 #brother[0] is the rule id; brother[1] is the shape index

1374:                                 #Now we have the information to apply the rule

1375:                                 #puts "Aplicando regla #{brother[0]}"

1376:                                 applied = apply_rule(brother[0], brother[1])

1377:                                 

1378:                                 @backtracking_steps += 1

1379:                                 

1380:                                 if !applied #The step is not feasible (i.e., the Constraints are not complied)

1381:                                         #Delete our current brother

1382:                                         

1383:                                         a_brothers.delete brother

1384:                                         #puts "Borrando brother, regla no aplicada. Quedan #{a_brothers.size} brothers"

1385:                                 else #The step is feasible (i.e., the Constraints are complied)

1386:                                         if self.goals_satisfied?() #If the design satisfies the present goals

1387:                                                 #Then we have the solution!

1388:                                                 #puts "Solución alcanzada"

1389:                                                 solution = true

1390:                                         else #If we have not reached the solution...

1391:                                                 #puts "backtracking goals #{Time.now}"

1392:                                                 # IF we have reached the maximum number of applications

1393:                                                 if (n_max_rules && (@execution_history.size == n_max_rules))

1394:                                                         #puts "Número máximo de reglas alcanzado"

1395:                                                         #We do not follow this path; it is too large

1396:                                                         @show_backtracking_steps = false

1397:                                                         #Undo the last step (the one of the last brother applied)

1398:                                                         undo

1399:                                                         @show_backtracking_steps = show_backtracking_steps

1400:                                                         #Delete our current brother

1401:                                                         a_brothers.delete brother

1402:                                                 else

1403:                                                         #We need to apply the remaining number of rules

1404:                                                         #puts "Backtracking"

1405:                                                         solution = backtracking_goals(show_backtracking_steps, n_max_rules)

1406: 

1407:                                                         #puts "Borrando brother, solución no alcanzada por este camino"

1408:                                                         if !solution #If we do not reach the solution with this brother...

1409:                                                                 @show_backtracking_steps = false

1410:                                                                 #Undo the last step (the one of the last brother applied)

1411:                                                                 undo

1412:                                                                 @show_backtracking_steps = show_backtracking_steps

1413:                                                                 #Delete our current brother

1414:                                                                 a_brothers.delete brother

1415:                                                         end

1416:                                                 end

1417:                                         end

1418:                                 end

1419:                         end  

1420:                 else #If we have reached the solution...

1421:                         solution = true

1422:                 end

1423:                 

1424:                 #Finally, return the solution

1425:                 return solution

1426:         end
brothers(shape = nil) click to toggle source
shape

optional argument; when it is specified, the possible brothers are computed over it instead of the current shape

returns

an array of pairs [rule_id, transformation] that can be applied to shape when specified, and to the current shape otherwise

      # File lib/main-structures.rb, line 1186
1186:         def brothers(shape = nil)

1187:                 brothers = Array.new

1188:                 show = false

1189:                 

1190:                 if @show_backtracking_steps

1191:                         show = true

1192:                         @show_backtracking_steps = false

1193:                 end

1194:                 

1195:                 @grammar.rules.each {|r|

1196:                         #Choose first non-empty layer

1197:                         found = false

1198:                         i = 0

1199:                         n_layers = r.alpha.p.keys.length

1200:                         layer_name = "Layer0"

1201:                         keys = r.alpha.p.keys

1202:                         while ((i < keys.size)&&(!found))

1203:                                 l_n = keys[i]

1204:                                 

1205:                                 if !found

1206:                                         if (r.alpha.p[l_n])

1207:                                                 n_points = 0

1208:                                                 r.alpha.p[l_n].reset_iterator

1209:                                                 while (n = r.alpha.p[l_n].get_next)

1210:                                                         n_points += n.list.size

1211:                                                 end

1212:                                                 found = (n_points > 2)

1213:                                         end

1214:                                         if found

1215:                                                 layer_name = l_n

1216:                                         end

1217:                                 end

1218:                                 

1219:                                 i += 1

1220:                         end

1221:                         

1222:                         possible_ts = possible_transformations(r, layer_name, shape)

1223:                         possible_ts.each {|t|

1224:                                 brothers.push [r.rule_id, t]

1225:                         }

1226:                 }

1227:                 

1228:                 if show

1229:                         @show_backtracking_steps = true

1230:                 end

1231:                 

1232:                 return brothers

1233:         end
cramer(m, b) click to toggle source

Auxiliar method for computing the determinant of a matrix

     # File lib/main-structures.rb, line 709
709:         def cramer(m, b)

710:                 result = Array.new

711:                 det = determinant(m)

712:                 

713:                 for i in 0..2

714:                         c = substitute(m,b,i)

715:                         

716:                         temp_det = determinant(c)

717:                         

718:                         result[i] = temp_det/det

719:                 end

720:                 

721:                 return result

722:         end
delete_constraint(name) click to toggle source

name: name of the Constraint to delete

return

true if the Constraint had been added previously

Deletes the Constraint whose name is equal to name

     # File lib/main-structures.rb, line 563
563:         def delete_constraint(name)

564:                 found = false

565:                 i = 0

566:                 size = @constraints.length

567:                 while i < size && !found

568:                         if @constraints[i].name == name

569:                                 found = true

570:                                 constraint = @constraints[i]

571:                                 constraint.delete()

572:                                 @constraints.delete_at(i)

573:                         end

574:                         i+=1

575:                 end

576:          

577:                 if found 

578:                         Shade.project.saved = false

579:                 end

580:                 return found

581:         end
delete_goal(name) click to toggle source

name: name of the goal to delete

return

true if the goal had been added previously

Deletes the goal whose name is equal to name

     # File lib/main-structures.rb, line 587
587:         def delete_goal(name)

588:                 found = false

589:                 i = 0

590:                 size = @goals.length

591:                 while i < size && !found

592:                         if @goals[i].name == name

593:                                 found = true

594:                                 goal = @goals[i]

595:                                 goal.delete()

596:                                 @goals.delete_at(i)

597:                         end

598:                         i+=1

599:                 end

600:          

601:                 if found 

602:                         Shade.project.saved = false

603:                 end

604:                 return found

605:         end
determinant(m) click to toggle source
m

a matrix

returns

the determinant of matrix m

     # File lib/main-structures.rb, line 747
747:         def determinant(m)

748:                 #Sarrus rule

749:                 det = (m[0][0]*m[1][1]*m[2][2]) + (m[0][1]*m[1][2]*m[2][0]) + (m[0][2]*m[1][0]*m[2][1])- ((m[0][2]*m[1][1]*m[2][0]) + (m[0][1]*m[1][0]*m[2][2]) + (m[0][0]*m[1][2]*m[2][1]))

750:                 

751:                 return det

752:         end
eql_c_eps(c1, c2, c3) click to toggle source
c1

a float number

c2

a float number

c3

a float number

returns

true if the three numbers are equal with a tolerance given by Constants::EPSILON

      # File lib/main-structures.rb, line 1151
1151:         def eql_c_eps(c1, c2, c3)

1152:                 dif1 = (c1 - c2).abs

1153:                 result = (dif1 < Constants::EPSILON)

1154:                 dif2 = (c2 - c3).abs

1155:                 result = (result && (dif2 < Constants::EPSILON))

1156:         end
execute_until_end() click to toggle source

Executes the grammar until no more rules can be applied. Be careful: it can turns into an endless loop

      # File lib/main-structures.rb, line 1478
1478:         def execute_until_end

1479:                 #puts "Applying rules..."

1480:                 applied = true

1481:                 while applied

1482:                         applied = apply_rule_random()

1483:                 end

1484:                 #puts "End reached"

1485:         end
get_constraint(name) click to toggle source
name

a constraint name

Gets the Constraint object responding to name

     # File lib/main-structures.rb, line 610
610:         def get_constraint(name)

611:                 found = false

612:                 constraint = nil

613:                 i = 0

614:                 size = @constraints.length

615:                 while i < size && !found

616:                         if  @constraints[i].name == name

617:                                 found = true

618:                                 constraint =  @constraints[i]

619:                         end

620:                         i+=1

621:                 end

622:                 return constraint

623:         end
get_goal(name) click to toggle source
name

a goal name

Gets the Goal object responding to name

     # File lib/main-structures.rb, line 628
628:         def get_goal(name)

629:                 found = false

630:                 goal = nil

631:                 i = 0

632:                 size = @goals.length

633:                 while i < size && !found

634:                         if  @goals[i].name == name

635:                                 found = true

636:                                 goal =  @goals[i]

637:                         end

638:                         i+=1

639:                 end

640:                 return goal

641:         end
get_transformation(dp_alpha, dp_current) click to toggle source
dp_alpha

Array with three points of the left shape of a Rule. This three points have to form a triangle.

dp_current::Array with three points of the current shape. This three points have to form an equivalent triangle to that of dp_alpha

returns

the transformation that has to be applied in order to convert the triangle formed by dp_alpha into the one formed by dp_current.

The transformation is an Array of six positions [a, b, c, d, e, f]; c and f are the traslation coefficients and a, b, d, e are the scale and rotation factors.

     # File lib/main-structures.rb, line 770
770:         def get_transformation(dp_alpha, dp_current)

771:                 #Construct the x-matrix

772:                 m_x = Array.new

773:                 b_x = Array.new

774:                 

775:                 m_x[0] = Array.new

776:                 m_x[0][0] = dp_alpha[0].x

777:                 m_x[0][1] = dp_alpha[0].y

778:                 m_x[0][2] = 1

779:                 b_x[0] = dp_current[0].x

780:                 

781:                 m_x[1] = Array.new

782:                 m_x[1][0] = dp_alpha[1].x

783:                 m_x[1][1] = dp_alpha[1].y

784:                 m_x[1][2] = 1

785:                 b_x[1] = dp_current[1].x

786:                 

787:                 m_x[2] = Array.new

788:                 m_x[2][0] = dp_alpha[2].x

789:                 m_x[2][1] = dp_alpha[2].y

790:                 m_x[2][2] = 1

791:                 b_x[2] = dp_current[2].x

792:                 

793:                 coef_x = cramer(m_x, b_x)

794:                 

795:                 #Construct the y-matrix

796:                 m_y = Array.new

797:                 b_y = Array.new

798:                 

799:                 m_y[0] = Array.new

800:                 m_y[0][0] = dp_alpha[0].x

801:                 m_y[0][1] = dp_alpha[0].y

802:                 m_y[0][2] = 1

803:                 b_y[0] = dp_current[0].y

804:                 

805:                 m_y[1] = Array.new

806:                 m_y[1][0] = dp_alpha[1].x

807:                 m_y[1][1] = dp_alpha[1].y

808:                 m_y[1][2] = 1

809:                 b_y[1] = dp_current[1].y

810:                 

811:                 m_y[2] = Array.new

812:                 m_y[2][0] = dp_alpha[2].x

813:                 m_y[2][1] = dp_alpha[2].y

814:                 m_y[2][2] = 1

815:                 b_y[2] = dp_current[2].y

816:                 

817:                 coef_y = cramer(m_y, b_y)

818:                 

819:                 result = Array.new

820:                 for i in 0..2

821:                         result[i] = coef_x[i]

822:                 end

823:                 for i in 3..5

824:                         result[i] = coef_y[i-3]

825:                 end

826:                 return result

827:         end
goals_satisfied?() click to toggle source
returns

true iff every present goal is satisfied. If no goals are present, it returns true

      # File lib/main-structures.rb, line 1429
1429:         def goals_satisfied?

1430:                 satisfied = true

1431:                 size = @goals.length

1432:                 i = 0

1433:                 while i < size && satisfied

1434:                         satisfied = @goals[i].satisfied?

1435:                         i+=1

1436:                 end

1437:                 return satisfied

1438:         end
load_execution_history(directory) click to toggle source
directory

the directory to load the execution history from

Loads the execution history (that is, the sequence of applied rules and the produced shape in each step) from the specified directory

     # File lib/main-structures.rb, line 488
488:         def load_execution_history(directory)

489:                 @execution_history = Array.new

490:                 if File.exist? "#{directory}\\entries.txt"

491:                         j = 0

492:                         File.open("#{directory}\\entries.txt", 'r') do |f|

493:                                 while (line = f.gets)

494:                                         line_a = line.split(",")

495:                                         

496:                                         if line_a.size > 1

497:                                                 rule_id = line_a[0].to_i

498:                                                 t = Array.new(6)

499:                                                 for i in 1..6

500:                                                         t[i-1] = line_a[i].to_f

501:                                                 end

502:                                                 

503:                                                 shape = CurrentLabelledShape.new([], [])

504:                                                 shape.load("#{directory}\\shape#{j}.txt")

505:                                                 

506:                                                 @execution_history.push [rule_id, t, shape]

507:                                                 j += 1

508:                                         end

509:                                 end

510:                         end

511:                 end

512:         end
possible_transformations(rule, layer_name, shape = nil, print = false) click to toggle source
rule

a Rule object

layer_name

the name of the affected layer

shape

optional argument; when it is specified, the possible transformations are computed over it instead of the current shape

returns

an array with all the possible transformations that can be applied to the left part of the specified rule in order to become

a subshape of the specified shape, or the current shape when there is no specified shape

      # File lib/main-structures.rb, line 1029
1029:         def possible_transformations(rule, layer_name, shape = nil, print = false)

1030:                 if !shape

1031:                         shape = @current_shape

1032:                 end

1033:                 #Step 1: Compute the fixed distinguishable points associated with rule.alpha (dp_alpha). They must form a triangle

1034:                 dp_alpha = Array.new #Fixed distinguishable points

1035:                 map = Array.new 

1036:                 possible_transformations = Array.new

1037:                 f = 3 #Shapes of type 1, because we force the existence of at least three distinguishable points forming a triangle

1038:                 #Step 1.1

1039:                 dptr = k = 1

1040:                 #Step 1.2

1041:                 step_1_2_dist_points(rule, dp_alpha, map, f, dptr, k, layer_name)

1042:                 if (dp_alpha.size == 3)

1043:                         #Pre-compute the l's of the formed triangle (l is the square of the distance between two points)

1044:                         l_alpha = Array.new

1045:                         #For the points 0 and 1

1046:                         l_alpha[0] = (((dp_alpha[0].y - dp_alpha[1].y)**2) + ((dp_alpha[0].x - dp_alpha[1].x)**2))

1047:                         #For the points 1 and 2

1048:                         l_alpha[1] = (((dp_alpha[1].y - dp_alpha[2].y)**2) + ((dp_alpha[1].x - dp_alpha[2].x)**2))

1049:                         #For the points 2 and 0

1050:                         l_alpha[2] = (((dp_alpha[2].y - dp_alpha[0].y)**2) + ((dp_alpha[2].x - dp_alpha[0].x)**2))

1051:                         #puts "dp_alpha[0]: #{dp_alpha[0].x}, #{dp_alpha[0].y}"

1052:                         #puts "dp_alpha[1]: #{dp_alpha[1].x}, #{dp_alpha[1].y}"

1053:                         #puts "dp_alpha[2]: #{dp_alpha[2].x}, #{dp_alpha[2].y}"

1054:                         

1055:                         #Step 2: [Backtracking process] Generate all possible mappings from dp_alpha to the current shape

1056:                         #Step 2.1

1057:                         index = Array.new

1058:                         dp_current = Array.new

1059:                         dptr = 0

1060:                         

1061:                         current_point_node = shape.p[layer_name].get_node_i(map[dptr]).list.first

1062:                         while (dptr >= 0)

1063:                                 while current_point_node

1064:                                         do_next = true

1065:                                         if !current_point_node.list #The point has not been selected previously

1066:                                                 point_bis = current_point_node.key

1067:                                                 i = 0

1068:                                                 found = false

1069:                                                 while (i < dptr) && !found

1070:                                                         if (point_bis == dp_current[i])

1071:                                                                 found = true

1072:                                                         end

1073:                                                         i+=1

1074:                                                 end

1075:                                                 if !found #point_bis is distinct from the already selected points

1076:                                                         dp_current[dptr] = point_bis

1077:                                                         if dptr < 2

1078:                                                                 index[dptr] = current_point_node

1079:                                                                 current_point_node.list = 1

1080:                                                                 dptr += 1

1081:                                                                 do_next = false

1082:                                                                 current_point_node = shape.p[layer_name].get_node_i(map[dptr]).list.first

1083:                                                         else #we now have three points to do a mapping

1084:                                                                 #We have to check if they form a triangle

1085: 

1086:                                                                 #puts "dp_current[0]: #{dp_current[0].x}, #{dp_current[0].y}"

1087:                                                                 #puts "dp_current[1]: #{dp_current[1].x}, #{dp_current[1].y}"

1088:                                                                 #puts "dp_current[2]: #{dp_current[2].x}, #{dp_current[2].y}"

1089:                                                                 segment1 = Segment.new(OrderedPoint.new(dp_current[0]), OrderedPoint.new(dp_current[1]))

1090:                                                                 segment2 = Segment.new(OrderedPoint.new(dp_current[1]), OrderedPoint.new(dp_current[2]))

1091:                                                                 if (segment1.line_descriptor.sine != segment2.line_descriptor.sine) 

1092:                                                                         #The lines are not collinear (they are always in the first and fourth quadrant and thus we can use the sine)

1093:                                                                         #Now we have to check if the triangles are similar

1094:                                                                         l_current = Array.new

1095:                                                                         #For the points 0 and 1

1096:                                                                         l_current[0] = (((dp_current[0].y - dp_current[1].y)**2) + ((dp_current[0].x - dp_current[1].x)**2))

1097:                                                                         #For the points 1 and 2

1098:                                                                         l_current[1] = (((dp_current[1].y - dp_current[2].y)**2) + ((dp_current[1].x - dp_current[2].x)**2))

1099:                                                                         #For the points 2 and 0

1100:                                                                         l_current[2] = (((dp_current[2].y - dp_current[0].y)**2) + ((dp_current[2].x - dp_current[0].x)**2))

1101:                                                                         c = Array.new

1102:                                                                         #For the points 0 and 1

1103:                                                                         c[0] = (l_current[0]/l_alpha[0])

1104:                                                                         #For the points 1 and 2

1105:                                                                         c[1] = (l_current[1]/l_alpha[1])

1106:                                                                         #For the points 2 and 0

1107:                                                                         c[2] = (l_current[2]/l_alpha[2])       

1108:                                                                         #puts "c's: #{c[0]}, #{c[1]}, #{c[2]}"

1109:                                                                         if (eql_c_eps(c[0], c[1], c[2]))

1110:                                                                                 t = get_transformation(dp_alpha, dp_current)

1111:                                                                                 #puts t

1112:                                                                                 flag_s=  shape.shape_expression(rule.alpha.transform(t), Constants::SUBSHAPE, Constants::SEGMENTS, print)

1113:                                                                                 flag_p = shape.shape_expression(rule.alpha.transform(t), Constants::SUBSHAPE, Constants::POINTS, print)

1114:                                                                                 

1115:                                                                                 #if print

1116:                                                                                         #puts "flag_s: #{flag_s}"

1117:                                                                                         #puts "flag_p: #{flag_p}"

1118:                                                                                         #puts "-----------------"

1119:                                                                                 #end

1120:                                                                                 

1121:                                                                                 if (flag_s && flag_p) #The transformed alpha is a subshape of the current shape

1122:                                                                                         possible_transformations.push t

1123:                                                                                 end

1124:                                                                         end

1125:                                                                 end

1126:                                                         end

1127:                                                 end

1128:                                         end

1129:                                         if do_next

1130:                                                 current_point_node = current_point_node._next

1131:                                         end

1132:                                 end

1133:                                 #Backtrack

1134:                                 dptr = dptr - 1

1135:                                 if dptr >= 0

1136:                                         current_point_node = index[dptr] #The previous selection

1137:                                         current_point_node.list = nil

1138:                                         current_point_node = current_point_node._next

1139:                                 end

1140:                         end

1141:                 end

1142:                 return possible_transformations

1143:         end
reset() click to toggle source

Resets the execution, so the current shape becomes the axiom again

      # File lib/main-structures.rb, line 1452
1452:         def reset

1453:                 @execution_history = Array.new

1454:                 if @current_shape

1455:                         @current_shape.erase

1456:                 end

1457:                 

1458:                 @current_shape = CurrentLabelledShape.new(Array.new, Array.new)

1459:                 

1460:                 @grammar.axiom.p.each_key {|layer_name|

1461:                         @current_shape.p[layer_name] = @grammar.axiom.p[layer_name].clone

1462:                 }

1463:                 

1464:                 @grammar.axiom.s.each_key {|layer_name|

1465:                         @current_shape.s[layer_name] = BalancedBinaryTree.new

1466:                         @grammar.axiom.s[layer_name].reset_iterator

1467:                         while (s_node = @grammar.axiom.s[layer_name].get_next)

1468:                                 @current_shape.s[layer_name].insert_node BalancedBinaryTreeNode.new(0, nil, nil, s_node.key, s_node.list.clone)

1469:                         end

1470:                 }

1471:                 

1472:                 @current_shape.create_pi

1473:                 @current_shape.paint(@show_labels)

1474:         end
save_execution_history(directory) click to toggle source
directory

the directory to save the execution history in

Saves the execution history (that is, the sequence of applied rules and the produced shape in each step) into the specified directory

     # File lib/main-structures.rb, line 456
456:         def save_execution_history(directory)

457:                 if @execution_history

458:                         if @execution_history.size > 0

459:                                 if File.exist? "#{directory}\\entries.txt"

460:                                         File.delete("#{directory}\\entries.txt")

461:                                 end

462:                                 File.open("#{directory}\\entries.txt", 'w') do |f|

463:                         

464:                                         execution_history.each{ |entry|

465:                                                 t_string = nil

466:                                                 entry[1].each { |e|

467:                                                         if t_string

468:                                                                 t_string = "#{t_string},#{e}"

469:                                                         else

470:                                                                 t_string = "#{e}"

471:                                                         end

472:                                                 }

473:                                                 #puts t_string

474:                                                 f.write "#{entry[0]},#{t_string}\n"

475:                                         }

476:                                 

477:                                 end

478:                                 execution_history.each_with_index{ |entry, i|

479:                                         entry[2].save("#{directory}\\shape#{i}.txt")

480:                                 }

481:                         end

482:                 end

483:         end
step_1_2_dist_points(rule, dp_alpha, map, f, dptr, k, layer_name) click to toggle source

A step of Krishnamurti algorithm

     # File lib/main-structures.rb, line 654
654:         def step_1_2_dist_points(rule, dp_alpha, map, f, dptr, k, layer_name)

655:                 k += 1

656:             if !@current_shape.pi[layer_name]

657:               @current_shape.create_pi

658:             end

659:                 #if @current_shape.pi[layer_name]

660:                         if @current_shape.pi[layer_name].get_node_i(k)

661:                                 pik = @current_shape.pi[layer_name].get_node_i(k).list #The index of the kth largest set of labelled points in the current shape

662:                                 #puts "k: #{k}, pik: #{pik}"

663:                                 node_pik = @current_shape.p[layer_name].get_node_i(pik) #The kth largest set of labelled points in the current shape (ascending order)

664:                                 #Step 1.3

665:                                 label_pik = node_pik.key

666:                                 alpha_labels = rule.alpha.p[layer_name]

667:                                 label_alpha = alpha_labels.get_node(label_pik)

668:                                 if label_alpha

669:                                         #Step 1.4

670:                                         i = 0

671:                                         while (i < label_alpha.list.size) && ((dptr+1) < f)

672:                                                 p_i = label_alpha.list.get_node_i(i).key

673:                                                 distinct = true

674:                                                 j = 0

675:                                                 while distinct && (j < dp_alpha.size) #Check if p_i is distinct from the existing distinguishable points

676:                                                         if (p_i == dp_alpha[j])

677:                                                                 distinct = false

678:                                                         end

679:                                                         j+=1

680:                                                 end

681:                                                 if distinct

682:                                                         dptr += 1

683:                                                         dp_alpha[dptr] = p_i.clone

684:                                                         #map contains the index of the set of labelled points in the current shape which has the same label as p_i

685:                                                         map[dptr] = pik

686:                                                         if ((dptr+1) == f)

687:                                                                 segment1 = Segment.new(OrderedPoint.new(dp_alpha[0]), OrderedPoint.new(dp_alpha[1]))

688:                                                                 segment2 = Segment.new(OrderedPoint.new(dp_alpha[1]), OrderedPoint.new(dp_alpha[2]))

689:                                                                 if (segment1.line_descriptor.sine == segment2.line_descriptor.sine) #That is, the lines are collinear (they are always in the first and fourth quadrant)

690:                                                                         dptr = 1

691:                                                                         dp_alpha.delete_at(2)

692:                                                                 end

693:                                                         end

694:                                                 end

695:                                                 i+=1

696:                                         end

697:                                         if ((dptr+1) < f)

698:                                                 step_1_2_dist_points(rule, dp_alpha, map, f, dptr, k, layer_name)

699:                                         end

700:                                 else

701:                                         step_1_2_dist_points(rule, dp_alpha, map, f, dptr, k, layer_name)

702:                                 end

703:                         end

704:                 #end

705:         end
substitute(m,b,pos) click to toggle source

Auxiliar method for computing the determinant of a matrix

     # File lib/main-structures.rb, line 725
725:         def substitute(m,b,pos)

726:                 result = Array.new

727:                 result[0] = Array.new

728:                 result[1] = Array.new

729:                 result[2] = Array.new

730:                 

731:                 for i in 0..2

732:                         for j in 0..2

733:                                 if j == pos

734:                                         result[i][j] = b[i]

735:                                 else

736:                                         result[i][j] = m[i][j]

737:                                 end

738:                         end

739:                 end

740:                 

741:                 return result

742:         end
sum(a) click to toggle source
a

an Array of three positions

returns

the sum of elements in the array

     # File lib/main-structures.rb, line 757
757:         def sum(a)

758:                 result = 0

759:                 for i in 0..2

760:                         result = result + a[i]

761:                 end

762:                 return result

763:         end
undo() click to toggle source

Undoes the last taken step (that is, the current shape becomes the one that existed when the last rule had not been applied)

      # File lib/main-structures.rb, line 1441
1441:         def undo

1442:                 

1443:                 pair = @execution_history.pop

1444:                 if pair

1445:                         @current_shape.erase

1446:                         @current_shape = pair[2]

1447:                         @current_shape.refresh

1448:                 end

1449:         end

Disabled; run with --debug to generate this.

[Validate]

Generated with the Darkfish Rdoc Generator 1.1.6.