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; }
}
}
