Topological sweep and Guided Topological sweep in degenerate cases - 
                 Description of the code
---------------------------------------------------------------
Author: Eynat Rafalin, Tufts University
Last updated: August 20, 2002

This readme file describes the topological sweep code that is located for download in http://www.eecs.tufts.edu/r/geometry/sweep.
Additional information about the algorithm and its time complexity is located in this site as well.
The code is written in C++ and does not use any geometrical libraries for computations. Geomview is used to output the data in a geometrical way to the screen.

The structure of the README file is as follows:
1. How to run the code - description of input file and output methods.
2. Code structure
3. How to make changes - includes information about the main variables and functions that are used for interface.
4. Known problems

1. How to run the code?
-----------------------
1.1 Compile
----------
To compile simply type "make"

1.2 Input
---------
The input file is "dat.txt".
The first line of the file includes a number representing the number of input data points and the dimension of the points (currently only 2 is acceptable)
The rest of the lines contain the data set itself. Each line is a pair a b that represents a line y=ax+b. The numbers are divided by spaces.
Example of a legal file:
"3 2
 1 1
 4 6
 -0.5 0.5"
This file contains 3 data points.
The data points can also be viewed as points (x,y) in the primal, that are transformed into lines in the dual. The sweep in this case is executed on the set of lines in the dual.
There is no restriction on the number or values of the data set. Lines can share the same slope or can even be identical (share both a and b)

1.3 Output
----------
The code has two different output methods:
a) Geometrical represantation of the sweep (default).
b) Alph-numeric data showing the information stored in the data structures in every step of the sweep
1.3.1 Geometrical output
------------------------
The Geomview library is used for geometrical output. If you do not have this library installed you can only use the second form output (see 1.3.2).
Run geomview from the current directory (by typing 'geomview'). The name "Topological sweep" should appear in the left hand window. Press "Topological sweep" and the right hand window will present the steps of the sweep. 
- The red lines are the lines of the data set.
- The green lines are the edges that form the cut (this means that the sweep line passes through them)
- The blue intersection points are the ready points. The next step of the algorithm will be performed on one of these intersection points.
Note 1: As a default the topological sweep is NOT guided. To perform a guided sweep with a vale of x, change the value of the variable k in main.cc
Note 2: Make sure that the file .geomview (part of the tar.zip download file) is present in the directory and has appropriate permissions!
1.3.2 Alpha-numeric output
-------------------------
Run "sweep". The content of each data structure in the current step of the sweep will be output to the screen. To move to the next step press any character and than Enter.
To use this form type "sweep 0" from the shell window. The parameter 0 instructs the computer to perform A/N output. 
As a default the sweep is not guided. To add guided topological sweep type the value of teh parameter for the guided topological sweep as teh second input parameter. E.g: to perform guided sweep with a value of 4 type "sweep 0 4". 
To set the value of k to be half of the size of the input (this is used for example in the LMS regression algorithm) type -2. Another option is to change the value assigned to k directly in main.cc.
1.3.3 No output
---------------
Type "sweep 5". This form can be used if the topological sweep is incorporated in another program.
Again, the default is with no guided sweep. To set the value of teh guided sweep add a second input parameter with the requested value, or -2 for n/2, or change the value directly in main.cc and recompile.

2. Code Structure
-----------------
Files: main.cc
       data.cc data.h
       point.h
       stack.h
The main file of the code is "main.cc". It manages the execution of the code.
File "data.cc" contains the functions that perform the sweep. The main function is sweep2d().
The rest of the files contain utility code and data structures.
2.1 main.cc
------------
  data * alldata;
  int k; //guided topological sweep.K =  -1 = not guided
  int print_type; 
  char file_name[] = "dat.txt";
 
  //Reading print type from argv\argc
  if (argc == 1)
    print_type = GEOMVIEW;
  else
    print_type = atoi(argv[1]);
  
  alldata = new data;

  //reading data from file
  if ((alldata->read(file_name)) == FALSE){
    cout<<"didn't manage to read input file "<<file_name<<endl;
    return FALSE;
  }

  //sorting data points
  alldata->sort();

  //scanning for duplicates and looking for rightmost and left most coordinates (for display)
  alldata->scan();

  if (PRINT_TYPE == AN){
    alldata->display_input(); //displays original data set, ordered
    alldata->display_data_set(); //display data set after sorting and deletion of multiple identical lines
  }

  //Choosing parameter for guided sweep. Default - not guided
  if (argc == 2)
    k = NOT_GUIDED;
  //for sweep used for LMS regression - k is (n+1)/2 -1. Set arg[2] to -2
  else if (atoi(argv[2]) == LMS)
    k = (alldata->get_original_size() + 1)/2 - 1;    
  //For guided sweep - define k bigger than 0. 
  else
    k = atoi(argv[2]); 

  alldata->sweep2d(k, print_type); <---perfoms the sweep

  delete alldata;

  return 1;
}


2.2 data.cc
-----------
The main function is the following
  int current;
  int gap;//number of lines passing through the ready point (not including the first line)
  intersection current_intersection;
  int correct;

  //initialize data structures
  create();
  init_htu();
  init_htl();
  init_input_m(); 
  init_position_in_input(); 
  init_m();
  init_n();
  init_i(k);

  print_out(TRUE, print_type);
  first_report();

  //step
  while((I->empty()) == FALSE){
     current_intersection = I->pop();
     current = current_intersection.f_line;
     gap = current_intersection.intersect_size;
     report_before_update(current, gap);

     update_input_m(current, gap);
     update_m(current, gap);
     update_left_n(current, gap);
     update_htu(current, gap);
     update_htl(current, gap);
     update_right_n(current, gap);
     update_in_stack(current, gap);
     update_i(current, gap, k);
     report_after_update(current, gap);
     print_out(FALSE, print_type);  
  }

   //verifies that the sweep was performed correctly and terminated at the tightmost cut
  if ((correct = check_correctness()) == FALSE)
    cout<<"Sweep terminated unsuccessfully"<<endl;
  else if((print_type==AN)||(print_type==NOPRINT))
    cout<<"Sweep finished successfully"<<endl;


  delete I;
  delete []HTL;
  delete []HTU;
  delete []input_M;
  delete []position_in_input;
  delete []M;
  delete []N;
  delete []MATCH;
  delete []in_stack;

  if (correct == TRUE)
    return TRUE;
  else
    return FALSE;



3. How to make changes?
-----------------------
3.1 Interface functions
-----------------------
To interface with the sweep data use the following functions in "sweep.cc":
- void first_report() - performed once, in the initial step of teh sweep.
- void report_before_update(int current, int gap) - perfomed after the next ready vertex is popped but before any update of the algorithm.
- void report_after_update(int current, int gap) - perfomed after each update step of the algorithm.
Notes:
The data structures input_M[] and position_in_input[] are used to follow the order of the cut lines in case of identical lines (M[], N[], etc work with unique lines). Use them to modify the report functions


4. Known problems
-----------------
The main problem is due to floating point arithmetic and errors that arise because of it:
The tests that check allignemnt of 3 points sometimes return incorrect answer (FALSE instead of equal etc').
If such an error occurs the sweep will not be able to advance all the way to teh right (because of the that causes a change in teh topological structure of teh arrangement). It will be detected by the algorithm in it's last phase, by verifying of the sweep reached the right most cut or not and an error message will be displayed to the user.