How to decide if four lines form a square?

This is a discussion on How to decide if four lines form a square? within the C++ Programming forums, part of the General Programming Boards category; OK, here's my problem: I have a class TLine that is defined as follows: Code: class TLine { public: /* ...

  1. #1
    Registered User
    Join Date
    Mar 2002
    Location
    South Africa
    Posts
    35

    How to decide if four lines form a square?

    OK, here's my problem: I have a class TLine that is defined as follows:
    Code:
    class TLine
    {
    public:
      /*
      .
      .
      .
      */
    private:
      TPoint P1, P2;
    };
    it isn't everything, but thats the essentials. A TPoint is defined as follows:
    Code:
     

  2. #2
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Check if the points of the different lines equals, so that a square is formed.

    Ie: Check if one point of the line L1 matches any of the other lines (L2-L4).
    If it do, check if that line's (L2) second point matches any of the remaining lines (L3-L4).
    If it do, check if that line's (L3) second point matches the remaining lines (L4) points.
    If it do, check if L4's second point matches L1's first point.

    I suggest parting up this problem in smaller pieces, like:

    Point CheckIfPointEqualsAnyOfLinesPoints(Point P, Line L);
    bool IsThePointItsFirstOrSecondPoint(PointP, Line L);

    ...or whatever!
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  3. #3
    Registered User
    Join Date
    Mar 2002
    Location
    South Africa
    Posts
    35
    Thanx for the help - and yes, sorry about the missing part - but I see you got the gist of it! :-).

    Anyways, what I really wanted to know: Isn't there a simpler (i.e. shorter, perhaps iterative?) way of doing it?
    Its simple enough to put the four lines in an array. But when I do that, I find it necessary to work with vectors and dot products, and the code just keeps on becoming longer!

    However, I think that the points approach is probably best.
    Going to be one hell of an if statement!

  4. #4
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    You simply need two nested for-loops. Take a look a this code:
    (Why would I write all this, you ask? Well, sometimes it's really fun to solve mathematical problems... Am I sick? )

    <edit>
    I'm using conio.h for getch(). If you don't use Borland, simply remove those two lines
    </edit>

    Code:
    #include <iostream.h>
    #include <conio.h>
    
    #define NO_POINT     0
    #define FIRST_POINT  1
    #define SECOND_POINT 2
    
    #define SQUARE       true
    #define NOT_SQUARE   false
    
    
    //+-----------------------------------------------------------------------------
    //| Point structure, a point is defined as a coordinate (In a 2D room)
    //+-----------------------------------------------------------------------------
    typedef struct
    {
       int Xpos;
       int Ypos;
    }POINT;
    
    
    //+-----------------------------------------------------------------------------
    //| Line structure, a line is defined as two points
    //+-----------------------------------------------------------------------------
    typedef struct
    {
       POINT Point1;
       POINT Point2;
    }LINE;
    
    
    //+-----------------------------------------------------------------------------
    //| Overloads the == operator, to easily check if two point are the same
    //+-----------------------------------------------------------------------------
    bool operator ==(POINT P1, POINT P2)
    {
       return ((P1.Xpos == P2.Xpos) && (P1.Ypos == P2.Ypos));
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Creates a point out of 2 integers (X and Y)
    //+-----------------------------------------------------------------------------
    POINT CreatePoint(int X, int Y)
    {
       POINT TempPoint;
       TempPoint.Xpos = X;
       TempPoint.Ypos = Y;
       return TempPoint;
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Creates a line out of 2 points
    //+-----------------------------------------------------------------------------
    LINE CreateLine(POINT P1, POINT P2)
    {
       LINE TempLine;
       TempLine.Point1 = P1;
       TempLine.Point2 = P2;
       return TempLine;
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Checks if a point belong to a line, and which position it has
    //+-----------------------------------------------------------------------------
    int PointInLinePosition(POINT P, LINE L)
    {
       if(P == L.Point1) return FIRST_POINT;
       else if(P == L.Point2) return SECOND_POINT;
       else return NO_POINT;
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Returns a specific point in a line
    //+-----------------------------------------------------------------------------
    POINT GetPointInLine(LINE L, int Position)
    {
       if(Position == FIRST_POINT) return L.Point1;
       else return L.Point2;
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Returns the other point position in a line
    //+-----------------------------------------------------------------------------
    int GetOtherPosition(int Pos)
    {
       if(Pos == FIRST_POINT) return SECOND_POINT;
       else if(Pos == SECOND_POINT) return FIRST_POINT;
       else return NO_POINT;
    }
    
    
    //+-----------------------------------------------------------------------------
    //| Main function
    //+-----------------------------------------------------------------------------
    int main()
    {
       //A square consists of 4 lines
       LINE Square[4];
    
       //Creates a valid square
       Square[0] = CreateLine(CreatePoint(3, 3), CreatePoint(12, 3));
       Square[1] = CreateLine(CreatePoint(12, 3), CreatePoint(12, 12));
       Square[2] = CreateLine(CreatePoint(12, 12), CreatePoint(3, 12));
       Square[3] = CreateLine(CreatePoint(3, 12), CreatePoint(3, 3));
    
       //Stores if a certain line has been checked
       bool LineChecked[4] = {true, false, false, false};
       bool Result = SQUARE;
       int LastPointPosition;
       POINT LastPoint;
    
    
       //Check if the first three connections are correct
       LastPoint = GetPointInLine(Square[0], FIRST_POINT);
       for(int LoopThreeTimes = 0; LoopThreeTimes < 3; LoopThreeTimes++)
       {
          for(int i = 0; i < 4; i++)
          {
             //Only check with the lines not already checked
             if(LineChecked[i] == false)
             {
                //Try to find a matching point in the line
                LastPointPosition = PointInLinePosition(LastPoint, Square[i]);
                if(LastPointPosition != NO_POINT)
                {
                   //Mark this line as checked, since we got a match
                   LineChecked[i] = true;
                   LastPoint = GetPointInLine(Square[i], GetOtherPosition(LastPointPosition));
                   i = 4;
                }
                else
                {
                    //If you reached the last element without a match, it can't be a square
                	if(i == 3) Result = NOT_SQUARE;
                }
             }
          }
       }
    
       //If the first three connections are correct, check if the fourth
       //is too (the last one, connected between the first and fourth).
       if(Result == SQUARE)
       {
          if(PointInLinePosition(LastPoint, Square[0]) == NO_POINT) Result = NOT_SQUARE;
       }
    
       //Print the results
       if(Result == SQUARE) cout << "The lines form a square!" << endl;
       else cout << "The lines does NOT form a square!" << endl;
       getch();
       return 0;
    }
    Last edited by Magos; 10-01-2002 at 08:49 AM.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  5. #5
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Note:

    My example just tests if the lines are ordered as a "circular list", so the shapes below will also count as a valid square. Didn't think of that when writing the example. Sorry!
    Code:
     = Point
    
    ------
     \    /
      \  /
       \/
       /\
      /  \
     /    \
    ------
    
    
    |\
    | \
    |  
    |   \
    |    \
    -----
    Last edited by Magos; 10-01-2002 at 09:30 AM.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  6. #6
    Registered User
    Join Date
    Mar 2002
    Location
    South Africa
    Posts
    35

    Oh thank you, thank you, thank you!

    The square problem is part of a larger system - you can be sure you will be credited! Seeing as how the system is object-oriented, I won't be using your code verbatim - but certainly I'll be using it!
    Email me here: moebius2day@yahoo.com if you want a copy of the program when it is finished :-)

    Thanks again.

    PS: Those shapes can be excluded with a little vector algebra (making the lines into vectors and taking their scalar products to determine if they are perpendicular or parallel)
    I code.
    I think.
    Ergo, I think in code.

  7. #7
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145

    Re: Oh thank you, thank you, thank you!

    PS: Those shapes can be excluded with a little vector algebra (making the lines into vectors and taking their scalar products to determine if they are perpendicular or parallel) [/B]
    True! Didn't think of that.
    So, you can use linear algebra for something useful after all
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. program to calculate the square root
    By saszew in forum C Programming
    Replies: 7
    Last Post: 10-28-2008, 12:53 PM
  2. Print out first N lines
    By YoYayYo in forum C Programming
    Replies: 1
    Last Post: 02-20-2008, 11:58 PM
  3. Clearing lines form a text file
    By Wiretron in forum C Programming
    Replies: 2
    Last Post: 12-28-2006, 01:24 PM
  4. My UserControls dissapear off my form
    By zMan in forum C# Programming
    Replies: 2
    Last Post: 09-15-2004, 08:55 AM
  5. Help with a bit of tweeking on form feed
    By breed in forum C Programming
    Replies: 5
    Last Post: 11-27-2001, 05:45 AM

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