homeGeek CultureWebstoreeCards!Forums!Joy of Tech!AY2K!webcam

The Geek Culture Forums


Post New Topic  New Poll  Post A Reply
my profile | directory login | | search | faq | forum home
  next oldest topic   next newest topic
» The Geek Culture Forums   » Techno-Talking   » Math-a-holics and Code Junkies   » Triangle

 - UBBFriend: Email this page to someone!    
Author Topic: Triangle
Number 2608
Mini Geek
Member # 2608

Rate Member
Icon 1 posted June 02, 2004 09:37      Profile for Number 2608     Send New Private Message       Edit/Delete Post   Reply With Quote 
OK, it is one of those days where I really have nothing better to think about, but I can't come up with a decent solution for this:

A triangle, rather unsuprisingly, has 3 corners at coordinates P, Q and R. Determine if point S lies within the triangle.

Suggestions??

Posts: 82 | From: Leeds, UK | Registered: Mar 2004  |  IP: Logged
dragonman97

SuperFan!
Member # 780

Member Rated:
4
Icon 1 posted June 02, 2004 10:01      Profile for dragonman97   Author's Homepage     Send New Private Message       Edit/Delete Post   Reply With Quote 
Insignificant information.

--------------------
There are three things you can be sure of in life: Death, taxes, and reading about fake illnesses online...

Posts: 9331 | From: Westchester County, New York | Registered: May 2001  |  IP: Logged
Doco

SuperFan!
Member # 371

Member Rated:
5
Icon 1 posted June 02, 2004 10:12      Profile for Doco   Author's Homepage     Send New Private Message       Edit/Delete Post   Reply With Quote 
The general form of finding if a point is inside a polygon is to draw a ray from the point to infinity in any direction and count how many edges it crosses. If it crosses an odd number it is inside the poly and if it crosses an even number it is outside the polygon.

A triangle is just a simplified version of this.

Try this URL http://www.ics.uci.edu/~eppstein/161/960307.html

Posts: 419 | From: Minneapolis, MN | Registered: Mar 2000  |  IP: Logged
TMBWITW,PB

Member # 1734

Member Rated:
5
Icon 1 posted June 02, 2004 10:47      Profile for TMBWITW,PB     Send New Private Message       Edit/Delete Post   Reply With Quote 
quote:
Originally posted by dragonman97:
Insignificant information.

D-man must still be recovering. If he meant what I think, then I would have to agree that there is insufficient information. [Wink]

--------------------
"Beauty is in the eye of the beholder and it may be necessary from time to time to give a stupid or misinformed beholder a black eye."
óMiss Piggy

Posts: 4010 | From: my couch | Registered: Oct 2002  |  IP: Logged
dragonman97

SuperFan!
Member # 780

Member Rated:
4
Icon 1 posted June 02, 2004 10:51      Profile for dragonman97   Author's Homepage     Send New Private Message       Edit/Delete Post   Reply With Quote 
quote:
Originally posted by TMBWITW,PB:
quote:
Originally posted by dragonman97:
Insignificant information.

D-man must still be recovering. If he meant what I think, then I would have to agree that there is insufficient information. [Wink]
You got it, Peebs - I'm knocked out, damn cold is killing me. And I'm not as strong at this kind of math stuff, so I see my answer was kind of weak. *shrug*

*coughs, weezes, and collapses...into his swivel chair at work :-/*

--------------------
There are three things you can be sure of in life: Death, taxes, and reading about fake illnesses online...

Posts: 9331 | From: Westchester County, New York | Registered: May 2001  |  IP: Logged
Stereo

Solid Nitrozanium SuperFan!
Member # 748

Member Rated:
5
Icon 3 posted June 02, 2004 11:19      Profile for Stereo     Send New Private Message       Edit/Delete Post   Reply With Quote 
Another way that doesn't require drawing, would be to calculate the triangle's area, replace one corner by the point, calculate the new area, then do it again for the two other corners.

If the sum of the three areas using the point instead of a corners is greater than the real triangle's area, the point is outside the triangle.

In other words:
code:
 
if area(PQR) < area(PQS)+area(PSR)+area(SQR) then
inside(s, PQR) = false
else
inside(s, PQR) = true

I don't know for sure wich one would be faster to calculate, in CPU usage terms (between this one and the number of edges counting one). I don't even know if this solution is the kind you are looking for. Anyway, have fun.

(I wonder how many other ways to solve the problem exists...)

edit:

I believe this solution can be extended to other polygons too. Replace the condition with:

code:
 area(poly)*(num_edges-2) < sum(area(poly')) 

An equivalent solution should also be possible for volumes, but that's a gut feeling only.

--------------------
Eppur, si muove!

Galileo Galilei

Posts: 2289 | From: Gatineau, Quebec, Canada | Registered: Apr 2001  |  IP: Logged
ooby
Highlie
Member # 2603

Member Rated:
4
Icon 1 posted June 02, 2004 11:21      Profile for ooby     Send New Private Message       Edit/Delete Post   Reply With Quote 
Just thinking out loud....
if S is within triangle PQR then
|pq x pr| = |ps x rs| + |rs x qs|
if S is not within triangle PQR, then |pq x pr| < |ps x rs| + |rs x qs|
That is, assuming |pq x pr| . |ps x rs| = 0 (i.e. P, Q, R, and S are coplanar)

--------------------
"haven't you ever wondered if there's more to life than being really, really, rediculously good looking?"

Posts: 680 | From: South Jersey | Registered: Feb 2004  |  IP: Logged
ooby
Highlie
Member # 2603

Member Rated:
4
Icon 1 posted June 02, 2004 13:58      Profile for ooby     Send New Private Message       Edit/Delete Post   Reply With Quote 
oops.. thats |pq x pr| >= |ps x rs| + |rs x qs|

I thought it looked funny.

--------------------
"haven't you ever wondered if there's more to life than being really, really, rediculously good looking?"

Posts: 680 | From: South Jersey | Registered: Feb 2004  |  IP: Logged
Callipygous
BlabberMouth, a Blabber Odyssey
Member # 2071

Member Rated:
4
Icon 1 posted June 02, 2004 17:00      Profile for Callipygous     Send New Private Message       Edit/Delete Post   Reply With Quote 
1. Look at triangle

2. See if point S is inside it.

3. Done.

and I thought mathematicians were supposed to be the clever ones....

--------------------
"Knowledge is Power. France is Bacon" - Milton

Posts: 2922 | From: Brighton - UK | Registered: Mar 2003  |  IP: Logged
Number 2608
Mini Geek
Member # 2608

Rate Member
Icon 1 posted June 04, 2004 04:14      Profile for Number 2608     Send New Private Message       Edit/Delete Post   Reply With Quote 
Thanks for your answers.

Sorry if anyone thought my original question was a little vague on details. I deliberately left it very general in order to get general answers. Either that or I was too lazy to fully specify the problem.

Posts: 82 | From: Leeds, UK | Registered: Mar 2004  |  IP: Logged
The Famous Druid

Gold Hearted SuperFan!
Member # 1769

Member Rated:
4
Icon 1 posted June 04, 2004 05:01      Profile for The Famous Druid     Send New Private Message       Edit/Delete Post   Reply With Quote 
I was going to describe a complicated, messy solution, but I much prefer the one Stereo suggested, very neat. [thumbsup]

However...

quote:
Originally posted by Stereo:
I believe this solution can be extended to other polygons too. Replace the condition with:

code:
 area(poly)*(num_edges-2) < sum(area(poly')) 


I'm not convinced that will work for all polygons. Specifically, polygons which have hollows in them (for example, a doughnut-shape, or an 'E' shape) probably wouldn't work, but I'd have to spend some time drawing little pictures to be sure.

--------------------
If you watch 'The History Of NASA' backwards, it's about a space agency that has no manned spaceflight capability, then does low-orbit flights, then lands on the Moon.

Posts: 10669 | From: Melbourne, Australia | Registered: Oct 2002  |  IP: Logged
ooby
Highlie
Member # 2603

Member Rated:
4
Icon 1 posted June 04, 2004 05:09      Profile for ooby     Send New Private Message       Edit/Delete Post   Reply With Quote 
tfd's and my answers are the same. I just got used to calculating everything using vectors. I had to prove sooooo many things in multivariable calc.

Anyway, if you cross multiply two vectors, you get a vector that is equal to the area of the triangle in the direction that is normal to the plane of the vectors.

--------------------
"haven't you ever wondered if there's more to life than being really, really, rediculously good looking?"

Posts: 680 | From: South Jersey | Registered: Feb 2004  |  IP: Logged
The Famous Druid

Gold Hearted SuperFan!
Member # 1769

Member Rated:
4
Icon 1 posted June 04, 2004 05:12      Profile for The Famous Druid     Send New Private Message       Edit/Delete Post   Reply With Quote 
quote:
Originally posted by ooby:
tfd's and my answers are the same.

Did I post an answer?????
Methinks you mean Stereos answer.

--------------------
If you watch 'The History Of NASA' backwards, it's about a space agency that has no manned spaceflight capability, then does low-orbit flights, then lands on the Moon.

Posts: 10669 | From: Melbourne, Australia | Registered: Oct 2002  |  IP: Logged
quantumfluff
BlabberMouth, a Blabber Odyssey
Member # 450

Member Rated:
5
Icon 1 posted June 04, 2004 06:43      Profile for quantumfluff     Send New Private Message       Edit/Delete Post   Reply With Quote 
What about computing the angles PSQ, QSR and RSP and adding them together. If they equal 360, then it's inside the triangle, otherwise outside. The area calculation is probably simpler, however.
Posts: 2901 | From: 5 to 15 meters above sea level | Registered: Jun 2000  |  IP: Logged
Drazgal
Geek
Member # 984

Member Rated:
5
Icon 1 posted June 04, 2004 08:25      Profile for Drazgal   Author's Homepage     Send New Private Message       Edit/Delete Post   Reply With Quote 
Heres a discussion we had on this in the graphics programming forum on gamedev.net. Includes code for the solution.
Posts: 154 | From: Dundee, United Kingdom | Registered: Nov 2001  |  IP: Logged


All times are Eastern Time  
Post New Topic  New Poll  Post A Reply Close Topic    Move Topic    Delete Topic next oldest topic   next newest topic
 - Printer-friendly view of this topic
Hop To:

Contact Us | Geek Culture Home Page

© 2015 Geek Culture

Powered by Infopop Corporation
UBB.classicTM 6.4.0



homeGeek CultureWebstoreeCards!Forums!Joy of Tech!AY2K!webcam