Line segments instersection algorithm

mresimulator
165 ●32 ●43 ●52

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!

add a comment

2 Answers

Sort by » oldest newest most voted

answered 11 years ago

tmonteil
27483 ●32 ●205 ●519 http://wiki.sagemath.o...

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.

link

Comments

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

mresimulator ( 11 years ago )

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 ( 11 years ago )

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 ( 11 years ago )

add a comment

answered 11 years ago

mresimulator
165 ●32 ●43 ●52

Hi experts!

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

Thanks a lot!

link

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 ( 11 years ago )

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

mresimulator ( 11 years ago )

add a comment

Your Answer

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

Add Answer

Line segments instersection algorithm

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Line segments instersection algorithm savecancel

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Line segments instersection algorithm