# Copyright 2008 by Peter Moxhay and Wade Brainerd. # This file is part of Math. # # Math is free software: you can redistribute it and/or modify # it under the terms of the GNU General Public License as published by # the Free Software Foundation, either version 3 of the License, or # (at your option) any later version. # # Math is distributed in the hope that it will be useful, # but WITHOUT ANY WARRANTY; without even the implied warranty of # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the # GNU General Public License for more details. # # You should have received a copy of the GNU General Public License # along with Math. If not, see . from objectarea import ObjectArea, Color from vector import Vector from shapeobject import ShapeObject from symbolobject import SymbolObject from instructionsobject import InstructionsObject from scissorsobject import ScissorsObject from problem import Problem import gtk, math, cmath, random, sys gamut = 500000000. mid = gamut/2. class Vertex: def __init__(self, ip, rx, ry, inn): self.ip = ip self.rx = rx self.ry = ry self.inn = inn class Box: def __init__(self, min = Vector(0, 0), max = Vector(0, 0)): self.min = min self.max = max class Rng: def __init__(self, mn = 0, mx = 0): self.mn = mn self.mx = mx class CuttingProblem(Problem): """ Generates a problem in which two areas are compared by cutting. """ def __init__(self, container, color_scheme, (letter1, letter2) ): self.container = container self.color_scheme = color_scheme self.letter1 = letter1 self.letter2 = letter2 self.problem_number = -1 self.generate_problem() self.show_problem() self.answer = self.find_answer() self.container.moons_visible = False self.near_scissors_position = Vector(900, 200) #self.sub_shapes1_points = [ ] #self.sub_shapes2_points = [ ] self.shape1_already_cut = False self.shape2_already_cut = False self.ssss = 0 #print "" #print "CuttingProblem constructor called" #print "Testing intersection calculation..." # 1/2, 1/2 #a1 = [ Vector(2,3), Vector(2,3), Vector(2,3), Vector(2,4), Vector(3,3), Vector(2,3), Vector(2,3) ] #b1 = [ Vector(1,1), Vector(1,4), Vector(4,4), Vector(4,1), Vector(1,1) ] #print "inter(a1, b1) = ", self.inter(a1, b1) #print "inter(a1, a1) = ", self.inter(a1, a1) # 0, 9 #a2 = [ Vector(1,7), Vector(4,7), Vector(4,6), Vector(2,6), Vector(2, 3), Vector(4,3), Vector(4,2), Vector(1,2) ] #b2 = [ Vector(3,1), Vector(5,1), Vector(5,4), Vector(3,4), Vector(3,5), Vector(6,5), Vector(6,0), Vector(3,0) ] #print "inter(a2, b2) = ", self.inter(a2, b2) #print "inter(a2, a2) = ", self.inter(a2, a2) # 0, 1/2 #a3 = [ Vector(1,1), Vector(1,2), Vector(2,1), Vector(2,2) ] #b3 = [ Vector(0,0), Vector(0,4), Vector(4,4), Vector(4,0) ] #print "inter(a3, b3) = ", self.inter(a3, b3) #print "inter(a3, a3) = ", self.inter(a3, a3) # -9, 11 #a4 = [ Vector(0,0), Vector(3,0), Vector(3,2), Vector(1,2), Vector(1,1), Vector(2,1), Vector(2,3), Vector(0,3)] #b4 = [ Vector(0,0), Vector(0,4), Vector(4,4), Vector(4,0) ] #print "inter(a4, b4) = ", self.inter(a4, b4) #print "inter(a4, a4) = ", self.inter(a4, a4) # -9, 11 #a5 = [ Vector(0,0), Vector(1,0), Vector(0,1) ] #b5 = [ Vector(0,0), Vector(0,4), Vector(4,4), Vector(4,0) ] #print "inter(a5, b5) = ", self.inter(a5, b5) #print "inter(a5, a5) = ", self.inter(a5, a5) # -1, 3 #a6 = [ Vector(1,3), Vector(2,3), Vector(2,0), Vector(1,0) ] #b6 = [ Vector(0,1), Vector(3,1), Vector(3,2), Vector(0,2) ] #print "inter(a6, b6) = ", self.inter(a6, b6) #print "inter(a6, a6) = ", self.inter(a6, a6) # -1, 4 #a7 = [ Vector(0,0), Vector(0,2), Vector(2,2), Vector(2,0) ] #b7 = [ Vector(1,1), Vector(3,1), Vector(3,3), Vector(1,3) ] #print "inter(a7, b7) = ", self.inter(a7, b7) #print "inter(a7, a7) = ", self.inter(a7, a7) # 1, 16 #a8 = [ Vector(0,0), Vector(0,4), Vector(4,4), Vector(4,0) ] #b8 = [ Vector(1,1), Vector(1,2), Vector(2,2), Vector(2,1) ] #print "inter(a8, b8) = ", self.inter(a8, b8) #print "inter(a8, a8) = ", self.inter(a8, a8) def generate_problem(self): # Choose two random colors. if self.color_scheme == 'red_green': (color1, color2) = random.choice([(Color.RED, Color.GREEN), (Color.GREEN, Color.RED)]) elif self.color_scheme == 'green_blue': (color1, color2) = random.choice([(Color.GREEN, Color.BLUE), (Color.BLUE, Color.GREEN)]) else: (color1, color2) = random.choice([(Color.RED, Color.BLUE), (Color.BLUE, Color.RED)]) # Some regular polygons. SQUARE_SHAPE = [ Vector(0, 0), Vector(200, 0), Vector(200, 200), Vector(0, 200) ] LARGE_SQUARE_SHAPE = [ Vector(0, 0), Vector(250, 0), Vector(250, 250), Vector(0, 250) ] SMALL_SQUARE_SHAPE = [ Vector(0, 0), Vector(150, 0), Vector(150, 150), Vector(0, 150) ] RECTANGLE_SHAPE = [ Vector(0, 0), Vector(400, 0), Vector(400, 100), Vector(0, 100) ] LARGE_RECTANGLE_SHAPE = [ Vector(0, 0), Vector(450, 0), Vector(450, 112.5), Vector(0, 112.5) ] SMALL_RECTANGLE_SHAPE = [ Vector(0, 0), Vector(350, 0), Vector(350, 87.5), Vector(0, 87.5) ] TRIANGLE_SHAPE = [ Vector(0, 0), Vector(200, -200), Vector(400, 0) ] SMALL_TRIANGLE_SHAPE = [ Vector(0, 0), Vector(175, -175), Vector(350, 0) ] LARGE_TRIANGLE_SHAPE = [ Vector(0, 0), Vector(250, -250), Vector(500, 0) ] PARALLELOGRAM_SHAPE = [ Vector(0, 0), Vector(200, 0), Vector(400, 200), Vector(200, 200) ] TRAPEZOID_SHAPE = [ Vector(0, 0), Vector(150, 0), Vector(300, 150), Vector(-150, 150) ] RECTANGLE_2_SHAPE = [ Vector(0, 0), Vector(300, 0), Vector(300, 150), Vector(0, 150) ] LARGE_RECTANGLE_2_SHAPE = [ Vector(0, 0), Vector(350, 0), Vector(350, 175), Vector(0, 175) ] SMALL_RECTANGLE_2_SHAPE = [ Vector(0, 0), Vector(250, 0), Vector(250, 125), Vector(0, 125) ] # Standard initial positions for the shapes. upper_left_position = Vector(300, 300) lower_right_position = Vector(900, 400) upper_right_position = Vector(900, 300) lower_left_position = Vector(300, 400) # Randomize the initial positions of the shapes. (original_position1, original_position2) = random.choice([(upper_left_position, lower_right_position), \ (lower_right_position, upper_left_position), \ (upper_right_position, lower_left_position), \ (lower_left_position, upper_right_position)]) (original_angle1, original_angle2) = (0, 0) # The total number of problems. self.n_problems = 12 # Choose a random problem. while (self.problem_number in self.container.recently_used): self.problem_number = random.randrange(0, self.n_problems) # Uncomment to test a particular problem. #self.problem_number = 0 self.sub_shapes1_points = [] self.sub_shapes2_points = [] # Define the various problems. if self.problem_number == 0: object1 = SQUARE_SHAPE object2 = TRIANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(200, 0), Vector(0, 200) ], [ Vector(200, 0), Vector(200, 200), Vector(0, 200) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(200, -200), Vector(200, 0) ], [ Vector(200, 0), Vector(200, -200), Vector(400, 0) ] ] elif self.problem_number == 1: object1 = LARGE_SQUARE_SHAPE object2 = TRIANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(250, 0), Vector(0, 250) ], [ Vector(250, 0), Vector(250, 250), Vector(0, 250) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(200, -200), Vector(200, 0) ], [ Vector(200, 0), Vector(200, -200), Vector(400, 0) ] ] elif self.problem_number == 2: object1 = SQUARE_SHAPE object2 = LARGE_TRIANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(200, 0), Vector(0, 200) ], [ Vector(200, 0), Vector(200, 200), Vector(0, 200) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(250, -250), Vector(250, 0) ], [ Vector(250, 0), Vector(250, -250), Vector(500, 0) ] ] elif self.problem_number == 3: object1 = SQUARE_SHAPE object2 = RECTANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(100, 0), Vector(100, 200), Vector(0, 200) ], [ Vector(100, 0), Vector(200, 0), Vector(200, 200), Vector(100, 200) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(200, 0), Vector(200, 100), Vector(0, 100) ], [ Vector(200, 0), Vector(400, 0), Vector(400, 100), Vector(200, 100) ] ] elif self.problem_number == 4: object1 = SQUARE_SHAPE object2 = SMALL_RECTANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(100, 0), Vector(100, 200), Vector(0, 200) ], [ Vector(100, 0), Vector(200, 0), Vector(200, 200), Vector(100, 200) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(175, 0), Vector(175, 87.5), Vector(0, 87.5) ], [ Vector(175, 0), Vector(350, 0), Vector(350, 87.5), Vector(175, 87.5) ] ] elif self.problem_number == 5: object1 = SQUARE_SHAPE object2 = LARGE_RECTANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(100, 0), Vector(100, 200), Vector(0, 200) ], [ Vector(100, 0), Vector(200, 0), Vector(200, 200), Vector(100, 200) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(225, 0), Vector(225, 112.5), Vector(0, 112.5) ], [ Vector(225, 0), Vector(450, 0), Vector(450, 112.5), Vector(225, 112.5) ] ] elif self.problem_number == 6: object1 = PARALLELOGRAM_SHAPE object2 = TRIANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(200, 0), Vector(200, 200) ], [ Vector(200, 0), Vector(400, 200), Vector(200, 200) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(200, -200), Vector(200, 0) ], [ Vector(200, 0), Vector(200, -200), Vector(400, 0) ] ] elif self.problem_number == 7: object1 = PARALLELOGRAM_SHAPE object2 = LARGE_TRIANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(200, 0), Vector(200, 200) ], [ Vector(200, 0), Vector(400, 200), Vector(200, 200) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(250, -250), Vector(250, 0) ], [ Vector(250, 0), Vector(250, -250), Vector(500, 0) ] ] elif self.problem_number == 8: object1 = PARALLELOGRAM_SHAPE object2 = SMALL_TRIANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(200, 0), Vector(200, 200) ], [ Vector(200, 0), Vector(400, 200), Vector(200, 200) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(175, -175), Vector(175, 0) ], [ Vector(175, 0), Vector(175, -175), Vector(350, 0) ] ] elif self.problem_number == 9: object1 = TRAPEZOID_SHAPE object2 = RECTANGLE_2_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(0, 150), Vector(-150, 150) ], [ Vector(0, 0), Vector(150, 0), Vector(300, 150), Vector(0, 150) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(150,0), Vector(300, 150), Vector(0, 150)], [ Vector(150, 0), Vector(300, 0), Vector(300, 150) ] ] elif self.problem_number == 10: object1 = TRAPEZOID_SHAPE object2 = LARGE_RECTANGLE_2_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(0, 150), Vector(-150, 150) ], [ Vector(0, 0), Vector(150, 0), Vector(300, 150), Vector(0, 150) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(175,0), Vector(350, 175), Vector(0, 175)], [ Vector(175, 0), Vector(350, 0), Vector(350, 175) ] ] elif self.problem_number == 11: object1 = TRAPEZOID_SHAPE object2 = SMALL_RECTANGLE_2_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(150, 0), Vector(300, 150), Vector(0, 150) ], [ Vector(0, 0), Vector(0, 150), Vector(-150, 150) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(125,0), Vector(250, 125), Vector(0, 125)], [ Vector(125, 0), Vector(250, 0), Vector(250, 125) ] ] else: object1 = SQUARE_SHAPE object2 = TRIANGLE_SHAPE (original_position1, original_position2) = ( Vector (250, 250), Vector(500, 600) ) self.sub_shapes1_points = [ [ Vector(0, 0), Vector(200, 0), Vector(0, 200) ], [ Vector(200, 0), Vector(200, 200), Vector(0, 200) ] ] self.sub_shapes2_points = [ [ Vector(0, 0), Vector(200, -200), Vector(200, 0) ], [ Vector(200, 0), Vector(200, -200), Vector(400, 0) ] ] ## Switch the shapes half the time (so we get > as well as < problems). #if random.choice([0,1]) == 0: # self.shape1 = ShapeObject(color1, letter1, object1, original_position1, original_angle1) # self.shape2 = ShapeObject(color2, letter2, object2, original_position2, original_angle2) #else: # self.shape1 = ShapeObject(color1, letter1, object2, original_position1, original_angle1) # self.shape2 = ShapeObject(color2, letter2, object1, original_position2, original_angle2) self.shape1 = ShapeObject(color1, self.letter1, object1, original_position1, original_angle1) self.shape2 = ShapeObject(color2, self.letter2, object2, original_position2, original_angle2) self.scissors_object = ScissorsObject(Vector(750, 100)) self.container.add_object(self.scissors_object) def show_problem(self): self.container.configure_dragging_area(50, 24, 16, math.pi / 4) self.container.add_object(self.shape1) self.container.add_object(self.shape2) # Randomize which object is initially selected. if random.choice([0,1]) == 0: self.container.select_object(self.shape1) else: self.container.select_object(self.shape1) # Add letter symbols. self.container.letter1 = SymbolObject(Vector(500 + 400 - 50, 650), self.shape1.symbol, None, None, size=100) self.container.letter2 = SymbolObject(Vector(700 + 400 - 50, 650), self.shape2.symbol, None, None, size=100) self.container.letter1.draggable = False self.container.letter1.selectable = False self.container.letter2.draggable = False self.container.letter2.selectable = False self.container.add_object(self.container.letter1) self.container.add_object(self.container.letter2) self.container.questionmark = SymbolObject(Vector(600 + 400 - 50, 650), '?', None, None, size=80) self.container.questionmark.draggable = False self.container.questionmark.selectable = False self.container.add_object(self.container.questionmark) self.container.instructions = InstructionsObject(Vector(50, 25), 'Compare the things in area') self.container.add_object(self.container.instructions) def scaled(self, vectors, factor): for vector in vectors: new_vectors = [v.scaled(factor) for v in vectors] return new_vectors def larger(self, vectors): for vector in vectors: new_vectors = [v.scaled(1.2) for v in vectors] return new_vectors def smaller(self, vectors): for vector in vectors: new_vectors = [v.scaled(0.8) for v in vectors] return new_vectors def replace_by_sub_shapes1(self): #print "CuttingProblem: replace_by_sub_shapes1() called" #print " self.sub_shapes1_points =", self.sub_shapes1_points self.sub_shape1_0 = ShapeObject(self.shape1.color, ' ', self.sub_shapes1_points[0], self.shape1.pos - Vector (150, 0), \ self.shape1.angle) self.sub_shape1_1 = ShapeObject(self.shape1.color, ' ', self.sub_shapes1_points[1], self.shape1.pos + Vector (150, 0), \ self.shape1.angle) self.container.add_object(self.sub_shape1_0) self.container.add_object(self.sub_shape1_1) if random.choice([0,1]) == 0: self.container.select_object(self.sub_shape1_0) else: self.container.select_object(self.sub_shape1_1) self.container.remove_object(self.shape1) self.container.remove_object(self.scissors_object) def replace_by_sub_shapes2(self): #print "CuttingProblem: replace_by_sub_shapes2() called" #print " self.sub_shapes2_points =", self.sub_shapes2_points self.sub_shape2_0 = ShapeObject(self.shape2.color, ' ', self.sub_shapes2_points[0], self.shape2.pos - Vector (150, 0), \ self.shape2.angle) self.sub_shape2_1 = ShapeObject(self.shape2.color, ' ', self.sub_shapes2_points[1], self.shape2.pos + Vector (150, 0), \ self.shape2.angle) self.container.add_object(self.sub_shape2_0) self.container.add_object(self.sub_shape2_1) if random.choice([0,1]) == 0: self.container.select_object(self.sub_shape2_0) else: self.container.select_object(self.sub_shape2_1) self.container.remove_object(self.shape2) self.container.remove_object(self.scissors_object) def check_sub_shapes1_overlap(self): #print " check_sub_shapes1_overlap() called" transformed_points1_0 = [] transformed_points1_1 = [] for i in range(0, len(self.sub_shape1_0.points)): transformed_points1_0.append(self.sub_shape1_0.transform_point(self.sub_shape1_0.points[i])) for i in range(0, len(self.sub_shape1_1.points)): transformed_points1_1.append(self.sub_shape1_1.transform_point(self.sub_shape1_1.points[i])) a3 = [ Vector(100,100), Vector(100,200), Vector(200,200), Vector(200,100) ] b3 = [ Vector(0,0), Vector(0,400), Vector(400,400), Vector(400,0) ] #intersection = self.inter(a3, b3) intersection = self.inter(transformed_points1_0, transformed_points1_1) #print "intersection =", intersection # How many points in the two subshapes are within 50 pixels of each other? n_near_points = 0 first_near_point_of_second_shape = -1 second_near_point_of_second_shape = -1 for i in range(0, len(transformed_points1_0)): for j in range(0, len(transformed_points1_1)): if transformed_points1_0[i].approx_equal(transformed_points1_1[j], tolerance=50): n_near_points += 1 if n_near_points == 1: first_near_point_of_second_shape = j #print "Found the first near point..., j = ",j # shift is the gap between the two shapes. shift = transformed_points1_1[j] - transformed_points1_0[i] elif n_near_points == 2: #print "Found the second near point..., j =",j second_near_point_of_second_shape = j #print "n_near_points =", n_near_points # Return False if subshapes do not have two near points if not n_near_points == 2: return False # If n_near_points is 2, we can joint the parts, but only if they do not overlap. # Do the subshapes overlap? #n_overlaps = 0 # #for i in range(0, len(transformed_points1_0)): # for j in range(0, len(transformed_points1_1)): # line_segment1 = (transformed_points1_0[i], transformed_points1_0[(i+1) % len(transformed_points1_0)]) # line_segment2 = (transformed_points1_1[j], transformed_points1_1[(j+1) % len(transformed_points1_1)]) # if self.line_segments_intersect(line_segment1, line_segment2): # n_overlaps += 1 #print "n_overlaps =", n_overlaps # Return False if the subshapes overlap. #if not n_overlaps == 0: #return False if not intersection < 10: return False new_shape_points = [] for i in range(0, len(transformed_points1_0)): new_shape_points.append(transformed_points1_0[i]) for i in range(0, len(transformed_points1_1)): if (not i == first_near_point_of_second_shape and not i == second_near_point_of_second_shape): new_shape_points.append(transformed_points1_1[i] - shift) n_points_new_shape = len(new_shape_points) #print"" #print"" #print "Okay, to start with, there are ",n_points_new_shape, " points." n_points_removed = 0 points_to_be_removed = [] # Remove any point that lies on a side. # Only need to check the points that were near. break_outside_loop = False for i in range(0, len(new_shape_points)): if break_outside_loop: break sides = [] #print "" #print "Checking the point: ",new_shape_points[i] for m in range(0, len(new_shape_points)): for n in range(0, len(new_shape_points)): if m < n and not m == i and not n == i: sides.append( (new_shape_points[m], new_shape_points[n]) ) for j in range(0, len(sides)): dist = self.distance_point_from_line(new_shape_points[i], sides[j]) #print "dist of point from side =", dist #print "self.is_between_end_points(new_shape_points[i], sides[j]) =",self.is_between_end_points(new_shape_points[i], sides[j]) # See if the point lies on a side. if dist < 0.01 and self.is_between_end_points(new_shape_points[i], sides[j]): # Remove this point. #print "We need to remove the point with i =",i points_to_be_removed.append(i) #new_shape_points.remove(new_shape_points[i]) n_points_removed += 1 #break_outside_loop = True #print "Altogether, ",n_points_removed," points need to be removed:" final_shape_points = [] for i in range(0, len(new_shape_points)): if not i in points_to_be_removed: final_shape_points.append(new_shape_points[i]) #print "final_shape_points has ", len(final_shape_points), " points" new_shape_points = final_shape_points x_mean = 0 y_mean = 0 for i in range (0, len(new_shape_points)): x_mean += new_shape_points[i].x/len(new_shape_points) y_mean += new_shape_points[i].y/len(new_shape_points) mean = Vector(x_mean, y_mean) def sort_points_clockwise(a, b): return cmp((a - mean).theta(), (b - mean).theta()) new_shape_points = sorted(new_shape_points, cmp=sort_points_clockwise) ## If the last point coincide with the first, remove it. #print "new_shape_points[4] =",new_shape_points[4] #print "new_shape_points[0] =",new_shape_points[0] # #if new_shape_points[4].approx_equal(new_shape_points[0], tolerance=50): # print "removing the last point..." # new_shape_points.remove(new_shape_points[4]) self.shape1 = ShapeObject(self.shape1.color, self.shape1.symbol, new_shape_points, (self.sub_shape1_0.pos + self.sub_shape1_1.pos)/2.0 + shift, 0.0) self.container.add_object(self.shape1) self.container.snap_to_grid(self.shape1) self.container.remove_object(self.sub_shape1_0) self.container.remove_object(self.sub_shape1_1) self.container.select_object(self.shape1) self.shape1_already_cut = False new_scissors_pos = self.get_new_scissors_pos(self.scissors_object.pos) self.scissors_object.move(new_scissors_pos) self.container.add_object(self.scissors_object) self.near_scissors_position = new_scissors_pos + Vector(150, 100) # Check whether a point lying on a line defined by a line segment is between the segment's end points. #TODO- check for bug here. #def is_between_end_points(self, point, (point0, point1)): # # def sort_points_arbitrarily(a, b): # if a.x != b.x: # return cmp(a.x, b.x) # else: # return cmp(a.y, b.y) # # if not sorted((point, point0), cmp=sort_points_arbitrarily) == sorted((point, point1), cmp=sort_points_arbitrarily): # return True # else: # return False def get_new_scissors_pos(self, old_pos): #print "" #print "get_new_scissors_pos called" #print "old_pos =", old_pos # Try difference scissors positions to find one where there is no overlap with ShapeObjects. shape_objects = [] i_shape = 0 for o in self.container.objects: if isinstance(o, ShapeObject) and o.selectable: i_shape += 1 shape_objects.append(o) #print "Found ", i_shape ," ShapeObjects " scissors_dimensions = self.scissors_object.get_dimensions() potential_scissors_pos = [ Vector(750, 100), Vector(550, 100), Vector(350, 100), Vector(150, 100), \ Vector(350, 300), Vector(550, 300), Vector(750, 300), \ Vector(150, 500), Vector(350, 500), Vector(550, 500), Vector(750, 500) ] i_good = -1 for i in range(0, len(potential_scissors_pos)): #print "checking potential scissors position:", i scissors_bounds = potential_scissors_pos[i], potential_scissors_pos[i] + scissors_dimensions scissors_points = [ Vector(scissors_bounds[0].x, scissors_bounds[0].y), Vector(scissors_bounds[0].x, scissors_bounds[1].y), \ Vector(scissors_bounds[1].x, scissors_bounds[1].y), Vector(scissors_bounds[1].x, scissors_bounds[0].y) ] #print " scissors_bounds =", scissors_bounds area_of_overlap = 0 #print "len(shape_objects) =",len(shape_objects) for j in range(0, len(shape_objects)): shape_bounds = shape_objects[j].get_bounds() shape_points = [ Vector(shape_bounds[0].x, shape_bounds[0].y), Vector(shape_bounds[0].x, shape_bounds[1].y), \ Vector(shape_bounds[1].x, shape_bounds[1].y), Vector(shape_bounds[1].x, shape_bounds[0].y) ] #print " shape_bounds =", shape_bounds #print " contains_rectangle: ", self.inter(scissors_points, shape_points) area_of_overlap += self.inter(scissors_points, shape_points) #print "total area of overlap =",area_of_overlap if area_of_overlap == 0: i_good = i break #for pos in potential_scissors_pos: #print "i_good =", i_good if (i_good != -1): return potential_scissors_pos[i_good] else: return old_pos #def contains_rectangle(self, this_bounds, other_bounds): # b = False # other_mn, other_mx = other_bounds # # if self.contains_point(this_bounds, Vector(other_mn.x, other_mn.y) ) \ # or self.contains_point(this_bounds, Vector(other_mx.x, other_mn.y) ) \ # or self.contains_point(this_bounds, Vector(other_mn.x, other_mx.y) ) \ # or self.contains_point(this_bounds, Vector(other_mx.x, other_mx.y) ): # # b = True # # return b # #def contains_point(self, bounds, pos): # mn, mx = bounds # return pos.x >= mn.x and pos.x <= mx.x and \ # pos.y >= mn.y and pos.y <= mx.y def is_between_end_points(self, point, (point0, point1)): if point1.x > point0.x: if point.x > point0.x and point.x < point1.x: return True else: return False elif point1.x < point0.x: if point.x > point1.x and point.x < point0.x: return True else: return False else: if point1.y > point0.y: if point.y > point0.y and point.y < point1.y: return True elif point1.y < point0.y: if point.y > point1.y and point.y < point0.y: return True else: return False return False def distance_point_from_line(self, point, (point0, point1)): dist = abs( ( (point0.y - point1.y)*point.x + (point1.x - point0.x)*point.y + (point0.x*point1.y - point1.x*point0.y)) \ / math.sqrt( (point1.x - point0.x) ** 2 + (point1.y - point0.y) ** 2) ) return dist def line_segments_intersect(self, (point1, point2), (point3, point4)): zi = point1.x + 1j * point1.y zf = point2.x + 1j * point2.y wi = point3.x + 1j * point3.y wf = point4.x + 1j * point4.y b = zf - zi bb = wf - wi det = ( bb.conjugate() * b ).imag # Check whether line segments are parallel. if abs( det ) < 1.0e-10: return False else: t = ( bb.conjugate() * (wi - zi) ).imag / det u = ( b.conjugate() * (wi - zi) ).imag / det return ( ( t >= 0 and t <= 1) and ( u >= 0 and u <= 1) ) def check_sub_shapes2_overlap(self): #print " check_sub_shapes2_overlap() called" transformed_points2_0 = [] transformed_points2_1 = [] for i in range(0, len(self.sub_shape2_0.points)): transformed_points2_0.append(self.sub_shape2_0.transform_point(self.sub_shape2_0.points[i])) for i in range(0, len(self.sub_shape2_1.points)): transformed_points2_1.append(self.sub_shape2_1.transform_point(self.sub_shape2_1.points[i])) intersection = self.inter(transformed_points2_0, transformed_points2_1) # How many points in the two subshapes are within 50 pixels of each other? n_near_points = 0 first_near_point_of_second_shape = -1 second_near_point_of_second_shape = -1 for i in range(0, len(transformed_points2_0)): for j in range(0, len(transformed_points2_1)): if transformed_points2_0[i].approx_equal(transformed_points2_1[j], tolerance=50): n_near_points += 1 if n_near_points == 1: first_near_point_of_second_shape = j # shift is the gap between the two shapes. shift = transformed_points2_1[j] - transformed_points2_0[i] elif n_near_points == 2: second_near_point_of_second_shape = j #print "n_near_points =", n_near_points # Return False if subshapes do not have two near points if not n_near_points == 2: return False # If n_near_points is 2, we can joint the parts, but only if they do not overlap. # Do the subshapes overlap? n_overlaps = 0 for i in range(0, len(transformed_points2_0)): for j in range(0, len(transformed_points2_1)): line_segment1 = (transformed_points2_0[i], transformed_points2_0[(i+1) % len(transformed_points2_0)]) line_segment2 = (transformed_points2_1[j], transformed_points2_1[(j+1) % len(transformed_points2_1)]) if self.line_segments_intersect(line_segment1, line_segment2): n_overlaps += 1 # Return False if the subshapes overlap. #if not n_overlaps == 0: # return False if not intersection < 10: return False new_shape_points = [] for i in range(0, len(transformed_points2_0)): new_shape_points.append(transformed_points2_0[i]) for i in range(0, len(transformed_points2_1)): if (not i == first_near_point_of_second_shape and not i == second_near_point_of_second_shape): new_shape_points.append(transformed_points2_1[i] - shift) n_points_new_shape = len(new_shape_points) #print"" #print"" #print "Okay, to start with, there are ",n_points_new_shape, " points." n_points_removed = 0 points_to_be_removed = [] # Remove any point that lies on a side. # Only need to check the points that were near. break_outside_loop = False for i in range(0, len(new_shape_points)): if break_outside_loop: break sides = [] #print "" #print "Checking the point: ",new_shape_points[i] for m in range(0, len(new_shape_points)): for n in range(0, len(new_shape_points)): if m < n and not m == i and not n == i: sides.append( (new_shape_points[m], new_shape_points[n]) ) for j in range(0, len(sides)): dist = self.distance_point_from_line(new_shape_points[i], sides[j]) #print "dist of point from side =", dist #print "self.is_between_end_points(new_shape_points[i], sides[j]) =",self.is_between_end_points(new_shape_points[i], sides[j]) # See if the point lies on a side. if dist < 0.01 and self.is_between_end_points(new_shape_points[i], sides[j]): # Remove this point. #print "We need to remove the point with i =",i points_to_be_removed.append(i) #new_shape_points.remove(new_shape_points[i]) n_points_removed += 1 #break_outside_loop = True #print "Altogether, ",n_points_removed," points need to be removed:" final_shape_points = [] for i in range(0, len(new_shape_points)): if not i in points_to_be_removed: final_shape_points.append(new_shape_points[i]) #print "final_shape_points has ", len(final_shape_points), " points" new_shape_points = final_shape_points x_mean = 0 y_mean = 0 for i in range (0, len(new_shape_points)): x_mean += new_shape_points[i].x/len(new_shape_points) y_mean += new_shape_points[i].y/len(new_shape_points) mean = Vector(x_mean, y_mean) def sort_points_clockwise(a, b): return cmp((a - mean).theta(), (b - mean).theta()) new_shape_points = sorted(new_shape_points, cmp=sort_points_clockwise) self.shape2 = ShapeObject(self.shape2.color, self.shape2.symbol, new_shape_points, (self.sub_shape2_0.pos + self.sub_shape2_1.pos)/2.0 + shift, 0.0) self.container.add_object(self.shape2) self.container.snap_to_grid(self.shape2) self.container.remove_object(self.sub_shape2_0) self.container.remove_object(self.sub_shape2_1) self.container.select_object(self.shape2) self.shape2_already_cut = False new_scissors_pos = self.get_new_scissors_pos(self.scissors_object.pos) self.scissors_object.move(new_scissors_pos) self.container.add_object(self.scissors_object) self.near_scissors_position = new_scissors_pos + Vector(150, 100) def check_problem_solved(self): #print "" #print "cuttingproblem: check_problem_solved() called" if self.shape1_already_cut: #print "shape1_already_cut, so returning False" self.check_sub_shapes1_overlap() return False elif self.shape2_already_cut: #print "shape2_already_cut, so returning False" self.check_sub_shapes2_overlap() return False if not self.shape1_already_cut and not self.shape2_already_cut: if self.shape1.pos.approx_equal(self.near_scissors_position, tolerance=100): #print " first area is near the scissors" self.replace_by_sub_shapes1() self.shape1_already_cut = True return False elif self.shape2.pos.approx_equal(self.near_scissors_position, tolerance=100): #print " second area is near the scissors" self.replace_by_sub_shapes2() self.shape2_already_cut = True return False #print "self.shape1.points =",self.shape1.points # Make sure the two ShapeObjects have the same number of points. if len(self.shape1.points) != len(self.shape2.points): #print "shapes don't have same number of points, so returning False" #print "len(self.shape1.points) =",len(self.shape1.points) #print "len(self.shape2.points) =",len(self.shape2.points) return False # First, test whether the first two ShapeObjects coincide (areas are equal). p0 = self.shape1.points p0 = [self.shape1.transform_point(p) for p in p0] p1 = self.shape2.points p1 = [self.shape2.transform_point(p) for p in p1] # Sort the points so they can be compared consistently. def sort_points_arbitrarily(a, b): if a.x != b.x: return cmp(a.x, b.x) else: return cmp(a.y, b.y) p0 = sorted(p0, cmp=sort_points_arbitrarily) p1 = sorted(p1, cmp=sort_points_arbitrarily) #print "p0 =", p0 #print "p1 =", p1 all_equal = True for i in range(0,len(p0)): if not p0[i].approx_equal(p1[i]): all_equal = False if all_equal: self.container.remove_object(self.scissors_object) return True # Test if one object is completely inside the other (areas are not equal) area0 = self.shape1.area area1 = self.shape2.area if area0 > area1: object_larger = self.shape1 p_smaller = p1 else: object_larger = self.shape2 p_smaller = p0 for i in range(0,len(self.shape1.points)): if not object_larger.contains_point(p_smaller[i]): return False self.container.remove_object(self.scissors_object) return True def find_answer(self): #print "find_answer() called" #print "self.shape1.area =", self.shape1.area #print "self.shape2.area =", self.shape2.area tolerance = 100 if abs(self.shape1.area - self.shape2.area) < tolerance: self.answer = 'equal' #print " equal problem" elif self.shape1.area > self.shape2.area: self.answer = 'greater' #print " greater problem" elif self.shape1.area < self.shape2.area: #print " less problem" self.answer = 'less' else: self.answer = 'equal' #print " equal problem" return self.answer def range(self, points, c, bbox): while (c > 0): c -= 1 bbox.min.x = min(bbox.min.x, points[c].x) bbox.min.y = min(bbox.min.y, points[c].y) bbox.max.x = max(bbox.max.x, points[c].x) bbox.max.y = max(bbox.max.y, points[c].y) def ovl(self, p, q): return p.mn < q.mx and q.mn < p.mx def area(self, a, p, q): #print "area returning:", p.x * q.y - p.y * q.x + a.x * (p.y - q.y) + a.y * (q.x - p.x) return p.x * q.y - p.y * q.x + a.x * (p.y - q.y) + a.y * (q.x - p.x) def cross(self, a, b, c, d, a1, a2, a3, a4): r1 = a1 / float(a1 + a2) r2 = a3 / float(a3 + a4) #print "cross: r1 =", r1 #print "cross: r2 =", r2 self.cntrib((int)(a.ip.x + r1 * (b.ip.x - a.ip.x)), (int)(a.ip.y + r1 * (b.ip.y - a.ip.y)), b.ip.x, b.ip.y, 1) self.cntrib(d.ip.x, d.ip.y, (int)(c.ip.x + r2 * (d.ip.x - c.ip.x)), (int)(c.ip.y + r2 * (d.ip.y - c.ip.y)), 1) a.inn += 1 c.inn -= 1 def fit(self, x, cx, ix, fudge, B): #print "fit called" c = cx; while (c > 0): c -= 1 #print "c =", c ix[c] = Vertex(Vector(0,0), Rng(0,0), Rng(0,0), 0) ix[c].ip = Vector(0, 0) ix[c].ip.x = ((int)((x[c].x - B.min.x) * self.sclx - mid) & ~7) | fudge | (c & 1) ix[c].ip.y = ((int)((x[c].y - B.min.y) * self.scly - mid) & ~7) | fudge #print " ixc[" , c , "].ip = (" , ix[c].ip.x , "," , ix[c].ip.y , ")" ix[0].ip.y += cx & 1 #print "After additional term: " #print " ixc[" , 0 , "].ip = (" , ix[0].ip.x , "," , ix[0].ip.y , ")" ix[cx] = ix[0] c = cx while (c > 0): c -= 1 ix[c].rx = Rng(ix[c].ip.x, ix[c + 1].ip.x) if ix[c].ip.x < ix[c + 1].ip.x else Rng(ix[c + 1].ip.x, ix[c].ip.x) ix[c].ry = Rng(ix[c].ip.y, ix[c + 1].ip.y) if ix[c].ip.y < ix[c + 1].ip.y else Rng(ix[c + 1].ip.y, ix[c].ip.y) ix[c].inn = 0 # Calculate the area of intersection of two polygons. # Here a and b are the polygons (arrays of points). def inter(self, a, b): #print "inter called" self.ssss = 0 na = len(a) nb = len(b) #print "na =", na #print "nb =", nb ipa = [] ipb = [] bbox = Box(Vector(sys.maxint, sys.maxint), Vector(-sys.maxint, -sys.maxint)) if (na < 3 or nb < 3): return 0 #print "bbox = (", bbox.min.x, ",", bbox.min.y, ",", bbox.max.x, ",", bbox.max.y, ")" self.range(a, na, bbox) #print "bbox = (", bbox.min.x, ",", bbox.min.y, ",", bbox.max.x, ",", bbox.max.y, ")" self.range(b, nb, bbox) #print "bbox = (", bbox.min.x, ",", bbox.min.y, ",", bbox.max.x, ",", bbox.max.y, ")" rngx = bbox.max.x - bbox.min.x #print "rngx =", rngx self.sclx = gamut / rngx #print "sclx =", self.sclx rngy = bbox.max.y - bbox.min.y #print "rngy =", rngy self.scly = gamut / rngy #print "scly =", self.scly ascale = self.sclx * self.scly #print "ascale =", ascale for i in range (0, na + 1): ipa.append(Vertex(0,0,0,0)) for i in range (0, nb + 1): ipb.append(Vertex(0,0,0,0)) self.fit(a, na, ipa, 0, bbox) self.fit(b, nb, ipb, 2, bbox) #print "After fit:" #print "ipa =" #for i in range (0, na + 1): # print " (", ipa[i].ip.x, ",",ipa[i].ip.y, ") (", ipa[i].rx.mn, ",", ipa[i].rx.mx, ") (", \ # ipa[i].ry.mn,",", ipa[i].ry.mx, ")", ipa[i].inn # #print "ipb =" #for i in range (0, nb + 1): # print " (", ipb[i].ip.x, ",",ipb[i].ip.y, ") (", ipb[i].rx.mn, ",", ipb[i].rx.mx, ") (", \ # ipb[i].ry.mn,",", ipb[i].ry.mx, ")", ipb[i].inn for j in range (0, na): #print " j =", j for k in range (0, nb): #print " k =", k if (self.ovl(ipa[j].rx, ipb[k].rx) and self.ovl(ipa[j].ry, ipb[k].ry)): a1 = -self.area(ipa[j].ip, ipb[k].ip, ipb[k + 1].ip) a2 = self.area(ipa[j + 1].ip, ipb[k].ip, ipb[k + 1].ip) # o is a boolean. o = a1 < 0 #print "o =",o #print "a2 < 0 =", (a2 < 0) #print "(o == (a2 < 0)) =", (o == (a2 < 0)) if (o == (a2 < 0)): a3 = self.area(ipb[k].ip, ipa[j].ip, ipa[j + 1].ip) a4 = -self.area(ipb[k + 1].ip, ipa[j].ip, ipa[j + 1].ip) if ((a3 < 0) == (a4 < 0)): if (o): self.cross(ipa[j], ipa[j + 1], ipb[k], ipb[k + 1], a1, a2, a3, a4) else: self.cross(ipb[k], ipb[k + 1], ipa[j], ipa[j + 1], a3, a4, a1, a2) #print "ssss = ",self.ssss self.inness(ipa, na, ipb, nb) #print "ssss = ",self.ssss self.inness(ipb, nb, ipa, na) #print "ssss = ",self.ssss return self.ssss / ascale def inness(self, P, cP, Q, cQ): s = 0 c = cQ p = P[0].ip while (c > 0): c -= 1 #print "......inness: c =",c if (Q[c].rx.mn < p.x and p.x < Q[c].rx.mx): sgn = 0 < self.area(p, Q[c].ip, Q[c + 1].ip) #print "............area(p, Q[c].ip, Q[c + 1].ip) =", self.area(p, Q[c].ip, Q[c + 1].ip) #print "............sgn =",sgn #print "............sgn != bool(Q[c].ip.x < Q[c + 1].ip.x) =",sgn != bool(Q[c].ip.x < Q[c + 1].ip.x) s += 0 if (sgn != bool(Q[c].ip.x < Q[c + 1].ip.x)) else (-1 if sgn else 1) #print "............s =",s for j in range (0, cP): #print "......inness: j =",j if (s != 0): self.cntrib(P[j].ip.x, P[j].ip.y, P[j + 1].ip.x, P[j + 1].ip.y, s) #print "............P[j].inn =",P[j].inn s += P[j].inn #print "............s =",s def cntrib(self, f_x, f_y, t_x, t_y, w): #print "cntrib returning:", w * (t_x - f_x) * (t_y + f_y) / 2 self.ssss += w * (t_x - f_x) * (t_y + f_y) / 2