#pragma warning disable 219
#define DEBUG


using System;
using System.Timers; 

using System.Data;
using System.Drawing;
using System.Windows.Forms; 
using System.Collections; 
using System.Collections.Specialized;
using System.Collections.Generic;

using System.Text.RegularExpressions; 
using System.IO;
using System.Threading;
using System.Globalization;

namespace ut
{
 public class geo    /// функции для работы с графикой


 {
                // see http://base.vingrad.ru/search.php?q=classify&x=17&y=8
   const string _nm = "geo";
   public enum   Position   { Left, Right, Ahead, Behind, Between, Begin, End };
   public enum   Edge   { Touching, Crossing, Inessential };
   public const double notLess  = 8.0;    /// to work less

   static public double len(Point a){    /// длина отрезка
     double  x= (double)a.X;
     double  y= (double)a.Y;
     return Math.Sqrt(x*x + y*y) ;
   } 

   static public double len(Point a, Point b){     /// длина отрезка
     return len ( new Point  (b.X - a.X, b.Y - a.Y) );
   } 

   static Point halfWay (Point a, Point b) {        /// точка на середине отрезка
     return new Point ((a.X + b.X)/2, (a.Y + b.Y)/2);
   }

   static Point stepLess (Point a, Point b, double step) {  /// маленький шаг от a к b
     Point ret = new Point ( b.X,  b.Y);
     while (step > notLess && len (a, ret ) > step)
        ret = halfWay(a, ret);
     return ret;
   }


               //http://algolist.manual.ru/maths/geom/datastruct.php
   static public Position classify(Point origin, Point bgn, Point end){ /// расположение точки относительно отрезка
     const string _me = _nm+"::classify";


     Point a = new Point (end.X - bgn.X, end.Y-bgn.Y);
     Point b = new Point (origin.X - bgn.X, origin.Y-bgn.Y);

     double sa = 1.0*a.X *b.Y - 1.0*b.X*a.Y;

#if DEBUG1
     gVars.lfl.wrLn ("{0}: origin/bgn/eng: {1}:{2}/{3}:{4}/{5}:{6} \n", _me,  
                                           origin.X, origin.Y,  
                                                    bgn.X, bgn.Y,
                                                           end.X, end.Y );
     gVars.lfl.wrLn ("{0}: a/b/sa: {1}:{2}/{3}:{4}/{5} \n", _me,  
                                a.X, a.Y,  
                                        b.X, b.Y,   sa);
#endif

     if (sa >  0.0) return   Position.Left;
     if (sa <  0.0) return   Position.Right;
     if ((a.X*b.X<0)||(a.Y*b.Y<0)) return  Position.Behind;
     if (geo.len(a) < geo.len(b))  return  Position.Ahead;
     if (origin.X == bgn.X && origin.Y == bgn.Y) return Position.Begin;
     if (origin.X == end.X && origin.Y == end.Y) return Position.End;
     return Position.Between;
   }


   static public Edge edgeType(Point a, Point v, Point w){
     const string _me = _nm+"::IsPointInside";
     Edge ret = Edge.Inessential;
     Position pos;
     switch (pos = classify(a, v, w)) {
      case Position.Left : ret =  ((v.Y < a.Y)&&(a.Y<=w.Y))?Edge.Crossing:Edge.Inessential ; break;
      case Position.Right: ret =  ((w.Y < a.Y)&&(a.Y<=v.Y))?Edge.Crossing:Edge.Inessential ; break;
      case Position.Begin: 
      case Position.End: 
      case Position.Between: 
                          ret =  Edge.Touching; break;
     }
     gVars.lfl.wrLn ("{0}: point: {1}:{2}; ret/pos: {3}/{4} \n", _me,  a.X, a.Y, ret, pos);

     return ret;
   }

   static public   bool IsPointInside (List<Point> plgn, Point pnt ) {
     const string _me = _nm+"::IsPointInside";
     int parity = 0;
     bool ret = false;
     gVars.lfl.wrLn ("{0}: point: {1}:{2} \n", _me,  pnt.X, pnt.Y);
     if ( plgn != null &&  plgn.Count>2) {
       Point bgn;
       Point end;
       for ( int i = 0; i < plgn.Count; i++){
         bgn = plgn[i];
         if (i+1 >= plgn.Count) {
           end = plgn[0];
         }
         else
           end = plgn[i+1];
         gVars.lfl.wrLn ("{0}: {1}th edge: {2}:{3}/{4}:{5}; parity {6} \n", _me, 
                                i, bgn.X, bgn.Y, end.X, end.Y, parity);
         switch(edgeType(pnt, bgn, end)){
           case Edge.Touching: return true;
           case Edge.Crossing: parity = 1 - parity; break;
         }
       }
       gVars.lfl.wrLn ("{0}: parity: {1} \n", _me,  parity);
       if (parity!=0)
         ret = true;
     }
     else {
       ; // not polygon but dot or segment.  check in another way
     }
     return ret;
   }
 
  static public   int  GetInnerVertex (List<Point> plgn) { /// взять первую внутреннюю вершину
     int rc = -1;
     const string _me = _nm+"::GetInnerConvex";
     if ( plgn != null & plgn.Count > 3){
       int l, r;
       double   minLen = (double) Math.Max(gVars.polygon.maxX, gVars.polygon.maxY);
       for (int i = 0; i < plgn.Count; i++)    // to find smallest distance
         for (int j = 0; j < plgn.Count; j++) { //  between any two vertexes
           if (i !=j ){
             minLen = Math.Min(minLen, len(plgn[i], plgn[j]));
#if DEBUG
             gVars.lfl.wrLn ("{0}: i/j/minL: {1}/{2}/'{3}' \n", _me, i, j, minLen); 
#endif
           }
         }
       gVars.lfl.wrLn ("{0}: minL: '{1}' \n", _me, minLen); 


       Point dot;//, dotL, dotR ;
       for (rc = 0; rc < plgn.Count; rc++){
         l = (rc+plgn.Count-1)%plgn.Count;
         r = (rc+plgn.Count+1)%plgn.Count;
         gVars.lfl.wrLn ("{0}: i/l/r/Count: {1}/{2}/{3}/{4} \n", _me,  rc, l, r, plgn.Count);
         dot = halfWay (plgn[l], plgn[r]) ;                           // to make one step in any case
         gVars.lfl.wrLn ("{0}: big vertex/dot: {1}:{2}/{3}:{4} \n", _me,  
                                            plgn[rc].X, plgn[rc].Y,
                                                    dot.X, dot.Y );
         dot =  stepLess (plgn[rc], dot, minLen/2);                   // небольшой сдвиг от вершины
                                                                      
         gVars.lfl.wrLn ("{0}: big vertex/dot2: {1}:{2}/{3}:{4} \n", _me,  
                                            plgn[rc].X, plgn[rc].Y,
                                                    dot.X, dot.Y );

         if (IsPointInside(plgn, dot)==false)                         
           return rc;
       }
       rc = -1;
     }
     return rc;
   }


   static public  List<Point>  RemoveInnerVertex (List<Point> plgn) { /// удаление внутренней вершины
     const string _me = _nm+"::ToConvex";
     int idx=0;
     if ( plgn != null && plgn.Count > 3 ){
       idx =  GetInnerVertex (plgn);
       if (idx >=0 ) {
         plgn.Remove (plgn[idx]);                                   // образ на экране
         gVars.polygon.Remove(gVars.polygon[idx]);                  // исходные точки для вывода в xml
       }
     }
     return plgn; 
   }

   static public  List<Point>  ToConvex (List<Point> plgn) {       /// удаление всех внутренних вершин
     const string _me = _nm+"::ToConvex";
     int idx=0;
     while ( plgn != null && plgn.Count > 3 ){
       idx =  GetInnerVertex (plgn);
       if (idx <0 ) break;
       plgn.Remove (plgn[idx]);
       gVars.polygon.Remove(gVars.polygon[idx]);
     }
     return plgn; 
   }

}}