Stick intersection path 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-sticks' path. Any idea for that? Thanks a lot!
On Sun, Sep 1, 2013 at 3:55 PM, Josè Luis Mietta < joseluismietta@yahoo.com.ar> wrote:
Given two arbitrary sticks, i need a simple and effective algorithm that determinate if that two sticks are conected by a 'intersected-sticks' path.
do you mean a test to see if two line segments intersect? This looks reasonable: http://wiki.processing.org/w/Line-Line_intersection It probably makes sense to translate to Cython (or use the C and call with cython). I"ve also got similar code in a little package of mine: https://github.com/ChrisBarker-NOAA/py_geometry Already Cython, and includes code to check a whole bunch at once, stored in numpy arrays: https://github.com/ChrisBarker-NOAA/py_geometry/blob/master/py_geometry/line... I hope it's useful to you. -Chris -Chris -Chris
Any idea for that?
Thanks a lot!
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
-- Christopher Barker, Ph.D. Oceanographer Emergency Response Division NOAA/NOS/OR&R (206) 526-6959 voice 7600 Sand Point Way NE (206) 526-6329 fax Seattle, WA 98115 (206) 526-6317 main reception Chris.Barker@noaa.gov
Hi Chris.
I wanna see if two line segments are connected by a path formed by line segments intersected.
Waiting for your answers.
Thanks a lot!
De: Chris Barker - NOAA Federal
do you mean a test to see if two line segments intersect? This looks reasonable: http://wiki.processing.org/w/Line-Line_intersection It probably makes sense to translate to Cython (or use the C and call with cython). I"ve also got similar code in a little package of mine: https://github.com/ChrisBarker-NOAA/py_geometry Already Cython, and includes code to check a whole bunch at once, stored in numpy arrays: https://github.com/ChrisBarker-NOAA/py_geometry/blob/master/py_geometry/line... I hope it's useful to you. -Chris -Chris -Chris Any idea for that?
Thanks a lot!
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
-- Christopher Barker, Ph.D. Oceanographer Emergency Response Division NOAA/NOS/OR&R (206) 526-6959 voice 7600 Sand Point Way NE (206) 526-6329 fax Seattle, WA 98115 (206) 526-6317 main reception Chris.Barker@noaa.gov _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
On 2 September 2013 02:50, Josè Luis Mietta
I wanna see if two line segments are connected by a path formed by line segments intersected.
You could build a network where each segment is a node and an intersection is a link. Then, you could use NetworkX connected_components to get groups of segments together.
On Sun, Sep 1, 2013 at 11:55 PM, Josè Luis Mietta < joseluismietta@yahoo.com.ar> wrote:
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-sticks' path. You may find it helpful to reword your problem using standard terminology. If I hadn't read your previous question, I would not have been able to understand what you meant by intersected sticks (or, as Chris thought at first, that you needed help determining the intersections). This will also help in searching Google for background and pre-existing software to solve your problem. You have an "undirected graph" (the sticks are "nodes", and the intersections are "edges") and you want to find if two given nodes are "reachable" from each other. You are currently representing your graph as an "adjacency matrix" `M` where `M[i,j]` is 1 iff nodes `i` and `j` have an edge between them and 0 otherwise. The "transitive closure" of your graph `M` is the graph that connects two nodes with an edge iff the two nodes are reachable from each other in the original graph `M`. There are several graph theory packages out there, like NetworkX, that will do this for you. Depending on the kinds of queries you would like to do, as David points out, want to compute the "connected components" of your graph; a connected component is a subgraph of your original graph such that all of the nodes are reachable from each other. You can also look up Python code for computing the transitive closure of a graph; it's not a complicated algorithm. However, this algorithm is usually implemented using a different representation of a graph than an adjacency matrix, so you may need to do a conversion. -- Robert Kern
Hi experts!
If I do:
G =Graph(M)
That is: to use the associated 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 I consider (M) is the adjacency matrix of this graph.
Then, I can do:
first_stick inG.connected_component_containing_vertex(second_stick)
This is 'True' if 'first_stick' is in the sub-graph formed by 'second_stick' and all sticks 'connected' with 'second_stick'.
The problem is that
G.connected_component_containing_vertex()
explore all the sub-graph.
How can I do (what is the code) for stop the iteration when the algorithm found 'first-stick'?
Waiting for your answers.
Thanks a lot!!
________________________________
De: Robert Kern
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-sticks' path.
You may find it helpful to reword your problem using standard terminology. If I hadn't read your previous question, I would not have been able to understand what you meant by intersected sticks (or, as Chris thought at first, that you needed help determining the intersections). This will also help in searching Google for background and pre-existing software to solve your problem. You have an "undirected graph" (the sticks are "nodes", and the intersections are "edges") and you want to find if two given nodes are "reachable" from each other. You are currently representing your graph as an "adjacency matrix" `M` where `M[i,j]` is 1 iff nodes `i` and `j` have an edge between them and 0 otherwise. The "transitive closure" of your graph `M` is the graph that connects two nodes with an edge iff the two nodes are reachable from each other in the original graph `M`. There are several graph theory packages out there, like NetworkX, that will do this for you. Depending on the kinds of queries you would like to do, as David points out, want to compute the "connected components" of your graph; a connected component is a subgraph of your original graph such that all of the nodes are reachable from each other. You can also look up Python code for computing the transitive closure of a graph; it's not a complicated algorithm. However, this algorithm is usually implemented using a different representation of a graph than an adjacency matrix, so you may need to do a conversion. -- Robert Kern _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
On Wed, Sep 4, 2013 at 3:17 PM, Josè Luis Mietta < joseluismietta@yahoo.com.ar> wrote:
Hi experts!
If I do:
G = Graph(M)
That is: to use the associated intersection graph, where the vertices are
It turns out that the matrix I consider (M) is the adjacency matrix of
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. this graph.
Then, I can do:
first_stick in G.connected_component_containing_vertex(second_stick)
This is 'True' if 'first_stick' is in the sub-graph formed by
'second_stick' and all sticks 'connected' with 'second_stick'.
The problem is that
G.connected_component_containing_vertex()
explore all the sub-graph.
How can I do (what is the code) for stop the iteration when the algorithm
found 'first-stick'? networkx.has_path(G, first_stick, second_stick) http://networkx.github.io/documentation/latest/reference/generated/networkx.... If you are going to be doing many queries, you should compute all of the path lengths, then you can query the final data structure easily. lengths = networkx.all_pairs_shortest_path_length(G) second_stick in lengths[first_stick] -- Robert Kern On Wed, Sep 4, 2013 at 3:17 PM, Josè Luis Mietta < joseluismietta@yahoo.com.ar> wrote:
Hi experts!
If I do:
G = Graph(M)
That is: to use the associated intersection graphhttps://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 I consider (M) is the adjacency matrixhttps://en.wikipedia.org/wiki/Adjacency_matrixof this graph.
Then, I can do:
first_stick in G.connected_component_containing_vertex(second_stick)
This is 'True' if 'first_stick' is in the sub-graph formed by 'second_stick' and all sticks 'connected' with 'second_stick'.
The problem is that
G.connected_component_containing_vertex()
explore all the sub-graph.
How can I do (what is the code) for stop the iteration when the algorithm found 'first-stick'?
Waiting for your answers.
Thanks a lot!!
------------------------------ *De:* Robert Kern
*Para:* Discussion of Numerical Python
*Enviado:* lunes, 2 de septiembre de 2013 10:40 *Asunto:* Re: [Numpy-discussion] Stick intersection path algorithm
On Sun, Sep 1, 2013 at 11:55 PM, Josè Luis Mietta < joseluismietta@yahoo.com.ar> wrote:
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-sticks' path.
You may find it helpful to reword your problem using standard terminology. If I hadn't read your previous question, I would not have been able to understand what you meant by intersected sticks (or, as Chris thought at first, that you needed help determining the intersections). This will also help in searching Google for background and pre-existing software to solve your problem.
You have an "undirected graph" (the sticks are "nodes", and the intersections are "edges") and you want to find if two given nodes are "reachable" from each other. You are currently representing your graph as an "adjacency matrix" `M` where `M[i,j]` is 1 iff nodes `i` and `j` have an edge between them and 0 otherwise. The "transitive closure" of your graph `M` is the graph that connects two nodes with an edge iff the two nodes are reachable from each other in the original graph `M`. There are several graph theory packages out there, like NetworkX, that will do this for you. Depending on the kinds of queries you would like to do, as David points out, want to compute the "connected components" of your graph; a connected component is a subgraph of your original graph such that all of the nodes are reachable from each other.
You can also look up Python code for computing the transitive closure of a graph; it's not a complicated algorithm. However, this algorithm is usually implemented using a different representation of a graph than an adjacency matrix, so you may need to do a conversion.
-- Robert Kern
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
-- Robert Kern
Thanks experts!
Thanks Robert Kern!
Two more questions about it:
1. networkx.has_path(G, first_stick, second_stick) stop when find second_stick or compute all the sub-graph and then evaluate if first_stick and second_stick are connected?
2. Using networkx or other tool: how can I obtain the 'clusters size' distribution (that is: number of clusters of size 'D', for all cluster-sizes)?
Thanks a lot!!
José Luis
________________________________
De: Robert Kern
Hi experts!
If I do:
G = Graph(M)
That is: to use the associated 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 I consider (M) is the adjacency matrix of this graph.
Then, I can do:
first_stick in G.connected_component_containing_vertex(second_stick)
This is 'True' if 'first_stick' is in the sub-graph formed by 'second_stick' and all sticks 'connected' with 'second_stick'.
The problem is that
G.connected_component_containing_vertex()
explore all the sub-graph.
How can I do (what is the code) for stop the iteration when the algorithm found 'first-stick'?
networkx.has_path(G, first_stick, second_stick)
http://networkx.github.io/documentation/latest/reference/generated/networkx....
If you are going to be doing many queries, you should compute all of the path lengths, then you can query the final data structure easily.
lengths = networkx.all_pairs_shortest_path_length(G)
second_stick in lengths[first_stick]
--
Robert Kern
On Wed, Sep 4, 2013 at 3:17 PM, Josè Luis Mietta
If I do: G =Graph(M)
That is: to use the associated 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 I consider (M) is the adjacency matrix of this graph.
Then, I can do: first_stick inG.connected_component_containing_vertex(second_stick) This is 'True' if 'first_stick' is in the sub-graph formed by 'second_stick' and all sticks 'connected' with 'second_stick'.
The problem is that
G.connected_component_containing_vertex()
explore all the sub-graph.
How can I do (what is the code) for stop the iteration when the algorithm found 'first-stick'?
Waiting for your answers.
Thanks a lot!!
________________________________ De: Robert Kern
Para: Discussion of Numerical Python
Enviado: lunes, 2 de septiembre de 2013 10:40 Asunto: Re: [Numpy-discussion] Stick intersection path algorithm
On Sun, Sep 1, 2013 at 11:55 PM, Josè Luis Mietta
wrote: 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-sticks' path.
You may find it helpful to reword your problem using standard terminology. If I hadn't read your previous question, I would not have been able to understand what you meant by intersected sticks (or, as Chris thought at first, that you needed help determining the intersections). This will also help in searching Google for background and pre-existing software to solve your problem.
You have an "undirected graph" (the sticks are "nodes", and the intersections are "edges") and you want to find if two given nodes are "reachable" from each other. You are currently representing your graph as an "adjacency matrix" `M` where `M[i,j]` is 1 iff nodes `i` and `j` have an edge between them and 0 otherwise. The "transitive closure" of your graph `M` is the graph that connects two nodes with an edge iff the two nodes are reachable from each other in the original graph `M`. There are several graph theory packages out there, like NetworkX, that will do this for you. Depending on the kinds of queries you would like to do, as David points out, want to compute the "connected components" of your graph; a connected component is a subgraph of your original graph such that all of the nodes are reachable from each other.
You can also look up Python code for computing the transitive closure of a graph; it's not a complicated algorithm. However, this algorithm is usually implemented using a different representation of a graph than an adjacency matrix, so you may need to do a conversion.
-- Robert Kern
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
_______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
-- Robert Kern _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
On 5 September 2013 13:14, Josè Luis Mietta
2. Using networkx or other tool: how can I obtain the 'clusters size' distribution (that is: number of clusters of size 'D', for all cluster-sizes)?
This is best asked in their mailing list. A possible way is: np.bincount([len(i) for i in nx.connected_components(G)]) For example: np.bincount([len(i) for i in nx.connected_components(nx.erdos_renyi_graph(100, 0.01))]) array([ 0, 39, 7, 3, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1])
Hi experts!
The array ([ 0, 39, 7, 3, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]) means that in the sistem (graph) are : 4 cluster of size 1, one cluster of size 3, one cluster of size 7 and one cluste of size 39?
What does means 'zero' (13 times) in the array?
Thans a lot!
José Luis
________________________________
De: Daπid
On 5 September 2013 17:03, Josè Luis Mietta
The array ([ 0, 39, 7, 3, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1]) means that in the sistem (graph) are : 4 cluster of size 1, one cluster of size 3, one cluster of size 7 and one cluste of size 39?
No, it means there are 39 of size 1, 7 of size 2 and so on. David.
Thanks so much!!
Best regards,
José Luis
________________________________
De: Daπid
Hi experts!
How can I create a networkx graph from the adjacency matrix M?
Thanks a lot,
José Luis
________________________________
De: Daπid
participants (4)
-
Chris Barker - NOAA Federal
-
Daπid
-
Josè Luis Mietta
-
Robert Kern