Prev: first order auto-regressive process to model video traffic
Next: Galil Motion Controller
From: Ivo Petkovi? on 19 May 2010 08:34
Hi!

I need to create some very fast algorithm that can tell me if intersection between two polygons exist. I don't need to know how this intersection polygon looks like .That is problem with polybool function which i currently use. It is slow because it finds and returns intersection polygon, but i only want the function that returns 1 (if intersection exists) or 0 (if it doesn't exist). I can't find anything similar to that in matlab and it is important to me to be fast. Anyone got any idea?

Thx!
From: Matt J on 19 May 2010 09:14
"Ivo Petkovi?" <dzurdzica(a)net.hr> wrote in message <ht0lrt$f5m$1(a)fred.mathworks.com>...
> Hi!
>
> I need to create some very fast algorithm that can tell me if intersection between two polygons exist. I don't need to know how this intersection polygon looks like .That is problem with polybool function which i currently use. It is slow because it finds and returns intersection polygon, but i only want the function that returns 1 (if intersection exists) or 0 (if it doesn't exist). I can't find anything similar to that in matlab and it is important to me to be fast. Anyone got any idea?
=========

I'm not sure if there is a way to determine intersection without finding the actual intersection polygon, but you might test other approaches to see if you can improve the speed.

For example, an alternative might be to use con2vert and vert2con on the file exchange. Using vert2con you can obtain linear inequalities for the 2 polygons, which will in turn let you form a combined set of inequalities for the intersection polygon. Feed the latter into con2vert and, if it returns a non-trivial output, you will know the intersection exists.

Another alternative would be to use linprog (if you have the Opt Toolbox) and try to run an iteration of a linear program solver over the intersection polygon. linprog would then use its own tests to try to find out if the problem is feasible, i.e. if an intersection exists.
From: Bruno Luong on 19 May 2010 09:28
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht0o6t$ir5$1(a)fred.mathworks.com>...
>
>
> For example, an alternative might be to use con2vert and vert2con on the file exchange. Using vert2con you can obtain linear inequalities for the 2 polygons, which will in turn let you form a combined set of inequalities for the intersection polygon. Feed the latter into con2vert and, if it returns a non-trivial output, you will know the intersection exists.
>
> Another alternative would be to use linprog (if you have the Opt Toolbox) and try to run an iteration of a linear program solver over the intersection polygon. linprog would then use its own tests to try to find out if the problem is feasible, i.e. if an intersection exists.

Both options require - I assume - the polygons are convex.

Bruno
From: Ivo Petkovi? on 19 May 2010 09:41
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht0o6t$ir5$1(a)fred.mathworks.com>...
> "Ivo Petkovi?" <dzurdzica(a)net.hr> wrote in message <ht0lrt$f5m$1(a)fred.mathworks.com>...
> > Hi!
> >
> > I need to create some very fast algorithm that can tell me if intersection between two polygons exist. I don't need to know how this intersection polygon looks like .That is problem with polybool function which i currently use. It is slow because it finds and returns intersection polygon, but i only want the function that returns 1 (if intersection exists) or 0 (if it doesn't exist). I can't find anything similar to that in matlab and it is important to me to be fast. Anyone got any idea?
> =========
>
> I'm not sure if there is a way to determine intersection without finding the actual intersection polygon, but you might test other approaches to see if you can improve the speed.
>
> For example, an alternative might be to use con2vert and vert2con on the file exchange. Using vert2con you can obtain linear inequalities for the 2 polygons, which will in turn let you form a combined set of inequalities for the intersection polygon. Feed the latter into con2vert and, if it returns a non-trivial output, you will know the intersection exists.
>
> Another alternative would be to use linprog (if you have the Opt Toolbox) and try to run an iteration of a linear program solver over the intersection polygon. linprog would then use its own tests to try to find out if the problem is feasible, i.e. if an intersection exists.

you believe that is going to be faster than checking if the matrix that returns polybool is empty?
From: John D'Errico on 19 May 2010 10:05
"Ivo Petkovi?" <dzurdzica(a)net.hr> wrote in message <ht0lrt$f5m$1(a)fred.mathworks.com>...
> Hi!
>
> I need to create some very fast algorithm that can tell me if intersection between two polygons exist. I don't need to know how this intersection polygon looks like .That is problem with polybool function which i currently use. It is slow because it finds and returns intersection polygon, but i only want the function that returns 1 (if intersection exists) or 0 (if it doesn't exist). I can't find anything similar to that in matlab and it is important to me to be fast. Anyone got any idea?
>
> Thx!

I might try this...

1. Test to see if a single vertex of polygon 1 is entirely
contained inside polygon 2. It will be sufficient to test
a single point here. Use inpolygon, on vertex 1 of
polygon 1.

2. Test to see if a single vertex of polygon 2 is contained
inside polygon 1. Use inpolygon, on vertex 1 of polygon 2.

3. Test to see if any of the edges between two two polygons
ever intersect. Doug Schwarz's intersections code on the FEX
will do this nicely.

These three tests in combination might potentially be slower
than just testing the output of polybool for empty anyway.

John
 |  Next  |  Last
Pages: 1 2 3 4
Prev: first order auto-regressive process to model video traffic
Next: Galil Motion Controller