checking whether a polygon contains another

checking whether a polygon contains another

Post by Chris Well » Mon, 17 May 1999 04:00:00



I have a closed polygon and I'd like to know if anyone knows of an
algorithim to check whether one polygon is "inside" another.

thanks,

chris

 
 
 

checking whether a polygon contains another

Post by Fabrice Triboi » Mon, 17 May 1999 04:00:00



> I have a closed polygon and I'd like to know if anyone knows of an
> algorithim to check whether one polygon is "inside" another.

> thanks,

> chris

  I guess it's in 2D...
  A theorem says : draw a half-line from your point and count the number
of intersection with the polygon. If it's odd, the point is inside, if
it's even, the point is outside.
  I don't have the source at hand, but the algorithm is quite simple.
The half-line is random, so we will use the half-line which start from
the point to test and go towards +X. Now, for each segment of your
polygon, you need to test if there is an intersection. Begin by testing
if the segment is entirely above or below the half-line; if yes, there
is no intersection, so go on to the next segment. Otherwise check if the
segment is entierly on left hand side of the point to test; if yes,
there is no intersection, so go on to the next segment. Otherwise, check
if the segment is entierly right hand side of the point to test; if yes,
there is an intersection, so increment your counter and go on to the
next segment. Otherwise, you have to calculate the intersection between
the segment and the half-line and check if it's right or left hand side
from the point to test, and increment or not the counter.
  With any figure, it may seem complicated... In fact only the final
step is necessary, but the previous ones are only tests and are not CPU
consuming and are indeed the most frequent cases.

  Hope it will help you. I can find some sources in C, just ask ;-)

 
 
 

checking whether a polygon contains another

Post by Matt McLellan » Mon, 17 May 1999 04:00:00




> > I have a closed polygon and I'd like to know if anyone knows of an
> > algorithim to check whether one polygon is "inside" another.

> > thanks,

> > chris

>   I guess it's in 2D...
>   A theorem says : draw a half-line from your point and count the number
> of intersection with the polygon. If it's odd, the point is inside, if
> it's even, the point is outside.

It seems you answered the wrong question.  However, it is easy to apply the
technique you mention to solve the problem he wants.  You have explained how to
test a point for inclusion in a polygon.  His problem is to find out if one
polygon (P1) is inside another (P2).    The obvious approach to solving his
problem is to pick an arbitrary point on P1 and test whether or not it is inside
P2, by the method you mention.  If it is, then you make sure that the two
polygons don't overlap.  The easiest way to test this is by comparing each edge
in P1 to each edge in P2, testing for intersection.  This is fairly slow,
though, and he may need something more sophisticated.
 
 
 

checking whether a polygon contains another

Post by Alan Murt » Tue, 25 May 1999 04:00:00





> > > I have a closed polygon and I'd like to know if anyone knows of an
> > > algorithim to check whether one polygon is "inside" another.

> > > thanks,

> > > chris

> >   I guess it's in 2D...
> >   A theorem says : draw a half-line from your point and count the number
> > of intersection with the polygon. If it's odd, the point is inside, if
> > it's even, the point is outside.

> It seems you answered the wrong question.  However, it is easy to apply the
> technique you mention to solve the problem he wants.  You have explained how to
> test a point for inclusion in a polygon.  His problem is to find out if one
> polygon (P1) is inside another (P2).    The obvious approach to solving his
> problem is to pick an arbitrary point on P1 and test whether or not it is inside
> P2, by the method you mention.  If it is, then you make sure that the two
> polygons don't overlap.  The easiest way to test this is by comparing each edge
> in P1 to each edge in P2, testing for intersection.  This is fairly slow,
> though, and he may need something more sophisticated.

You could use my polygon clipper:

  http://www.cs.man.ac.uk/aig/staff/alan/software/

If you compute the difference of polygons: A - B, and you get a
null polygon result, then A is completely inside B.

A and B can be have arbitrary shapes (concave, self intersecting, or
contain holes).

Alan.

 
 
 

1. Check a polygon whether it intersects or within another polygon

Hello,
       I am looking for an algorithm or source code that
compares two 2D polygons (A & B), to find out whether

1) polygon A is in within polygon B

2) polygon A is intersect with polygon B

3) both polygon A and B are separated polygons

The answer can be in a form of boolean, true or false for the
above conditions.

Actually I trying to find out which is the "outside" or
"inside" polygon. It maybe a little bit complicated since
it may involved bezier curves (all in 2D of course).

Anybody knows such algorithm ?

Thanks in advance.

Happy Millenium.

--
K.K.Chan

Sent via Deja.com http://www.deja.com/
Before you buy.

2. (08Aug94) comp.graphics Frequently Asked Questions (FAQ)

3. checking whether 2 2D polygons overlap

4. Texture binding

5. Checking whether a point is above or below a plane

6. Where is my mouse ?

7. How to check system whether support texture correction

8. Maya 1.5 for irix

9. Checking whether a point is visible or not

10. Just checking whether my Posting works

11. how do I check whether a timage has a bitmap

12. Whether a point is inside a regular polygon

13. Determining whether a point is in a polygon