/* 2D Geometry Demonstration Program, version 1.00, created March 27, 1999.      */
/* Last modified March 27, 1999, by Rick Wagner.                                 */
/* Copyright 1999 by Rick Wagner, all rights reserved.                           */
/* Source code use with attribution for educational purposes only.               */
/* Created for use with Computer Science 101 at USC.                             */

#include <stdio.h>
#include <math.h>           /* For sqrt() and pow(). */
#include <conio.h>          /* For getch(). */

typedef struct              /* Structure to model a point in the plane. */
{
  float x;
  float y;
} Point2D;

typedef struct              /* Structure to model a line segment in the plane. */
{
  Point2D p1;
  Point2D p2;
} Edge2D;

typedef struct              /* Structure to model a polygon in the plane. */
{
  int iNumEdges;
  Edge2D EdgeArray[100];
} Polygon2D;

/* Function prototypes */
void about();
void definePolygons(Polygon2D* PgonA, Polygon2D* PgonB);
float distanceBetweenPoints(Point2D p1, Point2D p2);
float distanceBetweenPolygons(Polygon2D PgonA, Polygon2D PgonB);

void main()
{
  Polygon2D PgonA;                 /* A polygon. */
  Polygon2D PgonB;                 /* Another polygon */
  float sfDistance = 0;            /* Distance between the polygons. */
  char c = 0;

  about();
  definePolygons(&PgonA, &PgonB);  /* Define two polygons for later use. */

  sfDistance = distanceBetweenPolygons(PgonA, PgonB);
  printf("The distance between the square and the triangle is %.3f\n\n", sfDistance);
  printf("Hit any key to continue...");
  c = getch();
  printf("\n\n");
}

void about()
{
  puts("                      2D Geometry Demonstration Program");
  puts("");
  puts("                  Version 1.00 last modified March 27, 1999.");
  puts("             Copyright 1999 by Rick Wagner, all rights reserved.\n");
  puts("        Source code use with attribution for educational purposes only.");
  puts("              Created for use with Computer Science 101 at USC.\n\n");
}

void definePolygons(Polygon2D* PgonA, Polygon2D* PgonB)
{
  /* Define a triangle based at the origin: */
  PgonA -> iNumEdges = 3;

  PgonA->EdgeArray[0].p1.x = 0;  /* First edge of the triangle */
  PgonA->EdgeArray[0].p1.y = 0;
  PgonA->EdgeArray[0].p2.x = 4;
  PgonA->EdgeArray[0].p2.y = 0;

  PgonA->EdgeArray[1].p1.x = 4;  /* Second edge of the triangle */
  PgonA->EdgeArray[1].p1.y = 0;
  PgonA->EdgeArray[1].p2.x = 4;
  PgonA->EdgeArray[1].p2.y = 4;

  PgonA->EdgeArray[2].p1.x = 4;  /* Third edge of the triangle */
  PgonA->EdgeArray[2].p1.y = 4;
  PgonA->EdgeArray[2].p2.x = 0;
  PgonA->EdgeArray[2].p2.y = 0;

  /* Define a square: */
  PgonB -> iNumEdges = 4;

  PgonB->EdgeArray[0].p1.x = 5;  /* First edge of the square */
  PgonB->EdgeArray[0].p1.y = 5;
  PgonB->EdgeArray[0].p2.x = 8;
  PgonB->EdgeArray[0].p2.y = 5;

  PgonB->EdgeArray[1].p1.x = 8;  /* Second edge of the square */
  PgonB->EdgeArray[1].p1.y = 5;
  PgonB->EdgeArray[1].p2.x = 8;
  PgonB->EdgeArray[1].p2.y = 8;

  PgonB->EdgeArray[2].p1.x = 8;  /* Third edge of the square */
  PgonB->EdgeArray[2].p1.y = 8;
  PgonB->EdgeArray[2].p2.x = 5;
  PgonB->EdgeArray[2].p2.y = 8;

  PgonB->EdgeArray[3].p1.x = 5;  /* Fourth edge of the square */
  PgonB->EdgeArray[3].p1.y = 8;
  PgonB->EdgeArray[3].p2.x = 5;
  PgonB->EdgeArray[3].p2.y = 5;
}

/* Find the distance between two points: */
float distanceBetweenPoints(Point2D p1, Point2D p2)
{
  float sfD = 0;                     /* Distance, the return value. */
  float sfDSquared = 0;              /* Distance squared, an intermediate value. */

  /* Pythagorean theorem: */
  sfDSquared = (p2.x - p1.x) * (p2.x - p1.x) + (p2.y - p1.y) * (p2.y - p1.y);
  sfD = (float) sqrt((double) sfDSquared);

  return sfD;
}

/* Find the closest distance between two polygons: */
float distanceBetweenPolygons(Polygon2D PgonA, Polygon2D PgonB)
{
  float sfD = 0;                     /* Distance, the return value. */
  int i = 0;
  int j = 0;
  float sfTempDistance;              /* Temporary distance for comparison. */

  sfD = (float) pow(10, 30);         /* Set the distance to a really big number */

  /* Compare all points of PgonA against all points of PgonB. */
  for (i = 0; i < PgonA.iNumEdges; i++)
  {
    for (j = 0; j < PgonB.iNumEdges; j++)
    {
      /* Check all four combinations of pairs of points between the two edges: */
      sfTempDistance = distanceBetweenPoints(PgonA.EdgeArray[i].p1, PgonB.EdgeArray[j].p1);
      if (sfTempDistance < sfD) sfD = sfTempDistance;
      sfTempDistance = distanceBetweenPoints(PgonA.EdgeArray[i].p1, PgonB.EdgeArray[j].p2);
      if (sfTempDistance < sfD) sfD = sfTempDistance;
      sfTempDistance = distanceBetweenPoints(PgonA.EdgeArray[i].p2, PgonB.EdgeArray[j].p1);
      if (sfTempDistance < sfD) sfD = sfTempDistance;
      sfTempDistance = distanceBetweenPoints(PgonA.EdgeArray[i].p2, PgonB.EdgeArray[j].p2);
      if (sfTempDistance < sfD) sfD = sfTempDistance;
    }
  }
  return sfD;
}