# Number of line segments in a group - algorithm

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?

Thanks a lot!

edit retag close merge delete

Sort by » oldest newest most voted

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]

more

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...

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).

Thanks a lot

more

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.

more