About
Community
News of the Temple
Community Bulletin Board
Chat
Meet Up
Bad Ideas
Drugs
Ego
Erotica
Fringe
Society
Technology
register | bbs | search | rss | faq | about
meet up | add to del.icio.us | digg it

Go Back   Community > Sciences > Mad Scientists

Mad Scientists Science and Mathematics discussion-- theories, arguments, citations, proofs and pudding.

Reply
 
Thread Tools Display Modes
  #1   Add pianoSpleen to your ignore list  
Old 2007-06-08, 08:47
pianoSpleen pianoSpleen is offline
Regular
 
RIGHT BEHIND YOU. pianoSpleen is helpful
Default Intersection of two quads

This has been driving me nuts and nobody I know seems to have any idea how to do it...

Does anyone here happen to know how to calculate the area of intersection of two quadrilaterals?

My first thought would be to find the intersections of their bounds and create a <=8-sided shape, then split that into triangles and calculate and sum their areas. Which would probably be really, really inefficient. I'd really like it if anyone happened to know of a more efficient answer.
Reply With Quote
  #2   Add tricky to your ignore list  
Old 2007-06-08, 09:34
tricky tricky is offline
Regular
 
Australia tricky is helpful
Default Re: Intersection of two quads

The 2 squares overlap. You get a 3rd square. Calculate its area. Done.
Reply With Quote
  #3   Add pianoSpleen to your ignore list  
Old 2007-06-08, 09:34
pianoSpleen pianoSpleen is offline
Regular
 
RIGHT BEHIND YOU. pianoSpleen is helpful
Default Re: Intersection of two quads

Quote:
Originally Posted by tricky View Post
The 2 squares overlap. You get a 3rd square. Calculate its area. Done.
Quadrilaterals, not squares.
Reply With Quote
  #4   Add xXPhoenixFireXx to your ignore list  
Old 2007-06-08, 13:44
xXPhoenixFireXx xXPhoenixFireXx is offline
Regular
 
North Charleston xXPhoenixFireXx is an unknown
Default Re: Intersection of two quads

I wouldn't worry too much about inefficiency, dividing the area of intersection into triangles and using heron's formula is probably the easiest way.

And with 2 quads the resulting shape is guaranteed to be convex which is really handy assuuming this problem is given in a CS context.

Thing is the area of a traingle can be a function of the length of the sides only, however with 4 or more sides angles need to be taken into account.
Reply With Quote
  #5   Add pianoSpleen to your ignore list  
Old 2007-06-09, 01:40
pianoSpleen pianoSpleen is offline
Regular
 
RIGHT BEHIND YOU. pianoSpleen is helpful
Default Re: Intersection of two quads

Dang. The intersection + area calculation will have to take an awful lot of optimising, and it'll have to happen on a pixel shader which makes things pretty slow... :/

Thanks though!
Reply With Quote
  #6   Add lifejunkie to your ignore list  
Old 2007-06-10, 07:54
lifejunkie lifejunkie is offline
Moderator
 
A dream within a dream. Send a message via ICQ to lifejunkie lifejunkie is helpful lifejunkie is helpful lifejunkie is helpful lifejunkie is helpful
Default Re: Intersection of two quads

Quote:
Originally Posted by pianoSpleen View Post
Dang. The intersection + area calculation will have to take an awful lot of optimising, and it'll have to happen on a pixel shader which makes things pretty slow... :/

Thanks though!
What exactly are you trying yo do?

Might be a more efficient way.
Reply With Quote
  #7   Add pianoSpleen to your ignore list  
Old 2007-06-10, 08:04
pianoSpleen pianoSpleen is offline
Regular
 
RIGHT BEHIND YOU. pianoSpleen is helpful
Default Re: Intersection of two quads

Quote:
Originally Posted by lifejunkie View Post
What exactly are you trying yo do?

Might be a more efficient way.
Short version: using polygons as light sources. Rather than rendering the entire scene again for each pixel like radiosity does, I was thinking we can just collide any likely faces with the lightsource to calculate how much of it is visible, then multiply by the normal factors (direction, distance, brightness, etc).

In this case we can consider 3-4 faces against one, which is vastly faster than repeatedly drawing the scene or doing a raytrace. Similarly, in theory with a faster system it could allow for realtime global illumination.

In 2D it's trivially easy/fast:
http://img177.imageshack.us/img177/5904/nonpointlg6.png
because we can just do a little bit of trig to calculate how much of the face is visible. In 3D it's a completely different story, as far as I can tell.

You'd have to project the faces into 2D, then work out how much of which is visible to get your brightness percentage.
Reply With Quote
  #8   Add yixil to your ignore list  
Old 2007-06-14, 01:47
yixil yixil is offline
Regular
 
Houston, Texas/Cornell U Send a message via AIM to yixil yixil is helpful
Default Re: Intersection of two quads

Quote:
Originally Posted by pianoSpleen View Post
You'd have to project the faces into 2D, then work out how much of which is visible to get your brightness percentage.
I might be talking out of my ass since I've forgotten a fair amount of multivariable, but I'm pretty sure Green's Theorem lets you project complex shapes onto any plane you choose.
Reply With Quote
  #9   Add pianoSpleen to your ignore list  
Old 2007-06-14, 04:08
pianoSpleen pianoSpleen is offline
Regular
 
RIGHT BEHIND YOU. pianoSpleen is helpful
Default Re: Intersection of two quads

Quote:
Originally Posted by yixil View Post
I might be talking out of my ass since I've forgotten a fair amount of multivariable, but I'm pretty sure Green's Theorem lets you project complex shapes onto any plane you choose.
Oh, I'm sure it does. The projection is the easy bit.
Reply With Quote
  #10   Add Sentinel to your ignore list  
Old 2007-06-14, 17:31
Sentinel Sentinel is offline
Regular
 
Planet Earth Sentinel is an unknown
Default Re: Intersection of two quads

http://en.wikipedia.org/wiki/Bretschneider%27s_formula

that might work? I'm not exactly sure what you're trying to do here.
Reply With Quote
Reply


Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is Off
HTML code is Off
Forum Jump


All times are GMT. The time now is 21:00.


 

 

totse.com certificate signatures
 
 
About | Advertise | Bad Ideas | Community | Contact Us | Copyright Policy | Drugs | Ego | Erotica
FAQ | Fringe | Link to totse.com | Search | Society | Submissions | Technology
Hot Topics
What am I doing wrong?
Compaq laptop goes blank on boot? Ubuntu 7.04
Debian Wireless
Torrents on linux?
Another noob can't connect to the net....
So tell me again...why use a *NIX?
Making my backspace key work...
ubuntu problem switching resolution
 
Sponsored Links
 
Ads presented by the
AdBrite Ad Network

 

TSHIRT HELL T-SHIRTS