Monday, February 10, 2020

how to check a 2D point within the polygon?

in my recent interview, the interviewer gave a problem to solve

I implemented a program with  crossing number algorithm

using System;
using System.Collections.Generic;
using System.Linq;
namespace Polygon_Graph
{
    class Program
    {
        static void Main(string[] args)
        {
            List<Point> polygon = new List<Point>();
            Console.WriteLine("please enter your points to build the polygon, enter exit to terminate the program");
            string input = Console.ReadLine();
            while (input != "0 0")
            {
                polygon.Add(GeneratePoint(input));
                input = Console.ReadLine();
            }
            Console.WriteLine("please enter your test point:");
            while (true)
            {
                input = Console.ReadLine();
                if (input == "exit")
                    break;
                Point testPoint = GeneratePoint(input);
                string resultMsg = string.Empty;
                if (IsPointOutOfBoundary(polygon, testPoint, ref resultMsg))
                {
                    Console.WriteLine("No, not inside");
                }
                else
                {
                    if (resultMsg == "Yes, inside")
                    {
                        Console.WriteLine("Yes, inside");
                    }
                    else
                    {
                        bool validateResult = ValidByCrossingNumber(polygon, testPoint);
                        if (validateResult)
                        {
                            Console.WriteLine("Yes, inside");
                        }
                        else
                        {
                            Console.WriteLine("No, not inside");
                        }
                    }
                }
            }
        }
        private static bool IsPointOutOfBoundary(List<Point> polygon, Point testPoint, ref string resultMsg) {
            var result = false;
            int minX = polygon[0].X;
            int maxX = polygon[0].X;
            int minY = polygon[0].Y;
            int maxY = polygon[0].Y;
            for (var i = 1; i < polygon.Count(); i++)
            {
                Point q = polygon[i];
                minX = Math.Min(q.X, minX);
                maxX = Math.Max(q.X, maxX);
                minY = Math.Min(q.Y, minY);
                maxY = Math.Max(q.Y, maxY);
            }
            //check for the boundary if the test point out of boundary return false
            if (testPoint.X < minX || testPoint.X > maxX || testPoint.Y < minY || testPoint.Y > maxY)
            {
                result = true;
            }
            else if (testPoint.X == minX && testPoint.Y < maxY || testPoint.X == maxX && testPoint.Y < maxY)
            {
                resultMsg = "Yes, inside";
            }
            return result;
        }
        private static bool ValidByCrossingNumber(List<Point> polygon, Point testPoint)
        {
            bool result = false;
            var j = polygon.Count() - 1;
            for (var i = 0; i < polygon.Count(); i++)
            {
                if (polygon[i].Y < testPoint.Y && polygon[j].Y >= testPoint.Y || polygon[j].Y < testPoint.Y && polygon[i].Y >= testPoint.Y)
                {
                    if (polygon[i].X + (testPoint.Y - polygon[i].Y) * (polygon[j].X - polygon[i].X) / (polygon[j].Y - polygon[i].Y) > testPoint.X)
                    {
                        result = !result;
                    }
                }
                j = i;
            }
            return result;
        }
        private static Point GeneratePoint(string inputString)
        {
            string[] strArray = inputString.Split(' ');
            if (strArray.Length >= 2)
            {
                return new Point
                {
                    X = ConvertToInt(strArray[0]),
                    Y = ConvertToInt(strArray[1])
                };
            }
            return null;
        }
        private static int ConvertToInt(string str)
        {
            try
            {
                return Int32.Parse(str);
            }
            catch {
                return 0;
            }
        }
    }
        class Point {
            public int X { get; set; }
            public int Y { get; set; }
        }
}

No comments:

Post a Comment