Find out if intersection of 2 polygons exist
Ivo Petkovi?
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!
Matt J
> 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.
Bruno Luong
>
>
> 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
Ivo Petkovi?
you believe that is going to be faster than checking if the matrix that returns polybool is empty?
John D'Errico
>
> 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
Matt J
> 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.
==========
And 3. would be necessary, it seems to me, only if these are unbounded polygons.
The only change I would make is, if the polygons are convex, to use vert2con_special below instead of inpolygon. It avoids a lot of the overhead encumbering inpolygon due to the fact that inpolygon also needs to be able to handle non-convex polygons.
function [A,b]=vert2con_special(a)
%Finds the expression of a 2D polygon as a set of linear inequalities from
%a set of vertices
%
% [A,b]=vert2con_special(a)
%
%in:
%
% a: Nx2 matrix whos rows are polygon vertex coordinates. The rows must
% must be ordered so that adjacent rows correspond to adjacent vertices
% (which will trivially be the case for triangles).
%
%out:
%
% [A,b]: Nx1 vector and Nx2 matrix such that A*x<=b if and only if x is a point
% inside the polygon
%
%
%Example: Detect whether a point is in a triangle
%
% %%%data
% Vertices=[0 0; 1 0; 0 1]; %vertices of a triangle
% p1=[.5;.25]; %a point inside the triangle
% p2=[.5;-.25];%a point outside the triangle
%
% [A,b]=vert2con_special(Vertices);
%
% >>all(A*p1<=b) %Test if p1 is in the triangle.
%
% ans =
%
% 1
%
% >>all(A*p2<=b) %Test if p2 in the triangle.
%
% ans =
%
% 0
centroid=mean(a).';
R=[0 1; -1 0];
A=diff([a;a(1,:)])*R;
b=sum(A.*a,2);
ii=(A*centroid>=b);
b(ii)=-b(ii);
A(ii,:)=-A(ii,:);
Bruno Luong
>
> And 3. would be necessary, it seems to me, only if these are unbounded polygons.
>
Why? John's method seems just about right and without redundancy for any polygons.
A) If the edges intersect then the polygons intersect.
B) Otherwise, the polygons intersect if and only if one is completely included in the other, and this fact can be check with a single vertexes.
Beside Doug's submission, I have programmed a function called POLY2POLY that detect intersection of edges between two polygons
http://www.mathworks.com/matlabcentral/newsreader/view_thread/160015
That was a while ago, and quick and dirty codded, this can be better optimized for speed.
Bruno
Matt J
> "Matt J " <mattja...@THISieee.spam> wrote in message <ht0tbt$929$1...@fred.mathworks.com>...
>
> >
> > And 3. would be necessary, it seems to me, only if these are unbounded polygons.
> >
>
> Why? John's method seems just about right and without redundancy for any polygons.
Forget it.
I still think it would be good to have the OP confirm whether or not the polygon's are convex, to see if we can exploit that.
In addition to avoiding inpolygon, for example, it might be an efficient test to compute all the vector differences
Ai-Bj,
where Ai are vertices in polygon 1 and Bj are vertices in polygon 2. In the case of convex non-intersecting polygons, I believe these vector differences should all be separated by acute angles.
Matt J
> In addition to avoiding inpolygon, for example, it might be an efficient test to compute all the vector differences
>
> Ai-Bj,
>
> where Ai are vertices in polygon 1 and Bj are vertices in polygon 2. In the case of convex non-intersecting polygons, I believe these vector differences should all be separated by acute angles.
=======================
Or rather, the differences should all lie in a common halfspace, which we might be able to detect somehow...
John D'Errico
> "John D'Errico" <wood...@rochester.rr.com> wrote in message <ht0r6v$b68$1...@fred.mathworks.com>...
>
> > 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.
> ==========
>
> And 3. would be necessary, it seems to me, only if these are unbounded polygons.
This is not true at all.
You can easily create a pair of polygons which have
an intersection when neither polygon contains any
vertex of the other polygon and both polygons are
nicely bounded, yet there is a non-empty intersection.
Triangles will suffice.
Consider the pair of triangles with (x,y) pairs given
in the rows of V1 and V2.
V1 = [0 0;0 1;1 0]
V2 = [-.5 .5;1 1;1 .5];
trimesh([1 2 3],V1(:,1),V1(:,2),'color','r','marker','o')
hold on
trimesh([1 2 3],V2(:,1),V2(:,2),'color','b','marker','x')
John
Steven Lord
"Matt J " <mattja...@THISieee.spam> wrote in message
> "John D'Errico" <wood...@rochester.rr.com> wrote in message
> <ht0r6v$b68$1...@fred.mathworks.com>...
>
>> 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.
> ==========
>
> And 3. would be necessary, it seems to me, only if these are unbounded
> polygons.
patch([1 2 2 1 1], [0 0 3 3 0], 'r')
patch([0 3 3 0 0], [1 1 2 2 1], 'g')
These two polygons are bounded (the axes limits are [0 3 0 3] and the
polygons fit entirely in the axes) and satisfy conditions 1 and 2; you need
to use condition 3 to determine that they do in fact intersect.
--
Steve Lord
sl...@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com
Rune Allnor
> 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?
If you want fast you probably want to ditch matlab and roll your own.
The task is a standard problem in computational geometry, and is used
as one of a few standard motivating problems to study data structures
and algorithms in the field of Computational Geometry. The general
idea
is based on finding intersections between edges of the two polygons.
If intersections exist, the polygons intersect. If no intersections
exist, one needs to do additional tests to determine if the two
polygons overlap or are disjoint.
Check out the textbooks by de Berg & al, and by Preparata & Shamos
for the details of the algorithms.
Rune
Matt J
> >
> > And 3. would be necessary, it seems to me, only if these are unbounded
> > polygons.
>
> patch([1 2 2 1 1], [0 0 3 3 0], 'r')
> patch([0 3 3 0 0], [1 1 2 2 1], 'g')
>
> These two polygons are bounded (the axes limits are [0 3 0 3] and the
> polygons fit entirely in the axes) and satisfy conditions 1 and 2; you need
> to use condition 3 to determine that they do in fact intersect.
Guys, I already recanted, hours ago, what I said about (3) being unnecessary. See my response to Bruno (Message #8)
Bruno Luong
function b = isintersect(P1, P2)
% function b = isintersect(P1, P2)
% Check if two polygons intersect
c = poly2poly(P1, P2);
if isempty(c)
b = inpolygon(P2(1,1),P2(2,1),P1(1,:),P1(2,:)) || ...
inpolygon(P1(1,1),P1(2,1),P2(1,:),P2(2,:));
else
b = true;
end
end % isintersect
function c = poly2poly(P1, P2)
% function c = poly2poly(P1, P2)
% intersection of two polygons P1 and P2.
% P1 and P2 are two-row arrays, each column is a vertice
% c is also two-row arrays, each column is an intersecting point
% Pad the first point to the end if necessary
if ~isequal(P1(:,1),P1(:,end))
P1 = [P1 P1(:,1)];
end
if ~isequal(P2(:,1),P2(:,end))
P2 = [P2 P2(:,1)];
end
c = zeros(2,0);
for n=2:size(P1,2)
c=[c seg2poly(P1(:,n-1:n), P2)]; %#ok
end
end % poly2poly
function c = seg2poly(s1, P)
% function c = seg2poly(s1, P)
% Check if a segment (2 x 2) segment s1 intersects with a polygon P.
% s(:,1) is the first point s(:,2) is the the second point of the segment.
% P is (2 x n) arrays, each column is a vertices
% Translate and rotation so that first point is origin
% the second point is on y-axis
a = s1(:,1);
M = bsxfun(@minus, P, a);
b = s1(:,2)-a;
nb2 = b(1)^2+b(2)^2;
R = [b(2) -b(1);
b(1) b(2)];
M = R*M;
sx = sign(M(1,:));
% x -coordinates has opposite signs
ind = sx(1:end-1).*sx(2:end) <= 0;
if any(ind)
ind = find(ind);
% cross point to y-axis
x1 = M(1,ind);
x2 = M(1,ind+1);
y1 = M(2,ind);
y2 = M(2,ind+1);
dx = x2-x1;
y = (y1.*x2-y2.*x1)./dx;
y = y/nb2;
ind = y>=0 & y<1;
if any(ind)
c = bsxfun(@plus, b*y(ind), a);
else
c = zeros(2,0);
end
else
c = zeros(2,0);
end
end % seg2poly
% Bruno
Bruno Luong
function b = isintersect(P1, P2)
% function b = isintersect(P1, P2)
% Check if two polygons intersect
% INPUTS:
% P1 and P2 are two-row arrays, each column is a vertice, assuming
% ordered along the boundary
% OUTPUT:
% b is true if two polygons intersect
c = poly2poly(P1, P2);
if isempty(c)
b = inpolygon(P2(1,1),P2(2,1),P1(1,:),P1(2,:)) || ...
inpolygon(P1(1,1),P1(2,1),P2(1,:),P2(2,:));
else
b = true;
end
end % isintersect
function c = poly2poly(P1, P2)
% function c = poly2poly(P1, P2)
% Intersection of two polygons P1 and P2.
% INPUTS:
% P1 and P2 are two-row arrays, each column is a vertice
% OUTPUT:
% c is also two-row arrays, each column is an intersecting point
% Pad the first point to the end if necessary
if ~isequal(P1(:,1),P1(:,end))
P1 = [P1 P1(:,1)];
end
if ~isequal(P2(:,1),P2(:,end))
P2 = [P2 P2(:,1)];
end
% swap P1 P2 so that we loop on a smaller one
if size(P1,2) > size(P2,2)
[P1 P2] = deal(P2, P1);
end
c = zeros(2,0);
% Loop over segments of P1
for n=2:size(P1,2)
c = [c seg2poly(P1(:,n-1:n), P2)]; %#ok
end
end % poly2poly
function c = seg2poly(s1, P)
% function c = seg2poly(s1, P)
% Check if a segment (2 x 2) segment s1 intersects with a polygon P.
% s(:,1) is the first point s(:,2) is the the second point of the segment.
% P is (2 x n) arrays, each column is a vertices
% Translate and rotation so that first point is origin
% the second point is on y-axis
a = s1(:,1);
M = bsxfun(@minus, P, a);
b = s1(:,2)-a;
x = [b(2) -b(1)]*M;
sx = sign(x);
% x -coordinates has opposite signs
ind = sx(1:end-1).*sx(2:end) <= 0;
if any(ind)
ind = find(ind);
% cross point to y-axis
x1 = x(ind);
x2 = x(ind+1);
d = b.'/(b(1)^2+b(2)^2);
y1 = d*M(:,ind);
y2 = d*M(:,ind+1);
dx = x2-x1;
% We won't bother with the degenerate case of dx=0 and x1=0
y = (y1.*x2-y2.*x1)./dx;
% Check if the cross point is inside the segment
Ivo Petkovi?
I will try it now. Thanks man!