Ask Your Question
0

Number of line segments in a group - algorithm

asked 2013-06-18 08:39:38 -0500

mresimulator gravatar image

updated 2013-06-18 08:53:40 -0500

Hi experts!

Im a newby SAGE, SciPy, Numpy and Python user.

I'm trying to write an algorithm that accounts for how many straight segment groups ('clusters') of a given dimension (dimension = number of lines that form the cluster).

Each line in my algorith is random-generated and characterized by his start point (xi,yi) and his end-point (xf,yf).

For example, in the image attached

http://subefotos.com/ver/?8818abc218c...

there are: one cluster formed by 9 line segments, one cluster consists of four line segments, one cluster consists of five line segments, two cluster formed by three line segments, four cluster formed by two line segments and one cluster consists of one single line segments.

Until now i only could write a code that generates a matrix of NxN (where N = total number of line segments ). In this matrix, the element located in row A column B is 'True' if the segment A is cut with segment B, and its value is 'False' if that two segments are NOT intersect.

¿Any idea?

Waiting for your answers.

Thanks a lot!

edit retag flag offensive close merge delete

3 answers

Sort by » oldest newest most voted
1

answered 2013-06-24 09:10:44 -0500

tmonteil gravatar image

I do not understand how you could build a matrix over the booleans or the strings in Sage ('True', 'False'). So, i will assume that you are able to build a matrix M where there is a 1 at position (i,j) if the segment i intersects the segment j, and 0 otherwise.

The answer of @kcrisman is correct: your matrix is the adjacency matrix of the intersection graph of your set of segments, and the clusters you are looking for are the connected components of your graph.

To transform your matrix into a graph:

sage: G = Graph(M) ; G

To see how your graph looks like:

sage: G.plot()

To find the connected components of your graph:

sage: CC = G.connected_components() ; CC

CC is a list of connected components, each connected component is a list of vertices. If you want to see how many components you have, just type:

sage: len(CC)

If you want to see how many vertices there is in each connected component, just type:

sage: [len(c) for c in CC]
edit flag offensive delete link more

Comments

Thanks, Thierry! I was going to do this, but didn't have the time over the weekend. I think that your first comment might have been the missing piece...

kcrisman gravatar imagekcrisman ( 2013-06-24 10:06:09 -0500 )edit
0

answered 2013-06-18 08:57:15 -0500

kcrisman gravatar image

Your matrix should be very useful if you use it as an adjacency matrix and then trying to get the number of connected components of the graph. I think that should give what you want... you might have to try to get more information about the connected components.

edit flag offensive delete link more
0

answered 2013-06-23 09:45:57 -0500

mresimulator gravatar image

Thanks for ypur answer kcrisman.

1) In my matrix (NxN) the element located in row A column B is 'True' if the segment A is cut with segment B, and its value is 'False' if that two segments are NOT intersect. Please note that one line segment can be intersected by more than one other

2) I cant see how to use the sage-based graph tools for transform my matrix (that content all the information about line segment intersections) in a counter of how many straight segment groups ('clusters') of a given dimension (dimension = number of lines that form the cluster).

Please help!

Thanks a lot

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-06-18 08:39:38 -0500

Seen: 225 times

Last updated: Jun 24 '13