CGAL users discussion list

[Ben Supnik <>]

Hi Sterpa,

I'm not entirely sure I understand what's going on here, but it looks to 
me like the slow part is running a zone insertion simulation for many 
lines, since each zone insertion is slow....you would be O(l * n) where 
L is the number of lines and n is the number of operations the zone 
insertion produces...(which is at least linear for something).

If your lines don't overlap, you could perhaps use a sweep operation to 
simply insert the lines into the arrangement.  For large numbers of 
lines and a not-insanely-huge arrangement, this would give you faster 
processing O nlogn more or less.  (The only time this is slower is if 
the lines are few and the arrangement is huge, such that the walking 
locator mostly ignores the arrangement.)

You could use a curve with data attached to then recover from the swept 
arrangement what edges are in the arrangement, what were your input 
lines and what were both.

You would have to do an O(N) pass over the TOTAL arrangement to find the 
lines where N is every edge in the arrangement, not just the inserted 
ones...so again depending on your arrangements the size of a different N 
might be worse than the advantage of lower time complexity.

cheers
Ben

Sterpa wrote:
>         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.

--
Scenery Home Page: http://scenery.x-plane.com/
Scenery blog: http://xplanescenery.blogspot.com/
Plugin SDK: http://www.xsquawkbox.net/xpsdk/
X-Plane Wiki: http://wiki.x-plane.com/
Scenery mailing list: 

Developer mailing list: