Prev: first order auto-regressive process to model video traffic
Next: Galil Motion Controller
From: Matt J on 19 May 2010 10:42
"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.

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,:);
From: Bruno Luong on 19 May 2010 11:15
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht0tbt$929$1(a)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.

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
From: Matt J on 19 May 2010 11:52
"Bruno Luong" <b.luong(a)fogale.findmycountry> wrote in message <ht0v9r$io8$1(a)fred.mathworks.com>...
> "Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht0tbt$929$1(a)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.
From: Matt J on 19 May 2010 12:01
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <ht11f4$g0n$1(a)fred.mathworks.com>...

> 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...
From: John D'Errico on 19 May 2010 13:04
"Matt J " <mattjacREMOVE(a)THISieee.spam> wrote in message <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.

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