Got Questions? Get Answers.
Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Binary check for polygons intersection

Subject: Binary check for polygons intersection

From: Sang-Ho Yun

Date: 23 Jan, 2013 22:47:06

Message: 1 of 11

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

Subject: Binary check for polygons intersection

From: Bruno Luong

Date: 23 Jan, 2013 23:26:08

Message: 2 of 11

"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

Subject: Binary check for polygons intersection

From: Sang-Ho Yun

Date: 23 Jan, 2013 23:37:08

Message: 3 of 11

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

Subject: Binary check for polygons intersection

From: Bruno Luong

Date: 23 Jan, 2013 23:50:09

Message: 4 of 11

"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

Subject: Binary check for polygons intersection

From: Matt J

Date: 23 Jan, 2013 23:53:08

Message: 5 of 11

"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?

Subject: Binary check for polygons intersection

From: Sang-Ho Yun

Date: 24 Jan, 2013 00:01:08

Message: 6 of 11

> 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

Subject: Binary check for polygons intersection

From: Sang-Ho Yun

Date: 24 Jan, 2013 00:22:09

Message: 7 of 11

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

Subject: Binary check for polygons intersection

From: Bruno Luong

Date: 24 Jan, 2013 00:27:07

Message: 8 of 11

"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

Subject: Binary check for polygons intersection

From: Bruno Luong

Date: 24 Jan, 2013 00:32:09

Message: 9 of 11

"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

Subject: Binary check for polygons intersection

From: Sang-Ho Yun

Date: 24 Jan, 2013 00:43:08

Message: 10 of 11

"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

Subject: Binary check for polygons intersection

From: Bruno Luong

Date: 24 Jan, 2013 06:38:08

Message: 11 of 11

"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

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us