CGAL users discussion list

[Sterpa <>]

        Arrangement_2 arr = getArrangement(lines);
        Arr_walk walk = Arr_walk(arr);
        sort(lines.begin(), lines.end(), lineComparison);

        for(int i = 0;i < lines.size();i++) {
                Line_2 l_1 = lines[i];
                std::vector<CGAL::Object> list;
                Face_handle face;
                Vertex_handle vertex;
                Halfedge_handle halfedge;
                CGAL::zone(arr, l_1, std::back_inserter(list), walk);
                int level = i;

                if(assign(halfedge, list[0]))
levels[level].push_back(*halfedge);

                for(int j = 2;j < list.size();j += 2) {
                        if(assign(halfedge, list[j])) {
                                if(halfedge->curve().line() == l_1) {
                                        Vertex_handle v = halfedge->source();
                                       
Arrangement_2::Halfedge_around_vertex_circulator circ =
v->incident_halfedges(); 
                                        while(circ->curve().line() == l_1)
circ++;
                                        Line_2 l_2 = circ->curve().line();    
 

                                        Point_2 p = v->point();
                                        NT x = p.x() + 1;
                                       
if(!halfedge->target()->is_at_open_boundary()) x = CGAL::midpoint(p,
halfedge->target()->point()).x();
                                        Line_2 l_vertical = Line_2(-1, 0, x);
                                        Point_2 p_1 = intersection(l_1,
l_vertical);
                                        Point_2 p_2 = intersection(l_2,
l_vertical);
                                        if(p_1.y() < p_2.y()) level--;
                                        else level++;
                                        levels[level].push_back(*halfedge);
                                }
                        }
                }
        }



I have this piece of code and I'm performing some tests over it, but with 500
lines this algorithm takes about 1minute, is there any way to improve the
performance? The complexity of this code is O(n^2) so I'd expect a little more
than just ordering 500 lines (which is O(n logn)) but not so much.