Ask Your Question
0

Line segments instersection algorithm

asked 2013-09-01 12:53:07 -0600

mresimulator gravatar image

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 flag offensive close merge delete

2 answers

Sort by ยป oldest newest most voted
1

answered 2013-09-01 14:02:21 -0600

tmonteil gravatar image

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.

edit flag offensive delete link more

Comments

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

mresimulator gravatar imagemresimulator ( 2013-09-01 15:58:53 -0600 )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()

tmonteil gravatar imagetmonteil ( 2013-09-02 00:59:20 -0600 )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

mresimulator gravatar imagemresimulator ( 2013-09-02 01:27:59 -0600 )edit
0

answered 2013-09-04 04:30:30 -0600

mresimulator gravatar image

Hi experts!

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

Thanks a lot!

edit flag offensive delete link more

Comments

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.

tmonteil gravatar imagetmonteil ( 2013-09-04 05:29:39 -0600 )edit

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

mresimulator gravatar imagemresimulator ( 2013-09-04 05:58:13 -0600 )edit

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2013-09-01 12:53:07 -0600

Seen: 163 times

Last updated: Sep 04 '13