Skip to topic
|
Skip to bottom
Jump:
TModeling
TModeling Web
TModeling Web Home
Changes
Notify
Index
Search
Webs
BioGeometry
Main
TModeling
TWiki
Edit
Attach
Printable
TModeling.SimpSimp
r1.1 - 28 Feb 2005 - 19:32 - Main.guest
topic end
Start of topic |
Skip to actions
_Note: This is not part of the Geo* project, but topical._ ---+ People At a Dagstuhl seminar in October 2003, Lars Kulik asked whether efficient line simplification could be achieved by a certain "shortcutting" operation (described below). [[Main.JackSnoeyink][Jack Snoeyink]], [[http://mail.med.upenn.edu/~ryangc/][Ryan Coleman]], and [[http://www.cs.tufts.edu/~dls/][Diane Souvaine]] at Tufts University have now developed such an algorithm. [[Main.CraigFalls][Craig Falls]] is implementing the algorithm and reporting on some practical considerations, comparing it to competing algorithms, etc. We will submit a paper Feb 21, 2005. ---+ The Problem Start with an arrangement of non-intersecting line segments (typically in the form of polygonal boundaries). Then, iteratively remove points, connecting their neighbors directly. (Shortcutting is only defined for degree-2 points -- degree-1 points can always be removed along with their lone edge, and higher-degree points are left alone.) However, doing so may introduce intersections with other line segments in the arrangement. So, the algorithm either reports that the shortcutting is not possible for that point, or it performs the shortcutting operation. ---+ Our Solution The runtime is O(n log n) pre-processing time on the initial arrangement and O(log^2 n) time per shortcut. First approach: The algorithm works by first computing an x-monotone subdivision of the arrangement, and maintaining a dynamic convex hull of each x-monotone chain. Then, when a point is being deleted, only the x-monotone chain above and below the point needs to be inspected to determine if the triangle sweeped out by the shortcut operation is empty (and therefore doesn't change the homotopy). The problem with this approach is that we are unable to maintain an x-monotone subdivision with bounded vertex degree. Such subdivisions exist, but they are expensive to maintain. (I can provide examples upon request.) New approach: Maintain a geodesic triangulation of the arrangement. A geodesic triangle on three vertices u, v, w is just the shortest path from u to v, v to w, and w to u. A balanced geodesic triangulation guarantees that a ray in the subidivision will intersect at most log(n) geodesic triangles. A balanced geodesic triangulation can be found for any connected planar subdivision but GIS data is often a disconnected subdivision, so we are looking for ways to maintain a connected subdivision by adding fake edges while maintaining bounded vertex degree. ---+ For more information More details are available in the attached rough draft of our paper. Please read it and offer comments. -- Main.CraigFalls - 02 Feb 2005 * [[%ATTACHURL%/main.ps][main.ps]]: Postscript version of a preliminary draft paper
to top
End of topic
Skip to action links
|
Back to top
Edit
|
Attach image or document
|
Printable version
|
Raw text
|
More topic actions
Revisions: | r1.1
|
Total page history
|
Backlinks
You are here:
TModeling
>
SimpSimp
to top
Copyright © 1999-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki?
Send feedback