path: root/cuttingproblem.py

# 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 <http://www.gnu.org/licenses/>.
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

class CuttingProblem(Problem):
    """
    Generates a problem in which two areas are compared by cutting.
    """
    
    def __init__(self, container):
        self.container = container
        
        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

    def generate_problem(self):     
        # Choose two random colors.
        (color1, color2) = random.choice([(Color.RED, Color.BLUE), (Color.BLUE, Color.RED), \
            (Color.RED, Color.GREEN), (Color.GREEN, Color.RED), \
            (Color.BLUE, Color.GREEN), (Color.GREEN, Color.BLUE)]) 
        
        # 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) ]
        TRIANGLE_SHAPE = [ Vector(0, 0), Vector(200, -200), Vector(400, 0) ]
        LARGE_TRIANGLE_SHAPE = [ Vector(0, 0), Vector(250, -250), Vector(500, 0) ]

        # Choose two random letter to represent the two quantities
        letter1 = random.choice(['A', 'B', 'C', 'D', 'G', 'H', 'K', 'L', 'M', 'N', 'P', 'S', 'T'])
        letter2 = letter1
        while letter2 == letter1:
            letter2 = random.choice(['A', 'B', 'C', 'D', 'G', 'H', 'K', 'L', 'M', 'N', 'P', 'S', 'T'])
            
        # 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)])
        
        ## Randomize the initial angles of the shapes.
        #(original_angle1, original_angle2) = random.choice( [(0, math.pi/4), (math.pi/4, 0) , \
        #    (0, math.pi/4), (math.pi/4, 0), (0, math.pi/4), (math.pi/4, 0), (0, 0), (math.pi/2, 0), (0, math.pi/2) ])
        
        (original_angle1, original_angle2) = (0, 0)
        
        # The total number of problems.
        n_problems = 3
        
        # Choose a random problem.
        problem_number = random.randrange(0,n_problems)
        
        # Uncomment to test a particular problem.
        #problem_number = 0
        
        self.sub_shapes1_points = [ ]  
        self.sub_shapes2_points = [ ]
       
        # Define the various problems. 
        if 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 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 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) ] ]      
        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, Vector(0, 0), self)
        #    self.shape2 = ShapeObject(color2, letter2, object2, original_position2, original_angle2, Vector(0, 0), self)
        #else:
        #    self.shape1 = ShapeObject(color1, letter1, object2, original_position1, original_angle1, Vector(0, 0), self)
        #    self.shape2 = ShapeObject(color2, letter2, object1, original_position2, original_angle2, Vector(0, 0), self)
            
        self.shape1 = ShapeObject(color1, letter1, object1, original_position1, original_angle1, Vector(0, 0), self)
        self.shape2 = ShapeObject(color2, letter2, object2, original_position2, original_angle2, Vector(0, 0), self)
          
        self.scissors_object = ScissorsObject(Vector(750, 100), self.container)
        self.container.add_object(self.scissors_object)
        
        return
    
    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 (100, 0), \
                                        self.shape1.angle, Vector(0, 0), self)
        self.sub_shape1_1 = ShapeObject(self.shape1.color, ' ', self.sub_shapes1_points[1], self.shape1.pos + Vector (100, 0), \
                                        self.shape1.angle, Vector(0, 0), self)
        self.container.add_object(self.sub_shape1_0)
        self.container.add_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 (100, 0), \
                                        self.shape2.angle, Vector(0, 0), self)
        self.sub_shape2_1 = ShapeObject(self.shape2.color, ' ', self.sub_shapes2_points[1], self.shape2.pos + Vector (100, 0), \
                                        self.shape2.angle, Vector(0, 0), self)
        self.container.add_object(self.sub_shape2_0)
        self.container.add_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]))
        
        # How many pointsin 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
                        # shift is the gap between the two shapes.
                        shift = transformed_points1_1[j] - transformed_points1_0[i]
                    elif n_near_points == 2:
                        second_near_point_of_second_shape = j
        
        # 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
                 
        # Return False if the subshapes overlap.
        if not n_overlaps == 0:   
            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)
        
        break_outside_loop = False
        
        # Remove any point that lies on a side.
        # Only need to check the points that were near.                
        for i in range(0, len(new_shape_points)):
            if break_outside_loop:
                break
            
            sides = []
        
            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])
                
                # 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.
                    new_shape_points.remove(new_shape_points[i])
                    break_outside_loop = True
        
        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.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, Vector(0, 0), self)
        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.shape1_already_cut = False
        self.container.add_object(self.scissors_object)
    
    # 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 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
        
        
        
    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]))
        
        # 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
        
        # 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
        
        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)
        
        break_outside_loop = False
        
        # Remove any point that lies on a side.
        for i in range(0, len(new_shape_points)):
            if break_outside_loop:
                break
            
            sides = []
        
            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])
                
                # 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.
                    new_shape_points.remove(new_shape_points[i])
                    break_outside_loop = True
                    
        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, Vector(0, 0), self)
        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.shape2_already_cut = False
        self.container.add_object(self.scissors_object)
    
    def check_problem_solved(self):   
        #print ""
        #print "cuttingproblem: check_problem_solved() called"
        
        if self.shape1_already_cut:
            self.check_sub_shapes1_overlap()
            return False
        elif self.shape2_already_cut:
            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
               
        # Make sure the two ShapeObjects have the same number of points.
        if len(self.shape1.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)

        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