Thread: How to decide if four lines form a square?

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!

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;
}

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

¤------¤
 \    /
  \  /
   \/
   /\
  /  \
 /    \
¤------¤

¤
|\
| \
|  ¤
|   \
|    \
¤-----¤

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: [email protected] 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)

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