Board index » delphi » Polygon inside polygon

Polygon inside polygon

Hi to all,

How can I know if one polygon is inside another polygon ?

type
    TPoint2D = record
        x,y:Double;
    end;
var
    Polygon1: array[0..10] of TPoint2D;
    Polygon2: array[0..5] of TPoint2D;

begin
   ... fill Polygon1 and Polygon2 here.

   // Now...how to know if Polygon2 is inside Polygon1 ???

..

If you test every point in Polygon2 against if that point is inside Polygon1
that does not work because some line in Polygon2 can intersect other line in
Polygon1.

TIA
Alex

 

Re:Polygon inside polygon


It the lines intersect, then by definition, one of the points of polygon2 must
be outside polygon1, no? Or am I missing something?
Quote
Alex S wrote:
>    // Now...how to know if Polygon2 is inside Polygon1 ???

> If you test every point in Polygon2 against if that point is inside Polygon1
> that does not work because some line in Polygon2 can intersect other line in
> Polygon1.

Re:Polygon inside polygon


That definition only applies to regular polygons. I think he is talking
about irregular polygons

"Sue D. Nom" <su...@courthouse.com> wrote in message
news:3C5179FF.715B1F65@courthouse.com...

Quote
> It the lines intersect, then by definition, one of the points of polygon2
must
> be outside polygon1, no? Or am I missing something?

> Alex S wrote:

> >    // Now...how to know if Polygon2 is inside Polygon1 ???

> > If you test every point in Polygon2 against if that point is inside
Polygon1
> > that does not work because some line in Polygon2 can intersect other
line in
> > Polygon1.

Re:Polygon inside polygon


Check for line intersection.

The following page my give you the clues that you need. Pay spetial atention
to the notes at the end.

http://astronomy.swin.edu.au/pbourke/geometry/lineline2d/

Jorge

Quote
"Alex S" <graph_developm...@yahoo.com> wrote in message

news:3c50af73_1@dnews...
Quote
> Hi to all,

> How can I know if one polygon is inside another polygon ?

> type
>     TPoint2D = record
>         x,y:Double;
>     end;
> var
>     Polygon1: array[0..10] of TPoint2D;
>     Polygon2: array[0..5] of TPoint2D;

> begin
>    ... fill Polygon1 and Polygon2 here.

>    // Now...how to know if Polygon2 is inside Polygon1 ???

> ..

> If you test every point in Polygon2 against if that point is inside
Polygon1
> that does not work because some line in Polygon2 can intersect other line
in
> Polygon1.

> TIA
> Alex

Re:Polygon inside polygon


If by "irregular polygons" you mean those that have inclusions, or concave
sides, or that have donut holes in them, then the solution is simple.  For
every point in polygon2, simply drop a line from the point to the x axis.  If
the line from the point crosses lines in polygon1 an odd number of times then
the point is in polygon1, if it crosses an even number of polygon1 lines, it
must be outside of polygon1.  All you need is for one polygon2 point to fail
this test to know that some part of it is outside polygon1.
Quote
"Jorge E. Perez" wrote:
> That definition only applies to regular polygons. I think he is talking about
> irregular polygons

> "Sue D. Nom" <su...@courthouse.com> wrote in message
> news:3C5179FF.715B1F65@courthouse.com...
> > It the lines intersect, then by definition, one of the points of polygon2
> must
> > be outside polygon1, no? Or am I missing something?

> > Alex S wrote:

> > >    // Now...how to know if Polygon2 is inside Polygon1 ???

> > > If you test every point in Polygon2 against if that point is inside
> Polygon1
> > > that does not work because some line in Polygon2 can intersect other
> line in
> > > Polygon1.

Re:Polygon inside polygon


Thanks for the answer.

Is simply to check if one polygon intersects another polygon.

What I want to know if Polygon2 is completely inside polygon1 (no
intersection) or viceversa. Like the following (althoug these are
rectangles):

+-----------------------------+
|                                             |
|     +-------------+                |
|      |                     |                |
|      |                     |                |
|      |                     |                |
|      |                     |                |
|     +-------------+                |
|                                             |
+----------------------------+

Polygon clipping algorithms could be the sollution: If I obtain the
intersection of Polygon2 and Polygon1 and the result is the same polygon2,
then Polygon 2 is inside Polygon1 or viceversa

....but two poins against this:

    - Very difficult to implement a polygon clipping algorithm.
    - Very slow just to determine if polygon2 fully inside polygon1 (maybe).

Any other solluion for this ?

Thanks
Alex

"Jorge E. Perez" <jorg...@unm.edu> wrote in message news:3c519c80_1@dnews...

Quote
> Check for line intersection.

> The following page my give you the clues that you need. Pay spetial
atention
> to the notes at the end.

> http://astronomy.swin.edu.au/pbourke/geometry/lineline2d/

> Jorge

> "Alex S" <graph_developm...@yahoo.com> wrote in message
> news:3c50af73_1@dnews...
> > Hi to all,

> > How can I know if one polygon is inside another polygon ?

> > type
> >     TPoint2D = record
> >         x,y:Double;
> >     end;
> > var
> >     Polygon1: array[0..10] of TPoint2D;
> >     Polygon2: array[0..5] of TPoint2D;

> > begin
> >    ... fill Polygon1 and Polygon2 here.

> >    // Now...how to know if Polygon2 is inside Polygon1 ???

> > ..

> > If you test every point in Polygon2 against if that point is inside
> Polygon1
> > that does not work because some line in Polygon2 can intersect other
line
> in
> > Polygon1.

> > TIA
> > Alex

Re:Polygon inside polygon


Hi Alex,

Quote
> Polygon clipping algorithms could be the sollution: If I obtain the
> intersection of Polygon2 and Polygon1 and the result is the same polygon2,
> then Polygon 2 is inside Polygon1 or viceversa

> ....but two poins against this:

>     - Very difficult to implement a polygon clipping algorithm.
>     - Very slow just to determine if polygon2 fully inside polygon1 (maybe).

Did you try the CombineRegion GDI call?
http://msdn.microsoft.com/library/en-us/gdi/regions_7tf2.asp

Thrse

Re:Polygon inside polygon


Hi Sue,

Quote
> For every point in polygon2, simply drop a line from the point to the x axis.
If
> the line from the point crosses lines in polygon1 an odd number of times then
> the point is in polygon1, if it crosses an even number of polygon1 lines, it
> must be outside of polygon1.  All you need is for one polygon2 point to fail
> this test to know that some part of it is outside polygon1.

In general you only know the coordinates of the vertices, and it does not seem
possible to compute the coordinates of "every point" of the polygon, as there is
an infinite number of them.

What you can test:
1) for each vertex of polygon1 if it is inside of polygon 2;
2) if at least one vertex is in polygon2, for each side of polygon1 if it
intersects with any side of polygon2.

At least one vertex inside and no intersection of sides means polygon1 is entirely
inside polygon2.

Thrse

Re:Polygon inside polygon


All you need to do is test the vertices of the polygon in the manner I noted... all
points not required... sorry for the confusion.

There is one test that needs to be made.  If a vertex of polygon2 falls onto a line
segment of polygon1, it needs to be decided if that is an in or out condition.

PS:  The dropping a line from the vertex to the x-axis works for all sorts of
polygons... occluded or concave sides, polygons with holes in them, and polygon areas
that are acutally multiple polygons... such as islands.

Quote
"Thrse Hanquet" wrote:
> Hi Sue,

> In general you only know the coordinates of the vertices, and it does not seem
> possible to compute the coordinates of "every point" of the polygon, as there is an
> infinite number of them.

> At least one vertex inside and no intersection of sides means polygon1 is entirely
> inside polygon2.

I would tend to agree.  I cannot think of a polygon shape where this would not be
true.  However, I would say that if one already has a generalized point in polygon
routine, then it is not necessary to have a specialized polygon in polygon routine.

Re:Polygon inside polygon


Hi Sue,

Quote
> There is one test that needs to be made.  If a vertex of polygon2 falls onto a
line
> segment of polygon1, it needs to be decided if that is an in or out condition.

It is not enough. Even if all vertices of polygon2 are in polygon1, there may
still be parts of polygon2 outside of polygon1 if polygon1 is concave.
For example think of a polygon with a shape of empty V. You may have a rectangle
with its right side inside the right branch of the V and its left side inside the
other branch, so all its vertices are inside, but still a part of its area may be
outside the shape of the V.

Quote
> PS:  The dropping a line from the vertex to the x-axis works for all sorts of
> polygons... occluded or concave sides, polygons with holes in them, and polygon
areas
> that are acutally multiple polygons... such as islands.

It is indeed what I used as basis for the PointInPolygon function I wrote a while
ago (available on efg's site), only the line is drawn horizontally, not
vertically.

Thrse

Re:Polygon inside polygon


Hi Sue,

Quote
> There is one test that needs to be made.  If a vertex of polygon2 falls onto a
line
> segment of polygon1, it needs to be decided if that is an in or out condition.

It is not enough. Even if all vertices of polygon2 are in polygon1, there may
still be parts of polygon2 outside of polygon1 if polygon1 is concave.
For example think of a polygon with a shape of empty V. You may have a rectangle
with its right side inside the right branch of the V and its left side inside the
other branch, so all its vertices are inside, but still a part of its area may be
outside the shape of the V.

Quote
> PS:  The dropping a line from the vertex to the x-axis works for all sorts of
> polygons... occluded or concave sides, polygons with holes in them, and polygon
areas
> that are acutally multiple polygons... such as islands.

It is indeed what I used as basis for the PointInPolygon function I wrote a while
ago (available on efg's site), only the line is drawn horizontally, not
vertically.

Thrse

P.S. Sorry if this is duplicated, at the moment my previous post seems lost.

Re:Polygon inside polygon


You are indeed correct.  A point test is insufficient
Quote
"Thrse Hanquet" wrote:
> Hi Sue,
> It is not enough. Even if all vertices of polygon2 are in polygon1, there may still
> be parts of polygon2 outside of polygon1 if polygon1 is concave. For example think
> of a polygon with a shape of empty V. You may have a rectangle with its right side
> inside the right branch of the V and its left side inside the other branch, so all
> its vertices are inside, but still a part of its area may be
> outside the shape of the V.

Re:Polygon inside polygon


Hi ,
   If you know OpenGL then you can you tesselator using AB_GEQ_TWO property
to determine if there is any int{*word*114} and it will return you triangles.

DPS

Quote
"Alex S" <graph_developm...@yahoo.com> wrote in message

news:3c51bfaa_2@dnews...
Quote
> Thanks for the answer.

> Is simply to check if one polygon intersects another polygon.

> What I want to know if Polygon2 is completely inside polygon1 (no
> intersection) or viceversa. Like the following (althoug these are
> rectangles):

> +-----------------------------+
> |                                             |
> |     +-------------+                |
> |      |                     |                |
> |      |                     |                |
> |      |                     |                |
> |      |                     |                |
> |     +-------------+                |
> |                                             |
> +----------------------------+

> Polygon clipping algorithms could be the sollution: If I obtain the
> intersection of Polygon2 and Polygon1 and the result is the same polygon2,
> then Polygon 2 is inside Polygon1 or viceversa

> ....but two poins against this:

>     - Very difficult to implement a polygon clipping algorithm.
>     - Very slow just to determine if polygon2 fully inside polygon1
(maybe).

> Any other solluion for this ?

> Thanks
> Alex

> "Jorge E. Perez" <jorg...@unm.edu> wrote in message

news:3c519c80_1@dnews...

- Show quoted text -

Quote
> > Check for line intersection.

> > The following page my give you the clues that you need. Pay spetial
> atention
> > to the notes at the end.

> > http://astronomy.swin.edu.au/pbourke/geometry/lineline2d/

> > Jorge

> > "Alex S" <graph_developm...@yahoo.com> wrote in message
> > news:3c50af73_1@dnews...
> > > Hi to all,

> > > How can I know if one polygon is inside another polygon ?

> > > type
> > >     TPoint2D = record
> > >         x,y:Double;
> > >     end;
> > > var
> > >     Polygon1: array[0..10] of TPoint2D;
> > >     Polygon2: array[0..5] of TPoint2D;

> > > begin
> > >    ... fill Polygon1 and Polygon2 here.

> > >    // Now...how to know if Polygon2 is inside Polygon1 ???

> > > ..

> > > If you test every point in Polygon2 against if that point is inside
> > Polygon1
> > > that does not work because some line in Polygon2 can intersect other
> line
> > in
> > > Polygon1.

> > > TIA
> > > Alex

Re:Polygon inside polygon


Hi,

Thanks to all for your help!

Quote
> Did you try the CombineRegion GDI call?
> http://msdn.microsoft.com/library/en-us/gdi/regions_7tf2.asp

Not possible because I use polygons with real world coordinates (doubles).

Quote
> At least one vertex inside and no intersection of sides means polygon1 is
entirely
> inside polygon2.

I think this will give correct results as you stated previously. I will test
intensively.

Thanks a lot.
Alex

Quote
"Thrse Hanquet" <therese.hanq...@skynet.be> wrote in message

news:3c51c39a_1@dnews...
Quote
> Hi Alex,

> > Polygon clipping algorithms could be the sollution: If I obtain the
> > intersection of Polygon2 and Polygon1 and the result is the same
polygon2,
> > then Polygon 2 is inside Polygon1 or viceversa

> > ....but two poins against this:

> >     - Very difficult to implement a polygon clipping algorithm.
> >     - Very slow just to determine if polygon2 fully inside polygon1
(maybe).

> Did you try the CombineRegion GDI call?
> http://msdn.microsoft.com/library/en-us/gdi/regions_7tf2.asp

> Thrse

Re:Polygon inside polygon


On Fri, 25 Jan 2002 13:12:35 -0600, "Sue D. Nom"

Quote
<su...@courthouse.com> wrote:
>If by "irregular polygons" you mean those that have inclusions, or concave
>sides, or that have donut holes in them, then the solution is simple.  For
>every point in polygon2, simply drop a line from the point to the x axis.  If
>the line from the point crosses lines in polygon1 an odd number of times then
>the point is in polygon1, if it crosses an even number of polygon1 lines, it
>must be outside of polygon1.  All you need is for one polygon2 point to fail
>this test to know that some part of it is outside polygon1.

     However, every point passing doesn't guarantee it's entirely
inside.  Consider:

    +++++++++++++++++++++
    +                *****                        +
    +                *     *                       +
    +       +++++++++++++++++
    +       +      *     *
    +       +      *     *
    +       +++++++++++++++++
    +               *     *                        +
    +               *****                         +
    +++++++++++++++++++++

      I hope that didn't get too mangled by fonts.

Other Threads