Repository: vaskoz/dailycodingproblem-go (go)

Issue:
Day 236
Good morning! Here's your coding interview problem for today.

This problem was asked by Nvidia.

You are given a list of N points (x1, y1), (x2, y2), ..., (xN, yN) representing a polygon. You can assume these points are given in order; that is, you can construct the polygon by connecting point 1 to point 2, point 2 to point 3, and so on, finally looping around to connect point N to point 1.

Determine if a new point p lies inside this polygon. (If p is on the boundary of the polygon, you should return False).

Pull request:
Day236
Resolves #485.

Patch:
diff --git a/README.md b/README.md
index e21ffa5..4c80f8b 100644
--- a/README.md
+++ b/README.md
@@ -244,3 +244,4 @@ problems from
 * [Day 233](https://github.com/vaskoz/dailycodingproblem-go/issues/479)
 * [Day 234](https://github.com/vaskoz/dailycodingproblem-go/issues/481)
 * [Day 235](https://github.com/vaskoz/dailycodingproblem-go/issues/483)
+* [Day 236](https://github.com/vaskoz/dailycodingproblem-go/issues/485)
diff --git a/day236/problem.go b/day236/problem.go
new file mode 100644
index 0000000..9432a52
--- /dev/null
+++ b/day236/problem.go
@@ -0,0 +1,38 @@
+package day236
+
+// Point is a cartesian 2D point.
+type Point struct {
+	X, Y float64
+}
+
+// LiesInsidePolygon answers if the given point lies inside the polygon.
+func LiesInsidePolygon(polygon []Point, p Point) bool {
+	polygon = append(polygon, polygon[0]) // to link back to first point
+	intersections := make(map[Point]struct{})
+	for i := 1; i < len(polygon); i++ {
+		low, high := polygon[i-1], polygon[i]
+		if low.Y > high.Y {
+			low, high = high, low
+		}
+		if low.Y == high.Y || p.Y < low.Y || p.Y > high.Y {
+			continue // skip horizontal lines and too high, too low
+		}
+		if low.X == high.X { // vertical line
+			if p.X == low.X && p.Y >= low.Y && p.Y <= high.Y {
+				return false // on boundary
+			} else if p.X < low.X && p.Y >= low.Y && p.Y <= high.Y {
+				intersections[Point{low.X, p.Y}] = struct{}{}
+			}
+			continue
+		}
+		slope := (high.Y - low.Y) / (high.X - low.X)
+		b := low.Y - slope*low.X
+		xAtY := (p.Y - b) / slope
+		if p.X == xAtY {
+			return false // on boundary
+		} else if p.X < xAtY {
+			intersections[Point{xAtY, p.Y}] = struct{}{}
+		}
+	}
+	return len(intersections) == 1
+}


Test patch:
diff --git a/day236/problem_test.go b/day236/problem_test.go
new file mode 100644
index 0000000..f64030f
--- /dev/null
+++ b/day236/problem_test.go
@@ -0,0 +1,38 @@
+package day236
+
+import "testing"
+
+var testcases = []struct {
+	polygon  []Point
+	p        Point
+	isInside bool
+}{
+	{[]Point{{0, 0}, {0, 5}, {5, 5}, {5, 0}}, Point{2, 2}, true},
+	{[]Point{{0, 0}, {0, 5}, {5, 5}, {5, 0}}, Point{0, 0}, false},
+	{[]Point{{0, 0}, {0, 5}, {5, 5}, {5, 0}}, Point{-2, 2}, false},
+	{[]Point{{0, 0}, {0, 5}, {5, 5}, {5, 0}}, Point{5, 2}, false},
+	{[]Point{{3, 2}, {2, 3}, {3, 4}, {4, 3}}, Point{3, 3}, true},
+	{[]Point{{3, 2}, {2, 3}, {3, 4}, {4, 3}}, Point{2, 3}, false},
+	{[]Point{{3, 2}, {2, 3}, {3, 4}, {4, 3}}, Point{0, 0}, false},
+	{[]Point{{3, 2}, {2, 3}, {3, 4}, {4, 3}}, Point{3, 5}, false},
+	{[]Point{{0, 0}, {5, 5}, {10, 0}}, Point{3, 3}, false},
+	{[]Point{{0, 0}, {5, 5}, {10, 0}}, Point{6, 4}, false},
+	{[]Point{{0, 0}, {5, 5}, {10, 0}}, Point{6, 3}, true},
+}
+
+func TestLiesInsidePolygon(t *testing.T) {
+	t.Parallel()
+	for _, tc := range testcases {
+		if result := LiesInsidePolygon(tc.polygon, tc.p); result != tc.isInside {
+			t.Errorf("Given %v and p=%v, expected %v, got %v", tc.polygon, tc.p, tc.isInside, result)
+		}
+	}
+}
+
+func BenchmarkLiesInsidePolygon(b *testing.B) {
+	for i := 0; i < b.N; i++ {
+		for _, tc := range testcases {
+			LiesInsidePolygon(tc.polygon, tc.p)
+		}
+	}
+}