Bookmark this page: Add Outline from series of triangles to Yahoo MyWeb Add Outline from series of triangles to Google Bookmarks Add Outline from series of triangles to Windows Live Add Outline from series of triangles to Del.icio.us Digg Outline from series of triangles! Add Outline from series of triangles to Netscape
  •  
  • Subject
  • Author
  • Date
If you were  Registered and logged in, you could reply and use other advanced thread options
Posted by Brian Cryer on August 16, 2007, 4:32 am
We have an in-house application that generates a series of overlapping
triangles (thousands) and then traces round the edge of these (and displays
the results as an overlay on a map). The tracing algorithm isn't
particularly fast and was developed by someone who left the company years
ago. I was wondering if there are established algorithms for this type of
thing - because I would like to investigate alternatives to see if I can
speed up what we currently do.

TIA.



Posted by Dave Eberly on August 16, 2007, 10:55 am
> We have an in-house application that generates a series of overlapping
> triangles (thousands) and then traces round the edge of these (and
> displays the results as an overlay on a map). The tracing algorithm isn't
> particularly fast and was developed by someone who left the company years
> ago. I was wondering if there are established algorithms for this type of
> thing - because I would like to investigate alternatives to see if I can
> speed up what we currently do.

http://www.geometrictools.com/SampleFoundation/MeshEnvelope/MeshEnvelope.html

The application is currently configured to use exact arithmetic for robust
calculations, but it may be easily switched to using fixed-precision
floating-point arithmetic.

The bottleneck in such an algorithm is determining all the edge-edge
intersections of the triangles. My implementation uses a sweep
method to keep this cost to a minimum (file CreateEnvelope.cpp,
function UpdateAllEdges).

--
Dave Eberly
http://www.geometrictools.com



Posted by Brian Cryer on August 17, 2007, 5:54 am
>> We have an in-house application that generates a series of overlapping
>> triangles (thousands) and then traces round the edge of these (and
>> displays the results as an overlay on a map). The tracing algorithm isn't
>> particularly fast and was developed by someone who left the company years
>> ago. I was wondering if there are established algorithms for this type of
>> thing - because I would like to investigate alternatives to see if I can
>> speed up what we currently do.
> http://www.geometrictools.com/SampleFoundation/MeshEnvelope/MeshEnvelope.html
> The application is currently configured to use exact arithmetic for robust
> calculations, but it may be easily switched to using fixed-precision
> floating-point arithmetic.
> The bottleneck in such an algorithm is determining all the edge-edge
> intersections of the triangles. My implementation uses a sweep
> method to keep this cost to a minimum (file CreateEnvelope.cpp,
> function UpdateAllEdges).

Thank you Dave. I'm off for a few days but once I'm back I'll take a long
hard look at this.



Related Posts
  • Subject
  • Posted In
  • Date