- INIT_QUADTREE(size, maxdepth, isect_dist)
- Sets a number of parameters for the quadtree.
- size
- gives the upper bounds for the quadtree. After
initialization the quadtree should hold points/lines that fall between [0,0] at the
southwest/lower left hand corner, and [
] in the northeast upper
right hand corner. If size is less than 2 or more than 30 print an error.
- maxdepth
- gives the maximum recursion depth in the tree before an intersection
error should be reported. A maxdepth of 0 indicates that the root would not be
allowed to split- ie. the tree could hold a single edge (A,A). A maxdepth of 1 would
allow the tree to be split once into four quadrants. The value given will
never be 0 or 1, I only state them explicitly so that we all agree on indexing ;)
- isect_dist
- specifies the minimum distance between two segments before the are
considered intersecting. This number will be an integer as with size, however it
may be negative. The actual minimum distance should be
. A value of
0 would indicate that two lines one unit apart should be treated as intersecting.
For concreteness this number should be inclusive, so that in the case of 0, (1,1) and
(1,2) would be considered as intersecting. This detail is mostly irrelevant,
since in floating point arithmetic 'inclusive' and 'exclusive' have very little meaning.
This command will always precede the first command which requires the quadtree. This
command is only valid the first time it is successfully called (out of range is
not a successful call). If an attempt is made to reinitialize the tree, print an
error.
Output summary:
<output>:=<success>|<error>
<success>:=Quadtree initialized.<nl>
<error>:=<OOR>|<INIT>
<OOR>:=Error: size out of range.<nl>
<INIT>:=Error: The Quadtree has already been initialized.<nl>
- CREATE_DOT(name, x, y, radius, color) UNCHANGED
- Creates a 'dot' object with the
appropriate name, coordinates, radius, and color.
The dot will then be added to a skiplist sorted based on the name (the
data dictionary) and to one based on the coordinates. The latter structure is
used to check for duplicate coordinates.
Coordinates will be non-negative. This should be an O(logn) operation where n is
the number of dots already in the dictionary. The dots should be stored in an
asciibetically sorted SkipList.
If a dot with the same name already exists print an error. If a dot already exists
at the specified coordinates print an error.
Output summary:
<output>:=<success>|<error>
<success>:=Created dot <dot>.<nl>
<error>:=<AE>|<DC>
<AE>:=Error: Dot <name> already exists.<nl>
<DC>:=Error: Dot <other\_dot\_name> already exists at the specified coordinates.
- DELETE_DOT(name)
- Removes the dot with the given name from the data dictionary.
If the dot does not exist print an error. If the given dot has already been added
to the Adjacency List (via CREATE_SEGMENT()) print an error and do not remove
it from the dictionary. If it has already been added to the PM1 (via MAP_SEGMENT())
print an error. Delete from the skiplist should be O(logn).
Some slowdown may occur from checks to the adjacency list and PM1 if either is
non-empty. This command will likely be used to verify that you can search for points
in those structures ;)
Output summary:
<output>:=<success>|<error>
<success>:=Deleted dot <name>.<nl>
<error>:=<DNE>|<AA>|<ZZ>
<AA>:=Error: Dot <name> has already been added to the Adjacency List.
<ZZ>:=Error: Dot <name> has already been added to the Quadtree.
- LIST_DOTS() UNCHANGED
- Lists all dots in the data dictionary
in increasing asciibetical order. This function will be used as a measure of
success for the CREATE_DOT function.
Output summary:
<output>:=<success>|<error>
<success>:=<dotlist>
<error>:= Dictionary is empty.<nl>
- COLOR_DOT(name,color) UNCHANGED
- Changes the color of the dot with the specified
name to the color given. The change should be reflected in the map, however only
the skiplist should be accessed for this operation.
Output summary:
<output>:=<success>|<error>
<success>:=Color of <name> changed from <oldcolor> to <color>.<nl>
<error>:=<DNE>
- CREATE_PATH(name1, name2)
- adds a bidirectional path between the dots
named to the Adjacency List. If one or both dots does not exist print the <DNE>
for the first argument not found. If the segment already exists print an error.
This command is not related to the PM1.
Output summary:
<output>:=<success>|<error>
<success>:=Created segment (name1,name2).<nl>
<error>:=<DNE>|<AI>
<AI>:=Error: The specified segment already exists.
- DELETE_PATH(name1, name2)
- Deletes a segment from the Adjacency list. If
either endpoint does not exist, or the segment does not exist print an error. This command
is not related to the PM1.
Output summary:
<output>:=<success>|<error>
<success>:=Deleted Segment (name1,name2).<nl>
<error>:=<DNE>|<SDNE>|<AM>
<SDNE>:=Error: The specified segment does not exist.
- SHORTEST_PATH(name1,name2)
- Prints the shortest path from
the first dot to the second dot based on the segments in the Adjacency List.
If either name is not in the dictionary print an error.
If there is no path between the two dots (possibly because one of the endpoints
was never added to the adjacency list) then print an error.
Otherwise print out the shortest path, followed by the total length of the path.
Output summary:
<output>:=<success>|<error>
<success>:= <name1> -> <moredots> <nl>Total length:<double>.<nl>
<moredots>:= <dotname> -> <moredots>| <name2>
<error>:= <DNE>|<NP>
<NP>:= Error: No path exists.
- MAP_SEGMENT(name1,name2)
- Adds a segment to the PM1.It is possible
that name1==name2,
this should not be an error. The PM1 should be able to know whether any given
point has a path to itself or not. There is one further error to detect. If the segment
intersects a segment already in the tree(except for shared endpoints),
print an error and leave the PM1 unchanged.
You may use this error even if the segment intersected is the same as the one you
are trying to insert. Further discussion on interesection detection rules will
appear on the newsgroup and later versions of the spec.
Output summary:
<output>:=<success>|<error>
<success>:=Mapped segment (name1,name2).<nl>
<error>:=<DNE>|<ID>
<ID>:=Error: Intersection detected.
- UNMAP_SEGMENT(name1,name2)
- Deletes a segment from the PM1. If the points do
not exist, or the segment does not exist, print an error. If after the operation
an endpoint would be left with no adjacent segments then it should also be completely
removed from the tree. The tree should be collapsed so that it is minimal- which
basically means that the tree should look as if the segment had never been in the
tree to begin with. (Some collapsing will need to be done). Remember that if
(A,A) is explicitly added to the tree via MAP_SEGMENT, then
(A,A) must be unmapped before A is removed.
Output summary:
<output>:=<success>|<error>
<success>:=Unmapped Segment (name1,name2).<nl>
<error>:=<DNE>|<SNF>
<SNF>:=Error: The specified segment was not found on the map.
- NEAREST_SEG_TO_POINT(x,y)
- Finds the Segment in the PM1 closest to the specified point, along
with the distance to the segment. If multiple
segments are the same distance from the point pick your favorite. If
the quadtree is empty print an error. Print the endpoints of the segment
in asciibetical order.
Output summary:
<output>:=<success>|<error>
<success>:= Nearest segment: <segment>. Distance: <double>.<nl>
<segment>:= (<name1>,<name2>)
<error>:= Tree is empty.<nl>
- COLOR_SEGMENTS(lx,ly,ux,uy,color)
- A twist on the old version. This function
will first locate all segments in PM1 which OVERLAP the specified
inclusive rectangular region(determined by (lx,ly),(lx,uy),(ux,ly),(ux,uy)).
Then it will change the color of the endpoints of those segments to the color
specified. The segment endpoints will not necessarily be within the rectangle.
Print the
number of unique segments matched.
Success can also be determined with the DRAW_MAP or LIST_DOTS commands
Output summary:
<output>:=<success>
<success>:=Update complete. Found <int> segments.
- PRINT_QUADTREE()
- Prints out the PM1 Quadtree map. Be sure to read the
section on the PM1 to understand what its structure must be.
When printing you must print in the following order: Northwest,
Northeast, Southwest, Southeast.
If you reach a leaf with a dot in it you should print the dot's name, followed
by all the dots it is adjacent to in some order. If a black leaf does not contain an
endpoint dot, print the segment that passes through it. A tree with only one isolated
point created by MAP_SEGMENT(A,A) should have output:
A:A
IE., a one element tree should look like a leaf, even if not implemented that way.
Output summary:
<output>:=<success>|<error>
<success>:= <pmtree><nl>
<pmtree>:=<black_node><nl>|<white_node><nl>|<nl><grey_node>
<grey_node>:= NW <pmtree> NE <pmtree> SW <pmtree> SE <pmtree>
<black_node>:=<name>:<namelist>|<segment><nl>
<white_node>:=
<namelist>:= <name><namelist>|<name>
<segment>:= (<name1>,<name2>)
<error>:= Tree is empty.<nl>
- DRAW_MAP()
- Draws all the points and segments of the pm1 map using the
java canvas class. The points should be displayed as in part1, the lines can be
plain solid black lines.
(If you're good with java graphics you are not required to use the canvas class,
but your output should be similar). Your program should stop running until the
graphics window is closed(this is the default behavior of the canvas class).
Output summary:
<output>:=<success>
<success>:=Drawing complete.
- DRAW_QUADTREE()
- Draws the internal partitions of the quadtree, as well
as the segments inside it. Do not draw the pretty colorful dots, as they will
just get in the way of debugging.
Output summary:
<output>:=<success>
<success>:=Drawing complete.
