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, 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