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
An array of pairs [rule_id, transformation] applied to the axiom, in order of application
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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
Prints the applied transformations in the ruby console
# File lib/main-structures.rb, line 644 644: def print_transformations 645: @execution_history.each { |triple| 646: puts triple[1] 647: puts "--" 648: } 649: return nil 650: end
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
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
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
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
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
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.
Generated with the Darkfish Rdoc Generator 1.1.6.