[Numpy-discussion] Stick intersection path algorithm

[Robert Kern]

On Sun, Sep 1, 2013 at 11:55 PM, Josè Luis Mietta <
joseluismietta at 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/numpy-discussion/attachments/20130902/1929b438/attachment.html>