/****************************************************************
 *								*
 *	Douglas - Peucker Line Simplification Algorithm.	*
 *								*
 ****************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <errno.h>

#define MAXPOINTS 10000

struct dppoint {
    float x;
    float y;
} pts[MAXPOINTS], simp[MAXPOINTS];

int n, simpptr;

float e;  /*  Точность приближения линии. */

void dpbase (int i, int j)
{
    float maxdist = 0, tmpdist;
    int k, f;
    
    for (k = i+1; k < j; k++)
    {
	/*  Вычислить расстояние от k-той точки до прямой ij. */
	tmpdist = (pts[j].x*pts[k].y + pts[i].x*pts[j].y + pts[k].x*pts[i].y - pts[j].x*pts[i].y - pts[i].x*pts[k].y - pts[k].x*pts[j].y) / sqrt ((pts[i].x-pts[j].x)*(pts[i].x-pts[j].x) + (pts[i].y-pts[j].y)*(pts[i].y-pts[j].y));
	
	if (tmpdist < 0) tmpdist = -tmpdist;  /*  Модуль расстояния. */
	
	if (tmpdist > maxdist)   /*  Если на данный момент k-тая точка  */
	{			 /*    является  самой  удаленной,  то  */
	    maxdist = tmpdist;	 /*    запомнить ее расстояние и номер. */
	    f = k;
	}
    }
    
    if (maxdist > e)	/*  Если самая удаленная точка находится на  */
    {			/*    расстоянии, превышающем заданную точ-  */
	dpbase (i, f);	/*    ность приближения, то разбить ломаную  */
	dpbase (f, j);	/*    в этой точке  и  рекурсивно упростить  */
    }			/*    две части.  			     */
    else
	simp[simpptr++] = pts[i];  /*  Иначе - запомнить  i-тую точку. */
}


void readfile (FILE *f)
{    
    /*  Выполнять, пока не встречен конец файла. */
    while (!feof (f))
    {
	simpptr = 0;
	
	/*  Считать из файла n-ную точку. */
	fscanf (f, "%f %f\n", &pts[n].x, &pts[n].y);
	
	/*  Выполнить упрощение линии по алгоритму Дугласа-Пекера. */
	dpbase (0, n);	
	
	if (n > 0)
	    simp[simpptr] = pts[n];

	n++;
    }
}


void writefile (FILE *f)
{
    int i;
    
    /*  Вывести точки в файл. */
    for (i = 0; i <= simpptr; i++)
	fprintf (f,"%f %f\n", simp[i].x, simp[i].y);
}


int main (int argc, char *argv[])
{
    FILE *fin, *fout; /* Входной и выходной файлы. */

    /*  Если в командной строке не введено имя входного файла,
	имя выходного файла, точность приближения или введено
	что-нибудь лишнее то написать сообщенине. */
    if (argc != 4)
    {
	printf ("Usage: %s in_file out_file dist\n", argv[0]);
	exit (-1);
    }
    
    /*  Открыть входной файл для чтения. */
    if ((fin = fopen (argv[1], "r")) == NULL)
    {
	printf ("%s: %s: %s\n", argv[0], argv[1], strerror (errno));
	exit (-1);
    }
    
    /*  Открыть выходной файл для записи. */
    if ((fout = fopen (argv[2], "w")) == NULL)
    {
	printf ("%s: %s: %s\n", argv[0], argv[2], strerror (errno));
	fclose (fin);
	exit (-1);
    }

    /*  Запомнить точность приближения. */
    e = atof (argv[3]);
    
    n = 0;
    
    /*  Выполнить чтение из входного файла с применением
	алгоритма Дугласа-Пекера. */
    readfile (fin);
    
    /*  Записать полученные точки в выходной файл. */
    writefile (fout);
    
    /*  Закрыть оба файла. */
    fclose (fin);
    fclose (fout);
    
    exit (0);
}