Line segments instersection algorithm

asked 2013-09-01 19:53:07 +0100

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!

edit retag flag offensive close merge delete

add a comment

2 Answers

Sort by » oldest newest most voted

answered 2013-09-01 21:02:21 +0100

tmonteil
27423 ●31 ●204 ●517 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.

edit flag offensive delete link

Comments

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

mresimulator ( 2013-09-01 22:58:53 +0100 )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 ( 2013-09-02 07:59:20 +0100 )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 ( 2013-09-02 08:27:59 +0100 )edit

add a comment

answered 2013-09-04 11:30:30 +0100

mresimulator
165 ●32 ●43 ●52

Hi experts!

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

Thanks a lot!

edit flag offensive delete 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 ( 2013-09-04 12:29:39 +0100 )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 ( 2013-09-04 12:58:13 +0100 )edit

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 edit

2 Answers

Comments

Comments

Your Answer

Question Tools

Stats

Related questions

Line segments instersection algorithm