context: using System;
  using System.Collections;
  using System.Collections.Generic;
  using System.Diagnostics;
  using System.IO;
  
  namespace Weland {
      public delegate bool PolygonFilter(Polygon p);
      public delegate bool ObjectFilter(MapObject o);
  
      public partial class Level {
  	public static PolygonFilter Filter = p => true;
  	public static ObjectFilter ObjectFilter = o => true;
  	public static bool FilterPoints = false;
  	public static bool RememberDeletedSides = false;
  
  	Dictionary<short, Side> ClockwiseOrphanedSides = new Dictionary<short, Side>();
  	Dictionary<short, Side> CounterClockwiseOrphanedSides = new Dictionary<short, Side>();
  	HashSet<short> LinesReflectingOrphanedSides = new HashSet<short>();
  
  	public bool FilterLine(PolygonFilter f, Line line) {
  	    if (line.ClockwisePolygonOwner == -1) {
  		if (line.CounterclockwisePolygonOwner == -1) {
  		    return true;
  		} else {
  		    return f(Polygons[line.CounterclockwisePolygonOwner]);
  		}
  	    } else {
  		if (line.CounterclockwisePolygonOwner == -1) {
  		    return f(Polygons[line.ClockwisePolygonOwner]);
  		} else {
  		    return f(Polygons[line.ClockwisePolygonOwner]) || f(Polygons[line.CounterclockwisePolygonOwner]);
  		}
  	    }
  	}
  
  	public bool FilterPoint(PolygonFilter f, short index) {
  	    if (!FilterPoints) return true;
  	    HashSet<Polygon> polygonSet = EndpointPolygons[index];
  	    foreach (Polygon polygon in polygonSet) {
  		if (f(polygon)) {
  		    return true;
  		}
  	    }
  
  	    HashSet<Line> lineSet = EndpointLines[index];
  	    foreach (Line line in lineSet) {
  		if (FilterLine(f, line)) {
  		    return true;
  		}
  	    }
  	    return false;
  	}
  
  	public int Distance(Point p0, Point p1) {
  	    return (int) Math.Round(Math.Sqrt(Math.Pow(p0.X - p1.X, 2) + Math.Pow(p0.Y - p1.Y, 2)));
  	}
  
  	double U(Point p, Line line) {
  	    Point e0 = Endpoints[line.EndpointIndexes[0]];
  	    Point e1 = Endpoints[line.EndpointIndexes[1]];
  
  	    return  ((((double) p.X - e0.X) * ((double) e1.X - e0.X)) + (((double) p.Y - e0.Y) * ((double) e1.Y - e0.Y))) / (Math.Pow(e1.X - e0.X, 2) + Math.Pow(e1.Y - e0.Y, 2));
  	}
  
  	public Point ClosestPointOnLine(Point p, Line line) {
  	    Point e0 = Endpoints[line.EndpointIndexes[0]];
  	    Point e1 = Endpoints[line.EndpointIndexes[1]];
  
  	    double u = U(p, line);
  	    Point point;
  	    point.X = (short) Math.Round(e0.X + u * (e1.X - e0.X));
  	    point.Y = (short) Math.Round(e0.Y + u * (e1.Y - e0.Y));
  	    return point;
  	}
  
  	public int Distance(Point p, Line line) {
  	    Point e0 = Endpoints[line.EndpointIndexes[0]];
  	    Point e1 = Endpoints[line.EndpointIndexes[1]];
  
  	    double u = U(p, line);
  
  	    if (u > 1.0) {
  		return Distance(p, e1);
  	    } else if (u < 0.0) {
  		return Distance(p, e0);
  	    } else {
  		Point i = new Point();
  		i.X = (short) Math.Round(e0.X + u * (e1.X - e0.X));
  		i.Y = (short) Math.Round(e0.Y + u * (e1.Y - e0.Y));
  		return Distance(p, i);
  	    }
  	}
  
  	public double Dot(Point p0, Point p1) {
  	    return p0.X * p1.X + p0.Y * p1.Y;
  	}
  
  	public double Cross(Point p0, Point p1) {
  	    return p0.Y * p1.X - p0.X * p1.Y;
  	}
  
  	public short GetClosestAnnotation(Point p) {
  	    int min = int.MaxValue;
  	    short closest_annotation = -1;
  	    for (short i = 0; i < Annotations.Count; ++i) {
  		Annotation a = Annotations[i];
  		int distance = Distance(p, new Point(a.X, a.Y));
  		if (distance < min) {
  		    closest_annotation = i;
  		    min = distance;
  		}
  	    }
  	    return closest_annotation;
  	}
  
  	public short GetClosestPoint(Point p) {
  	    int min = int.MaxValue;
  	    short closest_point = -1;
  	    for (short i = 0; i < Endpoints.Count; ++i) {	
  		if (FilterPoint(Filter, i)) {
  		    int distance = Distance(p, Endpoints[i]);
  		    if (distance < min) {
  			closest_point = i;
  			min = distance;
  		    }
  		}
  	    }
  	    return closest_point;
  	}
  
  	public short GetClosestObject(Point p) {
  	    int min = int.MaxValue;
  	    short closest_object = -1;
  	    for (short i = 0; i < Objects.Count; ++i) {
  		if (Filter(Polygons[Objects[i].PolygonIndex]) && ObjectFilter(Objects[i])) {
  		    int distance = Distance(p, new Point(Objects[i].X, Objects[i].Y));
  		    if (distance < min) {
  			closest_object = i;
  			min = distance;
  		    }
  		}
  	    }
  
  	    return closest_object;
  	}
  
  	public short GetClosestLine(Point p) {
  	    int min = int.MaxValue;
  	    short closest_line = -1;
  	    for (short i = 0; i < Lines.Count; ++i) {
  		if (FilterLine(Filter, Lines[i])) {
  		    int distance = Distance(p, Lines[i]);
  		    if (distance < min) {
  			closest_line = i;
  			min = distance;
  		    }
  		}
  	    }
  	    return closest_line;
  	}
  
  	public short GetEnclosingPolygon(Point p) {
  	    for (int i = 0; i < Polygons.Count; ++i) {
  		if (Filter(Polygons[i])) {
  		    List<short> points = GetPointRingFromLineRing(new List<short>(Polygons[i].LineIndexes).GetRange(0, Polygons[i].VertexCount));
  		    if (PointLoopEnclosesPoint(p, points)) {
  			return (short) i;
  		    }
  		}		
  	    }
  	    return -1;
  	}
  
  	public short NewPoint(short X, short Y) {
  	    Point p = new Point();
  	    p.X = X;
  	    p.Y = Y;
  	    Endpoints.Add(p);
  	    EndpointPolygons.Add(new HashSet<Polygon>());
  	    EndpointLines.Add(new HashSet<Line>());
  	    return (short) (Endpoints.Count - 1);
  	}
  
  	public short NewLine(short p1, short p2) {
  	    Line line = new Line();
  	    line.EndpointIndexes[0] = p1;
  	    line.EndpointIndexes[1] = p2;
  	    EndpointLines[p1].Add(line);
  	    EndpointLines[p2].Add(line);
  	    Lines.Add(line);
  	    return (short) (Lines.Count - 1);
  	}
  
  	public short NewObject(Point p, short polygon_index) {
  	    MapObject o = new MapObject();
  	    o.X = p.X;
  	    o.Y = p.Y;
  	    o.PolygonIndex = polygon_index;
  	    Objects.Add(o);
  	    return (short) (Objects.Count - 1);
  	}
  
  	// split line, return a new point index at X, Y
  	public short SplitLine(short index, short X, short Y) {
  	    Line line = Lines[index];
  	    short e0 = line.EndpointIndexes[0];
  	    short e1 = line.EndpointIndexes[1];
  	    short p = NewPoint(X, Y);
  
  	    short l1 = NewLine(e0, p);
  	    short l2 = NewLine(p, e1);
  
  	    if (line.ClockwisePolygonOwner != -1) {
  		Polygon polygon = Polygons[line.ClockwisePolygonOwner];
  
  		for (int i = 0; i < Polygon.MaxVertexCount; ++i) {
  		    if (polygon.LineIndexes[i] == index) {
  			for (int j = Polygon.MaxVertexCount - 2; j >= i; --j) {
  			    polygon.LineIndexes[j + 1] = polygon.LineIndexes[j];
  			    polygon.AdjacentPolygonIndexes[j + 1] = polygon.AdjacentPolygonIndexes[j];
  			    polygon.EndpointIndexes[j + 1] = polygon.EndpointIndexes[j];
  			}
  
  
  			polygon.LineIndexes[i] = l1;
  			polygon.LineIndexes[i + 1] = l2;
  
  			if (polygon.EndpointIndexes[i] == e0) {
  			    polygon.EndpointIndexes[i + 1] = p;
  			} else {
  			    polygon.EndpointIndexes[i] = p;
  			}
  			EndpointPolygons[p].Add(polygon);
  
  			polygon.VertexCount++;
  			UpdatePolygonConcavity(polygon);
  
  			if (line.ClockwisePolygonSideIndex != -1) {
  			    // clone it
  			    Side side = Sides[line.ClockwisePolygonSideIndex];
  			    MemoryStream stream = new MemoryStream();
  			    BinaryWriterBE writer = new BinaryWriterBE(stream);
  			    side.Save(writer);
  			    
  			    stream.Seek(0, SeekOrigin.Begin);
  			    Side s1 = new Side();
  			    BinaryReaderBE reader = new BinaryReaderBE(stream);
  			    s1.Load(reader);
  			    s1.LineIndex = l1;
  			    Lines[l1].ClockwisePolygonSideIndex = (short) Sides.Count;
  			    Sides.Add(s1);
  			    
  			    stream.Seek(0, SeekOrigin.Begin);
  			    Side s2 = new Side();
  			    s2.Load(reader);
  			    s2.LineIndex = l2;
  			    short l1_length = (short) Distance(Endpoints[e0], Endpoints[p]);
  			    if (!s2.Primary.Texture.IsEmpty()) {
  				s2.Primary.X += l1_length;
  			    }
  
  			    if (!s2.Secondary.Texture.IsEmpty()) {
  				s2.Secondary.X += l1_length;
  			    }
  
  			    if (!s2.Transparent.Texture.IsEmpty()) {
  				s2.Transparent.X += l1_length;
  			    }
  
  			    Lines[l2].ClockwisePolygonSideIndex = (short) Sides.Count;
  			    Sides.Add(s2);
  			}
  			break;
  		    }
  		}
  
  		Lines[l1].ClockwisePolygonOwner = line.ClockwisePolygonOwner;
  		Lines[l2].ClockwisePolygonOwner = line.ClockwisePolygonOwner;
  	    }
  
  	    if (line.CounterclockwisePolygonOwner != -1) {
  		Polygon polygon = Polygons[line.CounterclockwisePolygonOwner];
  		for (int i = 0; i < Polygon.MaxVertexCount; ++i) {
  		    if (polygon.LineIndexes[i] == index) {
  			for (int j = Polygon.MaxVertexCount - 2; j >= i; --j) {
  			    polygon.LineIndexes[j + 1] = polygon.LineIndexes[j];
  			    polygon.AdjacentPolygonIndexes[j + 1] = polygon.AdjacentPolygonIndexes[j];
  			    polygon.EndpointIndexes[j + 1] = polygon.EndpointIndexes[j];
  			}
  
  
  			polygon.LineIndexes[i] = l2;
  			polygon.LineIndexes[i + 1] = l1;
  			if (polygon.EndpointIndexes[i] == e0) {
  			    polygon.EndpointIndexes[i] = p;
  			} else {
  			    polygon.EndpointIndexes[i + 1] = p;
  			}
  
  			polygon.VertexCount++;
  			UpdatePolygonConcavity(polygon);
  
  			if (line.CounterclockwisePolygonSideIndex != -1) {
  			    // clone it
  			    Side side = Sides[line.CounterclockwisePolygonSideIndex];
  			    MemoryStream stream = new MemoryStream();
  			    BinaryWriterBE writer = new BinaryWriterBE(stream);
  			    side.Save(writer);
  			    
  			    stream.Seek(0, SeekOrigin.Begin);
  			    Side s1 = new Side();
  			    BinaryReaderBE reader = new BinaryReaderBE(stream);
  			    s1.Load(reader);
  			    s1.LineIndex = l1;
  			    Lines[l1].CounterclockwisePolygonSideIndex = (short) Sides.Count;
  			    Sides.Add(s1);
  			    
  			    stream.Seek(0, SeekOrigin.Begin);
  			    Side s2 = new Side();
  			    s2.Load(reader);
  			    s2.LineIndex = l2;
  			    short l1_length = (short) Distance(Endpoints[e0], Endpoints[p]);
  			    if (!s2.Primary.Texture.IsEmpty()) {
  				s2.Primary.X += l1_length;
  			    }
  
  			    if (!s2.Secondary.Texture.IsEmpty()) {
  				s2.Secondary.X += l1_length;
  			    }
  
  			    if (!s2.Transparent.Texture.IsEmpty()) {
  				s2.Transparent.X += l1_length;
  			    }
  
  			    Lines[l2].CounterclockwisePolygonSideIndex = (short) Sides.Count;
  			    Sides.Add(s2);
  			}
  			break;
  		    }
  		}
  
  		Lines[l1].CounterclockwisePolygonOwner = line.CounterclockwisePolygonOwner;
  		Lines[l2].CounterclockwisePolygonOwner = line.CounterclockwisePolygonOwner;
  
  		if (Lines[l1].ClockwisePolygonOwner != -1) {
  		    Lines[l1].Transparent = true;
  		}
  
  		if (Lines[l2].ClockwisePolygonOwner != -1) {
  		    Lines[l2].Transparent = true;
  		}
  	    }
  
  	    if (line.ClockwisePolygonSideIndex != -1) {
  		DeleteSide(line.ClockwisePolygonSideIndex);
  	    }
  
  	    if (line.CounterclockwisePolygonSideIndex != -1) {
  		DeleteSide(line.CounterclockwisePolygonSideIndex);
  	    }
  
  	    DeleteLineIndex(index);
  
  	    return p;
  	}
  
  	// returns all line indices due east of X, Y sorted by x intersect
  	SortedDictionary<double, short> GetFillCandidateLines(short X, short Y) {
  	    SortedDictionary<double, short> candidates = new SortedDictionary<double, short>();
  	    for (int i = 0; i < Lines.Count; ++i) {
  		if (FilterLine(Filter, Lines[i])) {
  		    Point p0 = Endpoints[Lines[i].EndpointIndexes[0]];
  		    Point p1 = Endpoints[Lines[i].EndpointIndexes[1]];
  		    
  		    if (p1.Y == p0.Y) {
  			continue;
  		    }
  		    
  		    double u = (double) (Y - p0.Y) / (p1.Y - p0.Y);
  		    
  		    double x_intersect = p0.X + (u * (p1.X - p0.X));
  		    if (u >= 0.0 && u <= 1.0 && x_intersect > X) {
  			// note that if two lines miraculously share the
  			// same X intercept, one will be lost--oh well,
  			// click somewhere else
  			candidates[x_intersect] = (short) i;
  		    }
  		}
  	    }
  	    return candidates;
  	}
  	
  	// get all lines attached to endpoint
  	public List<short> FindEndpointLines(short index) {
  	    List<short> lines = new List<short>();
  	    for (int i = 0; i < Lines.Count; ++i) {
  		Line line = Lines[i];
  		if (FilterLine(Filter, line) && (line.EndpointIndexes[0] == index ||
  					 line.EndpointIndexes[1] == index)) {
  		    lines.Add((short) i);
  		}
  	    }
  	    return lines;
  	}
  
  	// get all polygons that have this endpoint
  	public List<short> FindEndpointPolygons(short index) {
  	    List<short> polygons = new List<short>();
  	    for (int i = 0; i < Polygons.Count; ++i) {
  		for (int j = 0; j < Polygons[i].VertexCount; ++j) {
  		    Line line = Lines[Polygons[i].LineIndexes[j]];
  		    if (line.EndpointIndexes[0] == index ||
  			line.EndpointIndexes[1] == index) {
  			polygons.Add((short) i);
  			break;
  		    }
  		}
  	    }
  	    return polygons;
  	}
  
  	Point Diff(Point p0, Point p1) {
  	    return new Point((short) (p0.X - p1.X), (short) (p0.Y - p1.Y));
  	}
  
  	double Norm(Point p) {
  	    return Math.Sqrt(Math.Pow(p.X, 2) + Math.Pow(p.Y, 2));
  	}
  
  	bool BuildLoop(short target, short prev, short current, int depth, short starter, List<short> list) {
  	    if (depth >= 8) {
  		return false;
  	    } else if (current == target) {
  		int other_index = Lines[list[0]].EndpointIndexes[0];
  		if (other_index == current)
  
gt: 		    other_index = Lines[list[0]].EndpointIndexes[1];