CGAL users discussion list

Hello,

Can somebody tell me what is the line arrangement complexity ? It looks
that current CGAL takes anormous amout of time ( > 5 Hours ) for finding
the intersection points of 10000 segments on 1GB Ram machine.


#include <CGAL/Cartesian.h>
#include <CGAL/Polygon_2.h>
#include <CGAL/ch_graham_andrew.h>
#include <CGAL/ch_akl_toussaint.h>
#include <CGAL/ch_bykat.h>
#include <CGAL/ch_eddy.h>
#include <CGAL/ch_jarvis.h>
#include <CGAL/Sweep_line_2_algorithms.h>

#include <iostream>
#include <fstream>

#include <vector>
#include <list>

using namespace std;

typedef CGAL::Cartesian<double> K;
typedef CGAL::Point_2<K>   Point2D;
typedef CGAL::Segment_2<K> Line2D;

int vtk_points( const string &fname, vector<Point2D> &p)
{
  ofstream ofile( fname.c_str(), ios::out);

  int numNodes = p.size();

  ofile << "# vtk DataFile Version 1.0" << endl;
  ofile << "Unstructured FEM Solver " << endl;
  ofile << "ASCII " << endl;
  ofile << "DATASET UNSTRUCTURED_GRID " << endl;
  ofile << "POINTS " << numNodes << " float " << endl;

   for( int i = 0; i < numNodes; i++){
      double  px = p[i].x();
      double  py = p[i].y();
      double  pz = 0.0;
      ofile << px << " " << py << " " << pz << endl;
  }

  int numCells = numNodes;

  ofile << "CELLS "  << numCells << "  " <<  2*numCells <<  endl;

  for( int i = 0; i < numCells; i++)
    ofile << " 1 "  << i << endl;

  ofile << endl;

  ofile << "CELL_TYPES " << numCells << endl;
  for( int i = 0; i < numCells; i++) 
    ofile << " 1 " << endl;

  ofile.close();
}

int vtk_segments(const string &fname, vector<Point2D> &p)
{
  ofstream ofile( fname.c_str(), ios::out);

  int numNodes = p.size();

  ofile << "# vtk DataFile Version 1.0" << endl;
  ofile << "Unstructured FEM Solver " << endl;
  ofile << "ASCII " << endl;
  ofile << "DATASET UNSTRUCTURED_GRID " << endl;
  ofile << "POINTS " << numNodes << " float " << endl;

   for( int i = 0; i < numNodes; i++){
      double  px = p[i].x();
      double  py = p[i].y();
      double  pz = 0.0;
      ofile << px << " " << py << " " << pz << endl;
  }

  int numCells = p.size()-1;

  ofile << "CELLS "  << numCells << "  " <<  3*numCells <<  endl;

  for( int i = 0; i < numCells; i++)
    ofile << " 2 "  << i <<  " " << i+1 << endl;

  ofile << endl;

  ofile << "CELL_TYPES " << numCells << endl;
  for( int i = 0; i < numCells; i++) 
    ofile << " 3 " << endl;

  ofile.close();
}


void intersection_2d()
{
  vector<Point2D>  vpoints, result;
  vector<Line2D>   lines;

  int numPoints = 10000;
  for( int i = 0; i < numPoints; i++) {
       double x = drand48();
       double y = drand48();
       vpoints.push_back( Point2D(x,y) );
  }
  vtk_points( "p.vtk", vpoints);
  vtk_segments("s.vtk", vpoints);

  for( int i = 0; i < numPoints-1; i++) 
       lines.push_back( Line2D( vpoints[i], vpoints[i+1] ));

  cout << " Number of Segments : " << numPoints-1 << endl;
  cout << " Intersection Start ... " << endl;
  CGAL::get_intersection_points( lines.begin(), lines.end(), 
back_inserter(result));
  vtk_points( "r.vtk", result);
}

int main()
{
   intersection_2d();
}