Thread: 2 overlapping polygons (not sure if this is college level math, but...)

What I'm trying to find - On a normal X, Y coordinate plane, I'm trying to find a formula or group of formulas to find at which point two polygons overlap. The main problem with this is that this includes irregular polygons of any varying amount of sides. All I really know are the points and their order.

Why - I'm trying to implement color into a 3d true basic program. For anyone who hasn't worked with true basic, it doesn't understand depth. (I'll point out at this point that I know there's a download to add that to it, but I'm trying to see if I can do this anyway. Besides, I don't think my school is going to let me install the extras for that.) All and all, I've got wire frame support set up, and it works fairly well. But since it doesn't know depth, if I were to add color to it, I'd need a way to order what I'm drawing. Otherwise, something in back of something else could be drawn on top of it. So, I figure that I could check each group of polygons to figure out if they're overlapping. If they are, the I just pick a point that they have in common, find the placement on the z-axis, and it's all fairly simple from there. (Side Note: The z-axis is something that I have it change in the background, but it doesn't know what to do with it plot-wise)

So there's my problem. I'm not sure if this is really college level math, but I'm guessing it is. I'm in high school right now, and I've yet to find a teacher who knows how to do this.

Thanks for the help.

PS - If you have True basic, and would like to see the programs, I could send them to you. But they're a bit of a mess right now. (haven't cleaned them up code-wise)

Are your polygons all convex? If so, then they overlap if and only if there's a vertex of one inside the other. Now 'all' you need is a way to determine whether a point is inside a polygon.

Well, to answer you question, yes, they're all convex. (I needed that setup for a different problem)

But as for it only overlapping if a vertex of one is in the other, that's not always true. Consider this setup of the attached file. Both are convex, and overlap, but none of the vertexes are within the other polygon.

Either way, thanks for the help. I've been going at this one for a while now, and it's nice to have people helping out.

Oops!

I was just thinking... perhaps there is something that can be done with the various y<mx+b equations that each would have? I'm to tired right now to think about it, plus I've got school in about an hour, but it seems like it would be a good place to start.

Also, don't feel bad about making that mistake. I thought for a good while that it could be done by finding where the lines intersect until I realized one could be inside the other.

Take a look a quick-hull, implemented as a java applet here and available as a standalone program here. You'll also find more information on each of these site.

This looks like it could be what I'm looking for, though, again, I posting before school, and am a bit to tired to figure out exactly how to implement it for what I need.

Thanks for pointing that out.

It might also be possible to check whether the edges of the polygons intersect; that only happens if the polygons overlap.