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!

edit retag close merge delete

Sort by » oldest newest most voted

You can 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 you consider is the 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.

more

Thanks tmonteil! How works the algorinthm involved in G.connected_component_containing_vertex? Waiting for your answers. Thanks again

( 2013-09-01 22:58:53 +0200 )edit

According 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()

( 2013-09-02 07:59:20 +0200 )edit

Thanks 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 again

( 2013-09-02 08:27:59 +0200 )edit

Hi experts!

How can I do for stop iteration when the algorithm find first_stick?

Thanks a lot!

more

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

( 2013-09-04 12:29:39 +0200 )edit

Thanks. Must I write the depth_first_search algorithm or is already writen and I can modify it? How can I modify it?

( 2013-09-04 12:58:13 +0200 )edit