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

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 ;-)

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

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.

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

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

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

7. How to check system whether support texture correction

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

4 post • Page:**1** of **1**