ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Mon, 24 Jun 2013 10:06:09 -0500Number of line segments in a group - algorithmhttp://ask.sagemath.org/question/10252/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/?8818abc218ccd909f8c0bba71446c3b5o.png
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!
Tue, 18 Jun 2013 08:39:38 -0500http://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/Answer by kcrisman for <p>Hi experts!</p>
<p>Im a newby SAGE, SciPy, Numpy and Python user.</p>
<p>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).</p>
<p>Each line in my algorith is random-generated and characterized by his start point (xi,yi) and his end-point (xf,yf).</p>
<p>For example, in the image attached</p>
<p><a href="http://subefotos.com/ver/?8818abc218ccd909f8c0bba71446c3b5o.png">http://subefotos.com/ver/?8818abc218c...</a></p>
<p>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.</p>
<p>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.</p>
<p>¿Any idea?</p>
<p>Waiting for your answers.</p>
<p>Thanks a lot!</p>
http://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/?answer=15100#post-id-15100Your matrix should be very useful if you use it as an [adjacency matrix](http://www.sagemath.org/doc/reference/graphs/sage/graphs/graph.html#supported-formats) 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](http://www.sagemath.org/doc/reference/graphs/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.connected_components_subgraphs).Tue, 18 Jun 2013 08:57:15 -0500http://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/?answer=15100#post-id-15100Answer by tmonteil for <p>Hi experts!</p>
<p>Im a newby SAGE, SciPy, Numpy and Python user.</p>
<p>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).</p>
<p>Each line in my algorith is random-generated and characterized by his start point (xi,yi) and his end-point (xf,yf).</p>
<p>For example, in the image attached</p>
<p><a href="http://subefotos.com/ver/?8818abc218ccd909f8c0bba71446c3b5o.png">http://subefotos.com/ver/?8818abc218c...</a></p>
<p>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.</p>
<p>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.</p>
<p>¿Any idea?</p>
<p>Waiting for your answers.</p>
<p>Thanks a lot!</p>
http://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/?answer=15132#post-id-15132I 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](http://en.wikipedia.org/wiki/Adjacency_matrix) of the [intersection graph](http://en.wikipedia.org/wiki/Intersection_graph) of your set of segments, and the clusters you are looking for are the [connected components](http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29) 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]
Mon, 24 Jun 2013 09:10:44 -0500http://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/?answer=15132#post-id-15132Comment by kcrisman for <p>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 <code>M</code> where there is a <code>1</code> at position <code>(i,j)</code> if the segment <code>i</code> intersects the segment <code>j</code>, and <code>0</code> otherwise.</p>
<p>The answer of <a href="/users/41/kcrisman/">@kcrisman</a> is correct: your matrix is the <a href="http://en.wikipedia.org/wiki/Adjacency_matrix">adjacency matrix</a> of the <a href="http://en.wikipedia.org/wiki/Intersection_graph">intersection graph</a> of your set of segments, and the clusters you are looking for are the <a href="http://en.wikipedia.org/wiki/Connected_component_%28graph_theory%29">connected components</a> of your graph.</p>
<p>To transform your matrix into a graph:</p>
<pre><code>sage: G = Graph(M) ; G
</code></pre>
<p>To see how your graph looks like:</p>
<pre><code>sage: G.plot()
</code></pre>
<p>To find the connected components of your graph:</p>
<pre><code>sage: CC = G.connected_components() ; CC
</code></pre>
<p><code>CC</code> 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:</p>
<pre><code>sage: len(CC)
</code></pre>
<p>If you want to see how many vertices there is in each connected component, just type:</p>
<pre><code>sage: [len(c) for c in CC]
</code></pre>
http://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/?comment=17458#post-id-17458Thanks, 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...Mon, 24 Jun 2013 10:06:09 -0500http://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/?comment=17458#post-id-17458Answer by mresimulator for <p>Hi experts!</p>
<p>Im a newby SAGE, SciPy, Numpy and Python user.</p>
<p>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).</p>
<p>Each line in my algorith is random-generated and characterized by his start point (xi,yi) and his end-point (xf,yf).</p>
<p>For example, in the image attached</p>
<p><a href="http://subefotos.com/ver/?8818abc218ccd909f8c0bba71446c3b5o.png">http://subefotos.com/ver/?8818abc218c...</a></p>
<p>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.</p>
<p>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.</p>
<p>¿Any idea?</p>
<p>Waiting for your answers.</p>
<p>Thanks a lot!</p>
http://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/?answer=15121#post-id-15121Thanks 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
Sun, 23 Jun 2013 09:45:57 -0500http://ask.sagemath.org/question/10252/number-of-line-segments-in-a-group-algorithm/?answer=15121#post-id-15121