|
TERM PROJECT
CMSC 420-0201
The goal of
this project is to build a small geospatial database about resources (e.g.
schools, post offices, hospitals, etc.) using k-d trees for the case
where k=2. You will develop
methods to store data of this kind, as well as develop algorithms to query
the stored database.
Part 1
(20 points, Due: Sep. 26)
Write a program called kdcreate(locfile) that takes a file containing facilities as
input. Each line of your file is a
record containing 4 items separated by commas. The first item is an integer
x (x coordinate), the second item is an integer y (y
coordinate), the third item is a string type and the fourth item is
a string name. Note that
strings are enclosed within double quotes and may include spaces in them.
The figure below shows a small file of this kind with just three records.
10, 20,
“hospital”, “Children’s hospital”
10,25,
“school”, “Churchill
High School”
5,10, “post
office”, “Rockville
Post Office”
The kdcreate(locfile) algorithm
reads a location file of this kind and stores the records in a k-d
tree. In addition to creating this tree,
you need to print out (to screen) a table. Each row in the table contains
the name field of a node, and the name field of its parent
(for the root, print NIL for the name of the parent). In the above example, you would need to
print the following:
“Children’s
hospital”, NIL
“Churchill
High School”,
“Children’s hospital”
“Rockville Post
Office”, “Children’s hospital”
Part 2
(20 points. Due: Oct 4)
Write a program called findloc(locfile, x,y). This program takes a location file and a
point (specified by its x,y coordinates)
and returns the name of the facility at that location. You may assume that two facilities cannot
exist at the same location. If no
facility is found at the desired location, return NIL. For example, the function invocation findloc(testdata,10,20) will return the
string “Children’s hospital”. Your program MUST traverse
the k-d tree data structure.
Part 3
(20 points. Due: Oct 23) Write a program called find-in-window(locfile, x1,y1,x2,y2). This program takes 4 integers x1,y1,x2,y2
as input. It returns the names of all facilities located at points (x,y) such that x1 <= x <= x2 & y1 <= y
<= y2. For example, the
invocation find-in-window(testdata,3,8,6,12) returns just
“Rockville Post Office”. Your program MUST traverse the k-d
tree data structure.
Part 4
(20 points, Due: Nov 6)
Write a program called find-nn(locfile,x1,y1,k)
where (x1,y1) is a point and k > 0 is an integer. You program must return the names of the k
facilities nearest to the given point (x,y). As usual, the distance between a point (x,y) and another point (x’,y’)
is given by SQRT((x-x’)2 + (y-y’)2). The facility names should be returned in
increasing order of distance from (x,y). If two
facilities are at the same distance from (x,y),
the order in which those two facilities’ names are displayed does not
matter.
In the above example, the invocation find-nn(10,24,2) returns “Churchill
High School” followed by
“Children’s Hospital.”
Part 5
(20 points, Due: Nov 20):
Write a program called find-nearest-facility(locfile,x,y,k,facilitytype). This takes as input, location file, an (x,y) coordinate, an
integer k, and a string denoting the type of a facility (e.g.
“school”, “hospital”). You must find the k facilities of
the desired type which are as close to (x,y)
as possible. The answer must be listed in descending order of distance from
(x,y).
For example, if we expanded the testdata
file above to include the additional record
5,6,”school”,”Whitman
high school”
and we
called find-nearest-school(24,25,2,school) you would need to return
“Churchill High
School” followed by “Whitman
High School”.
EXTRA
CREDIT (10 points, Due: Dec 4):
Write a simple graphical user interface using which you can invoke
all the above functions and using which you can display the answer. You are free to indulge your artistic
skills to make this as easy to use as you can.
|
