Like Tree2Likes

triangle problem concept help

This is a discussion on triangle problem concept help within the C Programming forums, part of the General Programming Boards category; i need to do this program: enter the 3 co-ordinates of 2 triangles respectively and check if one of them ...

  1. #1
    Registered User
    Join Date
    Apr 2011
    Posts
    50
    i need to do this program: enter the 3 co-ordinates of 2 triangles respectively and check if one of them contains the other. i have been thinking of treating them as circles (finding the circumcircle)and check the required, but there are two problems:
    1> the triangles may not cut each other but the circum-circles may. so it is not the perfect way to solve.
    2> i even dont know how to find the circum-centre and circum-centre with the given data.
    any other idea about how to solve it or even solving problem 2> will be appreciated.
    i am just asking for the mathematical concept applicable here and not the code.

    plz plz someone help!!!!!!!
    Last edited by Abhas; 04-08-2011 at 10:10 PM.

  2. #2
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Contains? Or intersects?
    Hmmmm.
    Contains: check that each of the three vertices is inside other triangle. Then do similar check to see if triangle B may be in A instead.
    Intersects: check if any of the three lines intersects with any of the other triangle's three lines.

  3. #3
    Registered User
    Join Date
    Apr 2011
    Posts
    50
    ya, contains. but what can be the logic behind that check. give some hint.

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,832
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Apr 2011
    Posts
    50
    wow.. found it.. salem lots of thanks...
    this is the page if in any case someone needs Determining Whether A Point Is Inside A Complex Polygon
    solves much more complex problem than i require....

  6. #6
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    A lot of complicate solutions on-line. What if you calculate the angle from the questionable point to each of the three vertices. If the angles are all within a 180 degree swath then the point was outside. This should be all simplifiable by eliminating any arctan after optimization.

  7. #7
    Registered User
    Join Date
    Apr 2011
    Posts
    50
    I AM SORRY nonoob but i didnt get your point. can you please explain your point w.r.t to the picture attached. please mention the name of the angle when you are explaining.
    Attached Images Attached Images  

  8. #8
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Ok. In the first diagram, I would calculate angles from "o" to A, B, C. They would be something like 80 degrees, 220 degrees, and 300 degrees.
    If you subtract the lowest value 80 from each, you'd get 0, 140, and 220 respectively. The points are NOT all <= 180.

    Think of how you would tell if you stood in a large field. There are three posts around you. Are you inside or outside the triangle? If you are outside the triangle then all posts lie on one side of a straight line that intersects with your origin.

    This algorithm is just one I came up with. In its initial non-optimized phase you'd be calling atan2(). I haven't tried to clean it up by eliminating all trig and just ending up with vector math.
    Salem likes this.

  9. #9
    Registered User
    Join Date
    Apr 2011
    Posts
    50

    Question

    i still didnt get your point
    1.
    Ok. In the first diagram, I would calculate angles from "o" to A, B, C. They would be something like 80 degrees, 220 degrees, and 300 degrees.
    If you subtract the lowest value 80 from each, you'd get 0, 140, and 220 respectively. The points are NOT all <= 180.
    WHAN TWO ANGLES ARE 80,220 THE OTHER MUST BE 60 (SINCE SUM OF ALL ANGLES IS 360).
    IN THAT CASE IF WE SUBTRACT 60 FROM EACH THEY BECOME 0,20,160 AND NONE OF THEM ARE GREATER THAN 180 ie.they are all <=180.
    if u meant it for the picture in which the point is outside the triangle, look at fig.2 of the attachment. your theory is not always true. HERE ANGLE AOC IS SLIGHTLY GREATER THAN 180 AND SUBTRACTING THE LEAST ANGLE WILL MAKE IT <180.
    2.
    Think of how you would tell if you stood in a large field. There are three posts around you. Are you inside or outside the triangle? If you are outside the triangle then all posts lie on one side of a straight line that intersects with your origin.
    THIS IS ALSO NOT TRUE. SEE THE ATTACHMENT.FIG.1
    Attached Images Attached Images  

  10. #10
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    I'm not talking about sum of all angles of the triangle. I am talking about azimuth angle from "o" to each of the vertices.
    In Fig.1, from "o" angle B is approx. 20 degrees, angle C is 70 degrees, A is 80. All three points lie in a sector that's less that 180. That is, I don't have to turn myself any more than within a slice of 60 to view all points.

  11. #11
    Registered User
    Join Date
    Apr 2011
    Posts
    50
    o thats quiet clear now.

  12. #12
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    I just had a brainwave. Find area of triangles OAB, OBC, OCA. Is the sum of those triangles equal to area ABC or greater? If equal then the point O is inside.

  13. #13
    Registered User
    Join Date
    Nov 2010
    Location
    Long Beach, CA
    Posts
    5,676
    To follow that up nonoob, I found a cool method for calculating area of a triangle. I think it is some sort of variant on Heron's formula when you have vertex points instead of side lengths:

    Area= abs(x1*y2+x2*y3+x3*y1-x1*y3-x3*y2-x2*y1)/2 (from Point in triangle algorithm)

    Should be nice and speedy.
    stahta01 likes this.

  14. #14
    Registered User
    Join Date
    Sep 2008
    Location
    Toronto, Canada
    Posts
    1,832
    Yeah, that's the way to calculate area of any polygon: Polygon Area -- from Wolfram MathWorld
    Now to optimize using my untested brainwave algorithm...

  15. #15
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    I'm no mathematician, don't even play one on TV... but...

    Why would you not calculate the center point of each triangle and see if the center of one is inside the other?

    (Hope that's not too confusing...)

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Laptop Problem
    By Boomba in forum Tech Board
    Replies: 1
    Last Post: 03-07-2006, 06:24 PM
  2. Replies: 5
    Last Post: 11-07-2005, 11:34 PM
  3. loop problem
    By rhymewithnothin in forum C Programming
    Replies: 16
    Last Post: 09-24-2005, 02:06 PM
  4. searching problem
    By DaMenge in forum C Programming
    Replies: 9
    Last Post: 09-12-2005, 02:04 AM
  5. half ADT (nested struct) problem...
    By CyC|OpS in forum C Programming
    Replies: 1
    Last Post: 10-26-2002, 09:37 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21