1
$\begingroup$

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.

  • 0
    @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.2011-09-26

2 Answers 2

1

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.

  • 1
    I've told you enough. In the end it's you who has to implement this, not me.2011-09-27
1

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.

  • 0
    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...)2011-09-26