Matlab - common tangent of two objects

Author

common tangent of two objects

Abe Lau

2005-11-23, 3:59 am

Hi,
Having an 2D image segmented, I got two separate objects of
different size in an image. With the two objects being labeled (1
for object1, and 2 for object2), I wonder anyone could give me a hint
on how to find the two common tangents that touch both object1&2.

___________________
object1 object2
-------------------

--: the tangent lines

Thanks for any hint,
Abe Lau

Abe Lau

2005-11-23, 3:59 am

Sorry it got double posted.

would be great if all replies are redirected to this post, thx
Abe Lau, "common tangent of two objects" #, 23 Nov 2005 1:28 am </WebX?14@@.ef1c6f2>

Roger Stafford

2005-11-23, 7:59 am

In article <ef1c6f6.-1@webx.raydaftYaTP>, "Abe Lau"
<abelau<at@>gmail_dot._com> wrote:

> Hi,
> Having an 2D image segmented, I got two separate objects of
> different size in an image. With the two objects being labeled (1
> for object1, and 2 for object2), I wonder anyone could give me a hint
> on how to find the two common tangents that touch both object1&2.
>
> ___________________
> object1 object2
> -------------------
>
> --: the tangent lines
>
> Thanks for any hint,
> Abe Lau
-------------------------
Hello Abe,

First, I should point out that in general there are four, not two,
common tangents between two objects, with two of them crossing between the
objects and the other two crossing outside.

I have time only to outline an approach you might take. First, use
'convhull' to reduce your two objects to points in their respective convex
hulls. Your "tangent" lines cannot involve any points not in the two
convex hulls. In all the discussion which follows this, it will be
understood that the two objects have been thus reduced. I am assuming in
what follows that these two convex hulls do not intersect.

The next step is to take any two points, (x10,y10) and (x20,y20), in the
respective (reduced) objects and find the angle, a0, from one to the other
using a0 = atan2(y20-y10,x20-x10). a0 will lie between -pi and +pi. This
will be used as a base for all other angle determinations.

For each possible pair of points in the two respective objects, (x1,y1)
and (x2,y2), find the angle, a, from one to the other with the same
'atan2' function but modified using the base angle a0 in the following
manner:

a = a0 - pi + mod(atan2(y2-y1,x2-x1)-a0+pi, 2*pi);

This assures that each of the angles, a, will be selected so its
difference from base angle a0 is between -pi and +pi. Doing this may
place some of the a values either above pi or below -pi, but that is
necessary for the maximum/minimum process to follow.

Now, for each point in object 1 determine the maximum value for the
above angle a for various points in object 2. Among all these maxima, as
points are varied throughout object 1, find their minimum value, arriving
at a "minimax". The line between the corresponding points will constitute
one of your "tangents". There are three other cases to consider and each
of them gives rise to another "tangent": the maximin, the maximax, and the
minimin. This will give you the four tangent solutions between the two
objects.

You can either use two grand nested for-loops, doing all these minimum
and maximum calculations simultaneously, or else attempt a massive
vectorized version of all that. Unfortunately, doing the latter may
involve some rather large matrices.

The above is an "order n-squared" algorithm and may take quite a long
time to compute if the convex hulls each still have many points. I have
the uncomfortable feeling there must be some more clever ways in existence
for speeding up all this but I can't think of any at the moment.

(Remove "xyzzy" and ".invalid" to send me email.)
Roger Stafford

Roger Stafford

2005-11-23, 7:59 am

Hello Abe,

It occurs to me that a better way of finding two of the tangents might
be to find the polygons running through the successive vertices of the
convex hulls of the separate objects and through the vertices of the
convex hull of the combined objects, making three polygons altogether.
The four points where these different polygons separate would define the
endpoints of the two outer tangents. It's just an idea.

(Remove "xyzzy" and ".invalid" to send me email.)
Roger Stafford

Roger Stafford

2005-11-24, 4:02 am

In article
<ellieandrogerxyzzy-2311050412320001@pool1397.cvx3-bradley.dialup.earthlink.net>,
ellieandrogerxyzzy@mindspring.com.invalid (Roger Stafford) wrote:

> In article <ef1c6f6.-1@webx.raydaftYaTP>, "Abe Lau"
> <abelau<at@>gmail_dot._com> wrote:
>
> -------------------------
> Hello Abe,
>
> First, I should point out that in general there are four, not two,
> common tangents between two objects, with two of them crossing between the
> objects and the other two crossing outside.
>
> I have time only to outline an approach you might take. First, use
> 'convhull' to reduce your two objects to points in their respective convex
> hulls. Your "tangent" lines cannot involve any points not in the two
> convex hulls. In all the discussion which follows this, it will be
> understood that the two objects have been thus reduced. I am assuming in
> what follows that these two convex hulls do not intersect.
>
> The next step is to take any two points, (x10,y10) and (x20,y20), in the
> respective (reduced) objects and find the angle, a0, from one to the other
> using a0 = atan2(y20-y10,x20-x10). a0 will lie between -pi and +pi. This
> will be used as a base for all other angle determinations.
>
> For each possible pair of points in the two respective objects, (x1,y1)
> and (x2,y2), find the angle, a, from one to the other with the same
> 'atan2' function but modified using the base angle a0 in the following
> manner:
>
> a = a0 - pi + mod(atan2(y2-y1,x2-x1)-a0+pi, 2*pi);
>
> This assures that each of the angles, a, will be selected so its
> difference from base angle a0 is between -pi and +pi. Doing this may
> place some of the a values either above pi or below -pi, but that is
> necessary for the maximum/minimum process to follow.
>
> Now, for each point in object 1 determine the maximum value for the
> above angle a for various points in object 2. Among all these maxima, as
> points are varied throughout object 1, find their minimum value, arriving
> at a "minimax". The line between the corresponding points will constitute
> one of your "tangents". There are three other cases to consider and each
> of them gives rise to another "tangent": the maximin, the maximax, and the
> minimin. This will give you the four tangent solutions between the two
> objects.
>
> You can either use two grand nested for-loops, doing all these minimum
> and maximum calculations simultaneously, or else attempt a massive
> vectorized version of all that. Unfortunately, doing the latter may
> involve some rather large matrices.
>
> The above is an "order n-squared" algorithm and may take quite a long
> time to compute if the convex hulls each still have many points. I have
> the uncomfortable feeling there must be some more clever ways in existence
> for speeding up all this but I can't think of any at the moment.
>
> Roger Stafford
--------------------------
Hello Abe,

I finally worked out the detailed code for the vectorized solution I
first mentioned. Assume that x1,y1 are x-y coordinate vectors of your
object 1 after reduction to the vertices of its convex hull. Similarly
x2,y2 are vectors for reduced object 2. Then the following code finds a
pair of points in the two respective objects for each of the four possible
tangent lines, which you can use to generate the tangent lines. Probably
the first two tangents are the ones you are interested in. Again I remind
you that this assumes the two convex hulls do not overlap.

[X2,X1] = meshgrid(x2,x1);
[Y2,Y1] = meshgrid(y2,y1);
a0 = atan2(y2(1)-y1(1),x2(1)-x1(1));
a = a0 - pi + rem(atan2(Y2-Y1,X2-X1)-a0+3*pi,2*pi);
[mx,Ix] = max(a); [mn,In] = min(a);
[minmax,j1] = min(mx); i1 = Ix(j1);
[maxmin,j2] = max(mn); i2 = In(j2);
[maxmax,j3] = max(mx); i3 = Ix(j3);
[minmin,j4] = min(mn); i4 = In(j4);
% Points (x1(i1),y1(i1)) & (x2(j1),y2(j1)) lie on 1st tangent line
% " (x1(i2),y1(i2)) & (x2(j2),y2(j2)) lie on 2nd tangent line
% " (x1(i3),y1(i3)) & (x2(j3),y2(j3)) lie on 3rd tangent line
% " (x1(i4),y1(i4)) & (x2(j4),y2(j4)) lie on 4th tangent line

As I mentioned earlier, if there remain a large number of points in each
of the objects after reduction to convex hull vertices, the above matrices
will be very large and require a correspondingly long time for
computation. If these large sizes give you memory trouble, you can
readily convert this code to equivalent nested for-loops.

(Remove "xyzzy" and ".invalid" to send me email.)
Roger Stafford

Abe Lau

2005-11-24, 4:02 am

Roger Stafford wrote:
>
>
> Hello Abe,
>
> It occurs to me that a better way of finding two of the tangents
> might
> be to find the polygons running through the successive vertices of
> the
> convex hulls of the separate objects and through the vertices of
> the
> convex hull of the combined objects, making three polygons
> altogether.
> The four points where these different polygons separate would
> define the
> endpoints of the two outer tangents. It's just an idea.
>
> (Remove "xyzzy" and ".invalid" to send me email.)
> Roger Stafford
>

Hello Roger Stafford,
Thanks so much for your reply and explanation. I just tried the
2nd method you suggested, by comparing the convex hulls of object1,
object2, and (object1+object2) to get the two outer tangents. It
seems to work beautifully on my segmented CT data.

Thanks once again. It's such a elegant solution. and such a nice
birthday gift for me today :-)

Regards,
Abe Lau

Sponsored Links