Thread Subject:

Binary check for polygons intersection

I have two groups of polygons (10000 polygons in one group, 1 million polygons in the other group). I want to know which polygons in each group have overlaps with the polygons in the other group. I know "polybool" can be used to take the intersection of overlapping polygons. However, I don't need the shape of the intersection. I only need binary parameter (either 1 for overlap or 0 for no-overlap) for each polygon in each group.

Any idea?

Thank you in advance,
Sang-Ho

"Sang-Ho Yun" wrote in message <kdpp9a$dd3$1@newscl01ah.mathworks.com>...
> I have two groups of polygons (10000 polygons in one group, 1 million polygons in the other group). I want to know which polygons in each group have overlaps with the polygons in the other group. I know "polybool" can be used to take the intersection of overlapping polygons. However, I don't need the shape of the intersection. I only need binary parameter (either 1 for overlap or 0 for no-overlap) for each polygon in each group.
>
> Any idea?

http://www.mathworks.com/matlabcentral/fileexchange/27673-2d-polygon-edges-intersection

% Bruno

Thank you Bruno for your answer. However, it looks like when one polygon entirely includes the other with no intersecting line segments, your function would not return TRUE (please correct me if I am wrong). My task needs TRUE return for this case.

Thank you,
Sang-Ho


"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kdprig$l7c$1@newscl01ah.mathworks.com>...
> "Sang-Ho Yun" wrote in message <kdpp9a$dd3$1@newscl01ah.mathworks.com>...
> > I have two groups of polygons (10000 polygons in one group, 1 million polygons in the other group). I want to know which polygons in each group have overlaps with the polygons in the other group. I know "polybool" can be used to take the intersection of overlapping polygons. However, I don't need the shape of the intersection. I only need binary parameter (either 1 for overlap or 0 for no-overlap) for each polygon in each group.
> >
> > Any idea?
>
> http://www.mathworks.com/matlabcentral/fileexchange/27673-2d-polygon-edges-intersection
>
> % Bruno

"Sang-Ho Yun" wrote in message <kdps74$n7c$1@newscl01ah.mathworks.com>...
> Thank you Bruno for your answer. However, it looks like when one polygon entirely includes the other with no intersecting line segments, your function would not return TRUE (please correct me if I am wrong). My task needs TRUE return for this case.
>

There are two functions, look again.

Bruno

"Sang-Ho Yun" wrote in message <kdpp9a$dd3$1@newscl01ah.mathworks.com>...
> I have two groups of polygons (10000 polygons in one group, 1 million polygons in the other group). I want to know which polygons in each group have overlaps with the polygons in the other group. I know "polybool" can be used to take the intersection of overlapping polygons. However, I don't need the shape of the intersection. I only need binary parameter (either 1 for overlap or 0 for no-overlap) for each polygon in each group.
===============

Are they convex polygons?

> Are they convex polygons?

The polygons in one group is always convex (pixel boundary), but the polygons in the other group are not always convex (building outlines).

Thank you,
Sang-Ho

> There are two functions, look again.
>
> Bruno

Thank you. I revisited your functions. Your functions are for polygon EDGE intersection rather than polygon area intersection. I need polygon area intersection. Please let me know if I still misunderstood.

"Sang-Ho Yun" wrote in message <kdpurg$2fl$1@newscl01ah.mathworks.com>...
> > There are two functions, look again.
> >
> > Bruno
>
> Thank you. I revisited your functions. Your functions are for polygon EDGE intersection rather than polygon area intersection. I need polygon area intersection. Please let me know if I still misunderstood.

Yes, you are still miss understood. Function isintersect checks area intersection.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
>
> Yes, you are still miss understood. Function isintersect checks area intersection.

The statement:

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
   ...

treats the case where one polygonal is entirely included to the other.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <kdpve9$4cq$1@newscl01ah.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message
> >
> > Yes, you are still miss understood. Function isintersect checks area intersection.
>
> The statement:
>
> 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
> ...
>
> treats the case where one polygonal is entirely included to the other.
>
> Bruno

Thank you. I just tested it, and it worked well. By the way, does it handle multiple polygons (separated by nans) at once? I just noticed that running this on millions of polygons in a for loop would take for ever.

Thanks,
Sang-Ho

"Sang-Ho Yun" wrote in message <kdq02s$6h6$1@newscl01ah.mathworks.com>...

> Thank you. I just tested it, and it worked well. By the way, does it handle multiple polygons (separated by nans) at once?

Currently no, but you might try to adapt the code. The edge intersecting part can be vectorized straightforward. The other part, you might hack the code of inpolygon,

Bruno