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.Wed, 04 Sep 2013 05:58:13 -0500Line segments instersection algorithmhttp://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/Hi experts!
I wanna study the intersection between line segments (sticks).
I wrote a algorithm that generate a matrix, M, with N rows and N columns. The M-element Mij is 1 if stick number 'i' intersect stick number 'j' (obviously M is symmetric).
Given two arbitrary sticks, i need a simple and effective algorithm that determinate if that two sticks are conected by a 'intersected-stick' path.
Any idea for that?
Thanks a lot!
Sun, 01 Sep 2013 12:53:07 -0500http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/Answer by mresimulator for <p>Hi experts!</p>
<p>I wanna study the intersection between line segments (sticks).
I wrote a algorithm that generate a matrix, M, with N rows and N columns. The M-element Mij is 1 if stick number 'i' intersect stick number 'j' (obviously M is symmetric).</p>
<p>Given two arbitrary sticks, i need a simple and effective algorithm that determinate if that two sticks are conected by a 'intersected-stick' path.</p>
<p>Any idea for that?</p>
<p>Thanks a lot!</p>
http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?answer=15411#post-id-15411Hi experts!
How can I do for stop iteration when the algorithm find first_stick?
Thanks a lot!Wed, 04 Sep 2013 04:30:30 -0500http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?answer=15411#post-id-15411Comment by tmonteil for <p>Hi experts!</p>
<p>How can I do for stop iteration when the algorithm find first_stick?</p>
<p>Thanks a lot!</p>
http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17066#post-id-17066If you build a function `same_component(first_stick, second_stick)`, that starts from `second_stick` and depth_first_search around it, just `return True` when `first_stick` is found, and `return False` at the end of the search.Wed, 04 Sep 2013 05:29:39 -0500http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17066#post-id-17066Comment by mresimulator for <p>Hi experts!</p>
<p>How can I do for stop iteration when the algorithm find first_stick?</p>
<p>Thanks a lot!</p>
http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17065#post-id-17065Thanks. Must I write the depth_first_search algorithm or is already writen and I can modify it? How can I modify it?Wed, 04 Sep 2013 05:58:13 -0500http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17065#post-id-17065Answer by tmonteil for <p>Hi experts!</p>
<p>I wanna study the intersection between line segments (sticks).
I wrote a algorithm that generate a matrix, M, with N rows and N columns. The M-element Mij is 1 if stick number 'i' intersect stick number 'j' (obviously M is symmetric).</p>
<p>Given two arbitrary sticks, i need a simple and effective algorithm that determinate if that two sticks are conected by a 'intersected-stick' path.</p>
<p>Any idea for that?</p>
<p>Thanks a lot!</p>
http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?answer=15402#post-id-15402You can use the associated [intersection graph](https://en.wikipedia.org/wiki/Intersection_graph), where the vertices are the sticks and there is an edge between the two vertices if they intersect. Two sticks are "connected by a 'intersected-stick' path" if they are in the same connected component of this graph.
It turns out that the matrix you consider is the [adjacency matrix](https://en.wikipedia.org/wiki/Adjacency_matrix) of this graph.
Hence you can do something like:
sage: G = Graph(M)
sage: first_stick in G.connected_component_containing_vertex(second_stick)
The result is either `True` or `False` depending on wether `first_stick` and `second_stick` are connected by a path in the graph `G`.Sun, 01 Sep 2013 14:02:21 -0500http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?answer=15402#post-id-15402Comment by mresimulator for <p>You can use the associated <a href="https://en.wikipedia.org/wiki/Intersection_graph">intersection graph</a>, where the vertices are the sticks and there is an edge between the two vertices if they intersect. Two sticks are "connected by a 'intersected-stick' path" if they are in the same connected component of this graph.</p>
<p>It turns out that the matrix you consider is the <a href="https://en.wikipedia.org/wiki/Adjacency_matrix">adjacency matrix</a> of this graph.</p>
<p>Hence you can do something like:</p>
<pre><code>sage: G = Graph(M)
sage: first_stick in G.connected_component_containing_vertex(second_stick)
</code></pre>
<p>The result is either <code>True</code> or <code>False</code> depending on wether <code>first_stick</code> and <code>second_stick</code> are connected by a path in the graph <code>G</code>.</p>
http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17090#post-id-17090Thanks tmonteil! How works the algorinthm involved in G.connected_component_containing_vertex? Waiting for your answers. Thanks againSun, 01 Sep 2013 15:58:53 -0500http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17090#post-id-17090Comment by tmonteil for <p>You can use the associated <a href="https://en.wikipedia.org/wiki/Intersection_graph">intersection graph</a>, where the vertices are the sticks and there is an edge between the two vertices if they intersect. Two sticks are "connected by a 'intersected-stick' path" if they are in the same connected component of this graph.</p>
<p>It turns out that the matrix you consider is the <a href="https://en.wikipedia.org/wiki/Adjacency_matrix">adjacency matrix</a> of this graph.</p>
<p>Hence you can do something like:</p>
<pre><code>sage: G = Graph(M)
sage: first_stick in G.connected_component_containing_vertex(second_stick)
</code></pre>
<p>The result is either <code>True</code> or <code>False</code> depending on wether <code>first_stick</code> and <code>second_stick</code> are connected by a path in the graph <code>G</code>.</p>
http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17089#post-id-17089According to the source code, which you can get by typing
sage: G.connected_component_containing_vertex??
the connected component of `second_stick` is done by a [depth-first search ](http://en.wikipedia.org/wiki/Depth_first_search). If you need more speed, you can directly implement it from the matrix (and stop the iteration when you found `first_stick`). If you need to do a lot of queries to the same graph, you can also store its connected components:
sage: C = G.connected_components()
Mon, 02 Sep 2013 00:59:20 -0500http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17089#post-id-17089Comment by mresimulator for <p>You can use the associated <a href="https://en.wikipedia.org/wiki/Intersection_graph">intersection graph</a>, where the vertices are the sticks and there is an edge between the two vertices if they intersect. Two sticks are "connected by a 'intersected-stick' path" if they are in the same connected component of this graph.</p>
<p>It turns out that the matrix you consider is the <a href="https://en.wikipedia.org/wiki/Adjacency_matrix">adjacency matrix</a> of this graph.</p>
<p>Hence you can do something like:</p>
<pre><code>sage: G = Graph(M)
sage: first_stick in G.connected_component_containing_vertex(second_stick)
</code></pre>
<p>The result is either <code>True</code> or <code>False</code> depending on wether <code>first_stick</code> and <code>second_stick</code> are connected by a path in the graph <code>G</code>.</p>
http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17087#post-id-17087Thanks tmonteil! When you say 'you can directely implement it from the matrix (and stop the iteration when you found first_stick)'. How can I do that? Waiting for your answers. Thanks againMon, 02 Sep 2013 01:27:59 -0500http://ask.sagemath.org/question/10497/line-segments-instersection-algorithm/?comment=17087#post-id-17087