Prev: first order auto-regressive process to model video traffic
Next: Galil Motion Controller
From: Steven Lord on 19 May 2010 13:33

"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message
news:ht0tbt$929$1(a)fred.mathworks.com...
> "John D'Errico" <woodchips(a)rochester.rr.com> wrote in message
> <ht0r6v$b68$1(a)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
slord(a)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


From: Rune Allnor on 19 May 2010 13:46
On 19 Mai, 14:34, "Ivo Petkovi?" <dzurdz...(a)net.hr> wrote:
> 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
From: Matt J on 19 May 2010 13:49
"Steven Lord" <slord(a)mathworks.com> wrote in message <ht17cr$kek$1(a)fred.mathworks.com>...

> >
> > 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)
From: Bruno Luong on 19 May 2010 18:40
I have take a pain to code it, LOL. I also take opportunity to improve my poly2poly() function for speed. Here we go:

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
From: Bruno Luong on 19 May 2010 19:35
A somewhat better polygons intersection:

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
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
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4
Prev: first order auto-regressive process to model video traffic
Next: Galil Motion Controller