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

• Sep 20th 2005, 02:15 AM
Dragon 2075
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. http://67.18.37.16/533/159/emo/ultra...aito-Smile.gif

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)
• Sep 20th 2005, 09:13 AM
rgep
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.
• Sep 20th 2005, 11:19 AM
Dragon 2075
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.
• Sep 20th 2005, 11:44 AM
rgep
Oops!
• Sep 22nd 2005, 01:44 AM
Dragon 2075
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.
• Sep 26th 2005, 07:38 AM
hpe
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.
• Sep 28th 2005, 02:11 AM
Dragon 2075
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.
• Nov 29th 2005, 01:17 AM
lewisje
It might also be possible to check whether the edges of the polygons intersect; that only happens if the polygons overlap.