dcel swapping

classic Classic list List threaded Threaded
1 message Options
Reply | Threaded
Open this post in threaded view
|

dcel swapping

Ben Supnik
Hi Y'all,

I'm porting some of my old code, which used a home-rolled dcel and
planar map, to CGAL 3.3, using an arrangement_2.

Most of this has gone quite smoothly, but I found one algorithm that I'm
not sure I can port.

My old dcel had an option to swap ownership of half-edges, vertices, and
faces between two same-typed DCELs.

I used this for an optimized "region swap" - given a simple polygonal
region without holes, specified by an ordered set of curves, where the
same curves existed in BOTH maps, my region swap would simply swap the
entire interior of one for the entire interior of the other.

What made this operation fast was that the interiors were quite
literally swapped...there was no geometric calculations and no memory
allocation (for huge maps, that later property was a win).

This "fast" swap" was then used in crop and cut-and-paste style operations.

So my questions are:

1. Does it make any sense to try to preserve this dcel operation?  Would
it even be possible to modify CGAL's existing DCEL to get access at this
level?

2. Is there another way to rapidly swap the contents of a map?  From
what I can tell I'll at least be making a new copy (with new memory
allocation) if I use CGAL's built-in editing primitives.

I think the three operations I was using this for were:

- A crop that's faster than just deleting outside edges.
- The ability to cut one large map into several smaller maps more or
less in-place.
- The ability to "overwrite" a part of a map area with a new map,
"erasing" the contents in the middle of this overwrite zone.

I believe my data is large enough that these kind of optimizations will
matter in my overall run-time.

I suppose the alternative would be a non-in-place swap, e.g. code to
build the swapped map from scratch (lots of memory allocation) using the
dcel allocator to "just build it" since I know the topology from the
source maps.

cheers
Ben





--
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: [hidden email]
Developer mailing list: [hidden email]


--
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: [hidden email]
Developer mailing list: [hidden email]
--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss