Structured Data: Nesting Triangles(using structs and doing some geometric calculation

This is a discussion on Structured Data: Nesting Triangles(using structs and doing some geometric calculation within the C++ Programming forums, part of the General Programming Boards category; nestedTriangles.cpp description: The program takes as input a pair of triangles, specified be giving the coordinates of each trangle's vertices. ...

  1. #1
    Registered User
    Join Date
    Sep 2013
    Posts
    2

    Structured Data: Nesting Triangles(using structs and doing some geometric calculation

    nestedTriangles.cpp description:

    The program takes as input a pair of triangles, specified be giving the coordinates of each trangle's vertices. It then determines if either triangle is "nested" within the other, meaning that one triangle lies entirely within the interior of the other.



    Pseudocode:


    One triangle lies within another if and only if all three vertices of the first triangle lie within the interior of the second triangle.
    Suppose that we have a triangle with vertices A, B, and C, described by the coordinates (xA, yA), (xB, yB), and (xC, yC), respectively. The sides of the triangle are the line segments AB, BC, and CA.
    A line passing through two points (x1, y1) and (x2, y2) can be considered to be the set of points (x,y) satisfying the equation
    f(x,y) = 0
    where f(x,y) is given as
    f(x,y) = (x - x1) (y2 - y1) - (y - y1) (x2 - x1)
    One of the interesting things about that f(x,y) is that we can use it to determine which "side" of the line an abitrary point (x,y) is on:

    If f(x,y) = 0, the point is exactly on the line.
    All points for which f(x,y) > 0 are on one side of the line, and
    All points for which f(x,y) < 0 are on the other side
    So the problem of determining whether a point (x,y) is on the inside of a trangle can be checking the sign of f(x,y) for each of the three lines making up the triangle.
    A complicating factor is that we don't know, for any given triangle, whether those three signs should be all positive, all negative, or some mixture of the two.

    The centroid of a triangle can be computed as the "average" of the x and y coordinates of the vertices:
    xcen = (xA + xB + xC)/3
    ycen = (yA + yB + yC)/3
    This point (xcen, ycen) is definitely inside the trangle (unless the triangle is "degenerate" and has no interior points).



    The problem of determining whether (x,y) is on the inside of a triangle can therefore be resolved by checking to see if it is on the same side of each of the trangle's line segments as (xcen, ycen).



    What I need:


    I want to fill in the missing bodies for the functions eval and areOnSameSideOf, which manipulate line segments. I think calling eval from within areOnSameSideOf will simplify the implementation of the latter.

    Code:
    #include <iostream>
    
    using namespace std;
    
    /**
     * 2D Cartesian coordinates
     */
    struct Point {
      double x;
      double y;
    };
    
    
    /**
     * A simple triangle, modeled as a collection of 3 vertices
     */
    struct Triangle {
      Point vertices[3];
    };
    
    /**
     * A line segment, indicated by its two endpoints
     */
    //*** Insert your structure declaration here
    
    /**
     * Read a trangle from the input stream.
     *
     * A triangle is presented as a sequence of 6 floating point values,
     * each successive pair of numbers being the x,y coordinates of one vertex.
     *
     * @param t  the triangle being read in
     * @param in the input from which it should be read
     */
    void readTriangle (Triangle& t, istream& in)
    {
      for (int i = 0; i < 3; ++i)
        {
          double x, y;
          in >> x >> y;
          Point p = {x, y};
          t.vertices[i] = p;
        }
    }
    
    
    /**
     * Evaluate a point with respect to the equation defining the line
     * passing through a line segment.
     *
     *  A line is defined as the set of points satisfying f(x,y) = 0
     *  where f(x,y) is a function of the form ax + by + c. This function
     *  computes that f(x,y) for an arbitrary point, which might not be
     *  on that line.
     *
     * @param line a line segment
     * @param p a point at which we ant the line function evaluated
     * @return A value that is zero for points on the line, positive for all
     *          points on one side of the line, and negative for all points
     *          on the other side of the line.
     */
    double eval (LineSegment line, Point p)
    {
      //*** implement this function
    }
    
    
    
    
    /**
     * Check two points to see if they lie on the same side of a line
     *
     * @param p1 a point
     * @param p2 another point
     * @param line a line segment
     * @return true iff p1 and p2 are on the same side of the line
     *                  passing through the given line segment.
     *                  If either or both points lie exactly on the line,
     *                  return false.
     */
    bool areOnSameSideOf (Point p1, Point p2, LineSegment line)
    {
      //*** implement this function
    }
    
    /**
     * Check to see if a point lies on the interior of a triangle.
     *
     * @param p a point
     * @param t a triangle
     * @return true iff p lies in the interior of the trangle t
     */
    bool isWithin (Point p, Triangle t)
    {
      Point centroid = {0.0, 0.0};
      for (int i = 0; i < 3; ++i)
        {
          centroid.x += t.vertices[i].x;
          centroid.y += t.vertices[i].y;
          
        }
      centroid.x /= 3.0;
      centroid.y /= 3.0;
      
      for (int i = 0; i < 3; ++i)
        {
          LineSegment side = {t.vertices[i], t.vertices[(i+1)%3]};
          if (!areOnSameSideOf (p, centroid, side))
        return false;
        }
      return true;
    }
    
    /**
     * Check to see if one triangle lies entirely within the
     * interior of the other.
     *
     * @param outer
     * @param inner
     * @return true iff inner lies entirely within the interior of outer
     */
    bool contains (Triangle outer, Triangle inner)
    {
      for (int i = 0; i < 3; ++i)
        {
          if (!isWithin(inner.vertices[i], outer))
        return false;
        }
      return true;
    }
    
    /**
     * Check to see if either of two triangles is
     * entirely contained within the other.
     *
     * @param t1
     * @param t2
     */
    void checkForNesting (Triangle t1, Triangle t2)
    {
      if (contains(t1, t2) || contains(t2, t1))
        cout << "These triangles nest." << endl;
      else
        cout << "These triangles do not nest." << endl;
    }
    
    int main (int argc, char** argv)
    {
      cout << "Enter the x,y coordinates of three vertices of a triangle: " << flush;
      Triangle t1;
      readTriangle (t1, cin);
      cout << "Enter the x,y coordinates of three vertices of another triangle: " << flush;
      Triangle t2;
      readTriangle (t2, cin);
      checkForNesting (t1, t2);
    }
    Last edited by aharper; 09-08-2013 at 04:05 PM.

  2. #2
    11DE784A SirPrattlepod's Avatar
    Join Date
    Aug 2013
    Posts
    485
    Quote Originally Posted by aharper View Post

    What I need:


    I want to fill in the missing bodies for the functions eval and areOnSameSideOf, which manipulate line segments. I think calling eval from within areOnSameSideOf will simplify the implementation of the latter.
    That's not what you need. What you need to do is implement the pseudocode yourself. If you then encounter something that doesn't work you may also need to ask a specific question about the problem. I doubt that anyone will write it for you :/ Why should they?

  3. #3
    Registered User
    Join Date
    Sep 2013
    Posts
    2
    I'm getting there...I'm just desperate atm. I'll post further elaborations.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Geometric search/intersection problem
    By getsmart1 in forum Tech Board
    Replies: 9
    Last Post: 09-24-2012, 08:52 AM
  2. Arithmetic/Geometric/Harmonic
    By DJ_Steve in forum C Programming
    Replies: 12
    Last Post: 08-23-2009, 08:34 PM
  3. Program for average, geometric mean, harmonic mean
    By Northstar in forum C Programming
    Replies: 5
    Last Post: 11-07-2007, 10:33 AM
  4. Data structs and pointers
    By vegaaces in forum C Programming
    Replies: 2
    Last Post: 04-30-2005, 12:50 PM
  5. Geometric Libraries and Coordinate planes
    By Unregistered in forum Windows Programming
    Replies: 4
    Last Post: 11-11-2001, 01:46 PM

Tags for this Thread


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