Lab 2: Intersections and Computational Geometry

Posted on October 11, 2016

Announcements

No lab next week (Oct. 18). This lab is still due this Friday 11:59:59pm (October 14).

Summary

You will write a program to perform simple computational geometry.

Submitting

The same as last week, email your submission to brianhempel@uchicago.edu by 11:59:59pm Friday.

You may submit multiple times if the deadline is close. Only the last submission will be graded. Also note you can request up to two 24-hour extensions per quarter.

Modeling Computational Geometry in Haskell

The basic idea here is to use Haskell’s algebraic data types as a basis for defining geometric objects. Analytic geometry can then be used to answer geometric questions. In this lab we will model shapes in the two-dimensional plane and answer questions about intersection. This is useful for thinking about the code underlying computer games.

A starting file for this lab is available with some initial definitions.

Basic Definitions

We begin the lab with some simple definitions:

-- A point is a point in the xy plane, represented by x and y coordinates
-- E.g. (Point 0.0 0.0) is the origin, (Point (-1) (1)) is in the top left
-- quadrant.
data Point = Point Double Double
    deriving (Show, Eq)

-- A line segment is a straight line of finite length, defined by its
-- two end points.   E.g. (LineSegment (Point 0 0) (Point 1 1)) is a
-- line segment from the origin to the coordinate (1, 1)
data LineSegment = LineSegment Point Point
    deriving (Show, Eq)


-- A Path is a 2D path in the xy-plane.  The idea is that Path can be
-- extended to support straight lines, curves, and arbitrary paths,
-- but currently there is only one data constructor for Path: Line.
data Path =
-- Line represents an infinite straight line defined by its slope a
-- and its y intercept b, ie. by the equation y = ax + b
    Line Double Double
    deriving (Show, Eq)

So we now have some basic data structures. LineSegments are constructed from points and we have an abstract notion of a path formed from a line. Throughout this lab we are going to expand the definition of Path to include more definitions and we will write functions that use path using Haskell’s pattern-matching facilities to get the definition right (NOTE: when writing a function that maps a Path to something else use pattern matching idioms).

  1. Write a function intersects that checks whether a LineSegment intersects with a Line. Try solving for the problem in the case where the line segment is vertical and then see if you can generalize from that.

This first problem is meant as a warm-up to start checking intersections. We will add to the definition of intersects as we expand the definition of Path.

Representing vertical lines

Infinity is a valid value for IEEE floating point numbers but the Haskell language standard does not require it. To get around this you may write:

infinity = read "Infinity" :: Double

Another possibility is to add something like a VerticalLine constructor to the Path data type.

Testing and Sample Runs

You will write and submit tests for this lab.

At the top of Lab2.hs we can put a module declaration to export the data types and functions we write…

module Lab2(
	Point(Point),
	LineSegment(LineSegment),
	Path(Line)
	-- other functions and things go here
) where

and then construct a testing file Tests.hs with the top line having

import Lab2

Inside Tests.hs we will put the sample runs. We can think of a sample run as a function we have implemented, e.g. f, that along with a particular set of inputs, e.g. x and y, gives a particular expected result z. Thus, we could write a test as:

test0 :: Bool
test0 = f x y == z

which will evaluate to true if f behaves as expected. For each exercise you may come up with a set of sample runs that demonstrate you have correctly implemented the functions and then you can write tests in the form above.

To give a summary we can put all the tests into a single list:

tests :: [Bool]
tests = [test0,
         test1
	     -- more tests
         ]

And then we can get some summaries of the current testing state:

import Data.List

testAll = and tests
testPasses = sum $ map fromEnum tests
testFirstFailIndex = elemIndex False tests

testAll checks whether all the tests are passing. testPasses counts how many tests are passing. testFirstFailIndex gives the index in tests of the first failing test.

You can load this file into ghci and type testFirstFailIndex to see if all your tests pass.

Write some test cases for intersects to convince yourself your code is correct. If your code has a special case for vertical lines, be sure to write a separate test case for it.

In software development it is a good practice to write your tests just before you implement the appropriate code rather than waiting until after. Psychologically, writing the tests first helps you think about what, exactly, you need to do. It also helps ensure that each line of code you write is tested.

Your submitted Tests.hs file should have appropriate test case(s) for each of the functions this lab askes you to define; namely intersects, boundShape, intersectsBB, and mightIntersectShape (described below).

A question to ponder: How many tests should you write for a function? When is it okay to have only one test for a function? When do you instead want a lot of tests?

Defining data types for shapes

A crucial skill is being able to define abstract type definitions to capture real-world objects. We are wanting to do computational geometry so you will need to define models of shapes.

  1. Define a type Shape that can be a Triangle, Quadrilateral, or a Circle. Use algebraic datatypes. Make sure that you can use show.

Bounding Boxes for Shapes

For any shape there is a unique minimum bounding rectangle which is defined as the smallest axis-aligned rectangle that encloses the shape. Axis-aligned here means that each of the four edges of the rectangle runs parallel to either the x-axis or the y-axis. Minimum bounding rectangles are very useful for programming computer games because testing for intersections in general is a very hard problem.

  1. Write a datatype for BoundingBox. You may choose how you want to do it, but I suggest defining it by two points: the bottom left corner and the upper-right corner.
  2. Write a function boundShape which maps a Shape to a BoundingBox that maps a shape to its minimum bounding rectangle. Functions such as min, minimum, max, maximum may be useful here.

Don’t forget to write tests to demonstrate that your code is working.

Checking if lines intersect with bounding boxes

  1. Implement a function intersectsBB that, given a BoundingBox and a Path, checks to see if the path intersects the bounding box. At present a Path only includes a Line.
  2. Write a function mightIntersectShape which use the functions already present to check if a path intersects the bounding box of a shape. This should be a short function without much innovation to it.
  3. Extend Path to include a type constructor Parabola and add onto intersects and intersectsBB.

What you will submit

Submit two files:

  1. Lab2.hs with the all the definitions as described in the numbered points above.
  2. Tests.hs with all your test cases for intersects, boundShape, intersectsBB, and mightIntersectShape. You are also encouraged (but not required) to include tests for any extra helper functions you define.

Extra Credit

Implement projective geometry data types HomogeneousPoint and HomogeneousLine and use those to implement the assignment using homogeneous coordinates.