www.pudn.com > bsiftC_.rar > AreaFilter.cs

/* AreaFilter.cs
 *
 * Area maximizing match filtration using convex hull and polygon-area
 * maximization.
 *
 * (C) Copyright 2004 -- Sebastian Nowozin (nowozin@cs.tu-berlin.de)
 *
 * Convex hull code based on Ken Clarksons original C implementation.
 * Polygon area formula by Paul Bourke.
 */

using System;
using System.Collections;


public class
AreaFilter
{

	public static void Main (string[] args)
	{
		ArrayList al = new ArrayList ();
		Random rnd = new Random ();

		for (int n = 0 ; n < 10 ; ++n) {
			Point p = new Point ();

			p.x = rnd.NextDouble () * 400.0;
			p.y = rnd.NextDouble () * 400.0;

			al.Add (p);
		}
		foreach (Point p in al)
			Console.WriteLine ("{0} {1} # GNUPLOT1", p.x, p.y);

		AreaFilter conv = new AreaFilter ();
		ArrayList hull = conv.CreateConvexHull (al);

		Console.WriteLine ("\nhull: {0} elements", hull.Count);
		foreach (Point p in hull)
			Console.WriteLine ("{0} {1} # GNUPLOT2", p.x, p.y);

		Console.WriteLine ("\npolygon area: {0}", conv.PolygonArea (hull));
	}

	public class Point
	{
		public double x, y;
		public object user = null;	// Store anything for the user
	}

	// Measure the absolute area of a non self-intersecting polygon.
	// Formula by Paul Bourke
	// (http://astronomy.swin.edu.au/~pbourke/geometry/polyarea/)
	//
	// The input points must be ordered (clock- or counter-clockwise). The
	// polygon is closed automatically between the first and the last point,
	// so there should not be two same points in the polygon point set.
	public double PolygonArea (ArrayList orderedPoints)
	{
		double A = 0.0;

		for (int n = 0 ; n < orderedPoints.Count ; ++n) {
			Point p0 = (Point) orderedPoints[n];
			Point p1 = (Point) orderedPoints[(n + 1) % orderedPoints.Count];

			A += p0.x * p1.y - p1.x * p0.y;
		}

		A *= 0.5;

		return (Math.Abs (A));
	}

	// Create the convex hull of a point set.
	public ArrayList CreateConvexHull (ArrayList points)
	{
		return (CreateConvexHull ((Point[]) points.ToArray (typeof (Point))));
	}

	public ArrayList CreateConvexHull (Point[] points)
	{
		int chn = CreateHull (points);

		ArrayList hull = new ArrayList ();
		for (int k = 0 ; k < chn ; ++k)
			hull.Add (points[k]);

		return (hull);
	}

	public class CompareLow : IComparer {
		public int Compare (object o1, object o2)
		{
			Point p1 = (Point) o1;
			Point p2 = (Point) o2;

			double v = p1.x - p2.x;
			if (v > 0)
				return (1);
			if (v < 0)
				return (-1);

			v = p2.y - p1.y;
			if (v > 0)
				return (1);
			if (v < 0)
				return (-1);

			// Equal point
			return (0);
		}
	}

	public class CompareHigh : IComparer {
		CompareLow cl;

		public CompareHigh ()
		{
			cl = new CompareLow ();
		}

		public int Compare (object o1, object o2)
		{
			return (cl.Compare (o2, o1));
		}
	}


	private bool ccw (Point[] points, int i, int j, int k)
	{
		double a = points[i].x - points[j].x;
		double b = points[i].y - points[j].y;
		double c = points[k].x - points[j].x;
		double d = points[k].y - points[j].y;

		return ((a * d - b * c) <= 0.0);
	}

	private int MakeChain (Point[] points, IComparer comp)
	{
		System.Array.Sort (points, comp);

		int s = 1;
		int pCount = points.Length;
		for (int i = 2 ; i < pCount ; ++i) {
			int j;
			for (j = s ; j >= 1 && ccw (points, i, j, j - 1) ; --j)
				;

			s = j + 1;

			// Swap
			Point t = points[s];
			points[s] = points[i];
			points[i] = t;
		}

		return (s);
	}

	private int CreateHull (Point[] points)
	{
		int u = MakeChain (points, new CompareLow ());

		if (points.Length == 0)
			return (0);
		/*
		for (int k = 0 ; k < u ; ++k)
			Console.WriteLine ("point {0}: {1} {2}", k, points[k].x, points[k].y);
			*/

		Point[] pointsHigh = new Point[points.Length + 1 - u];
		//Console.WriteLine ("points.Length = {0}, u = {1}", points.Length, u);
		System.Array.Copy (points, u, pointsHigh, 0, points.Length - u);
		pointsHigh[pointsHigh.Length - 1] = points[0];

		int h = MakeChain (pointsHigh, new CompareHigh ());

		for (int p = u ; p < points.Length ; ++p)
			points[p] = pointsHigh[p - u];

		/*
		Console.WriteLine ("h = {0}, u = {1}", h, u);
		for (int k = 0 ; k < (h + u) ; ++k)
			Console.WriteLine ("point {0}: {1} {2}", k, points[k].x, points[k].y);
			*/

		return (h + u);
	}
}