Take the 2-minute tour ×
Geographic Information Systems Stack Exchange is a question and answer site for cartographers, geographers and GIS professionals. It's 100% free, no registration required.

I have a set of 2D triangles in a Geometry array which together forms a connected strip when placed them according to edge adjacency. However, in the array they are not in topological order based on the edge adjacency. How can i topologically sort them and put in the array?

share|improve this question
    
And what's the software you use? And it's version? –  Jakub Kania Apr 21 '13 at 12:32
    
I use JTS library. –  Sanjeewa Apr 21 '13 at 13:20
add comment

1 Answer

To do this you need to perform a topological sort, where the triangles are the nodes of the graph and the edge-adjacency provides the graph edges. Since you know the graph is a single line, the sort actually devolves into finding a node with only one other adjacent triangle, and then traversing the graph visiting all the other triangles in turn.

share|improve this answer
    
This is equivalent to a standard algorithm for topological sorting. –  whuber Jun 28 '13 at 15:21
    
@whuber would this work for triangles covering a sphere? (Like for an Icosahedron?) –  Kirk Kuykendall Jun 28 '13 at 17:33
    
@Kirk No triangulation of an icosahedron would constitute a "strip." Although it takes some parsing to figure it out, this question concerns only a triangulation in which the (abstract) edge-adjacency graph is linear. Whether or not they are on a sphere, a plane, or any other place is immaterial. (So basically this question asks "how do I sort those triangles" and the answer here is "use a brute-force search to find a triangle at one end, then proceed from there." Because of the assumptions, there are no choices to be made and no more searching to do.) –  whuber Jun 28 '13 at 17:37
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.