Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I have set of line segments, containing only 2 points. I know their point numbers. some point numbers are appeared in many lines according to their connections. So, when joining some end points, I can get a closed polygon. So, I took a line segment and get an end point, and then find connection from that point. Then from those connections, I took subsequent connections respectively. Then, I try to find the other end point of my line segment. If that point is not inside any of the connections, I have to go further and look for their connections. And so on. This appear like a tree when i draft all the connection in a piece of paper. I was trying to implement this but, i am not sure how should i handle this, effectiely. so, i am looking for some way.(i want to implement this in c++). also i heard depath first seearch method, i am not sure whether this methood can be solved my problem or not.

Also, I dont have any idea to implement even that to handle this type of case? Thank you in advance.

So, for example I have added below line list together with their point indices to get idea about m case. (Where First value = line number, second 2 values are the point indices)

0 - 9 11  
1 - 9 18  
2 - 9 16  
3 - 11 26  
4 - 11 45  
5 - 16 25
6 - 16 49  
7 - 18 26 
8 - 18 25  
9 - 18 21  
10 - 25 49  
11 - 26 45

So, assume I have started from the line 1. That is I have started to find connected loops from point 9, 18. Then, could you please explain (step by step) how I can get the "closed loops" from that line.

share|improve this question
    
Do you want all loops ('cycles') that contain line 1? Or do you just want to find one such cycle? –  TonyK Sep 26 '11 at 13:17
    
@TonyK: thanks. i need to find one cycle. it is better if i can find all cycles, then i can find the one i need. if it easy to find all cycles, then i like that way? –  niro Sep 26 '11 at 17:21
    
Well that's as clear as mud. What's 'the one i need'? –  TonyK Sep 26 '11 at 17:59
    
@TonyK: oh sorry. when there exist many loops, i want to get the loop having minimum number of points. this is the only criteria what i need. (if i can get all loops then i can make sure, i have minimum one. thats why i said if it is good to get all loops. if i can find a way to get only the minimum one FOR SURE, then it is fine for me. thanks again. –  niro Sep 26 '11 at 20:25

2 Answers 2

up vote 1 down vote accepted

Given an edge $e$, such as $(9,18)$, you want to find the shortest path from $9$ to $18$ that doesn't contain $e$. So just remove $e$ (and all duplicates of $e$) from your list of edges, and run a standard shortest-path algorithm, such as Dijkstra's algorithm (Wikipedia link here), on the resulting graph.

share|improve this answer
    
thank you very much. greate. If you do not mind, could you please explain the steps that i should follow (as the original Dijkstra's algorithm use distances. but i do not have such. My creiteria is the number of points).sorry, me i am poor in this graph theories. do you think is it good, if i organise all nodes as a connected tree (parent -child)? then, can you explain how can i go further..PLz.. thanks –  niro Sep 27 '11 at 10:25
    
Just set all distances to $1$. And you don't need a connected tree, all you need is a list of edges (which you already have). –  TonyK Sep 27 '11 at 10:29
    
detail explantions are highly appriciating. –  niro Sep 27 '11 at 13:40
    
Hi, could you please tell me, how can i implement this. what would be the stoping creiteria, and so on. –  niro Sep 27 '11 at 14:26
1  
I've told you enough. In the end it's you who has to implement this, not me. –  TonyK Sep 27 '11 at 14:39

From what I can make out, you have a set $S$ of line segments, each defined by two points in a set of points $P$. By "containing only 2 points" I assume you mean you know in advance that each segment in $S$ contains exactly two points of $P$ and no more. When you say "I took a line and get an end point," I assume you mean you take a line segment (not a line), and access one of its endpoints. Your task is to build a list of the line segments connected. (I don't see how "This is like a tree"?)

Perhaps this is a way to proceed. First process $P$ to remove all duplicates and assign each point a unique point index; maybe you already start with this? Then process $S$ so that its two endpoints are described by point indices (rather than coordinates). Again, this may already be your starting situation. Now make two lists, $S_1$, the segments in $S$ sorted by the index of their first endpoint, and $S_2$, sorted by second endpoint.

Now start with any segment $s \in S$. Let one of its endpoint indices be $p$. Look in $S_1$ and $S_2$ (by binary search, or indexing) for segments whose first endpoint index is $p$. You should find one in each, call them $s_1$ and $s_2$. One of these should be $s$. The other is the one to which you should connect. Extend your list of segments by this one. Repeat.


Now that you have clarified your problem with an example, it is clear that what you seek is a way to enumerate all the cycles in a graph. Under that phrase, you can find lots of information on the web. For example, there is a Wikipedia page on "Cycle detection" that explains it at a high level. The problem has also been extensively discussed on StackOverflow, as many need this computation: SO:Finding all cycles in a graph and SO:Find all cycles in a graph, redux. Your experience that "This appear like a tree" is on the mark, for indeed the main idea is to perform a DFS (depth-first search) on the graph.

share|improve this answer
    
Thank you for the response. I am not clear what you said. I have modified my post by giving an example. Actually, I have unique point indices for each node of line segments. I already removed duplicated. (Sorry, not to say). –  niro Sep 26 '11 at 8:47
    
I did not understand from your original posting that what you actually have are many polygons, not just one polygon. My algorithm assumed the latter. Including the example makes the problem more clear; thanks. The same basic idea works, but now you will need to mark options already explored to avoid finding the same polygons repeatedly. (I cannot detail this now...) –  Joseph O'Rourke Sep 26 '11 at 13:31

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.