Given coordinates of the N points of a Convex Polygon. The task is to check if the given point (X, Y) lies inside the polygon. Examples:
Input: N = 7, Points: {(1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)}, Query: X = 3, Y = 2 Below is the image of plotting of the given points:
Output: YES Input: N = 7, Points: {(1, 1), (2, 1), (3, 1), (4, 1), (4, 2), (4, 3), (4, 4)}, Query: X = 3, Y = 9 Output: NO
Approach: The idea is to use Graham Scan Algorithm to find if the given point lies inside the Convex Polygon or not. Below are some of the observations:
- Suppose the point (X, Y) is a point in the set of points of the convex polygon. If the Graham Scan Algorithm is used on this set of points, another set of points would be obtained, which makes up the Convex Hull.
- If the point (X, Y) lies inside the polygon, it won’t lie on the Convex Hull and hence won’t be present in the newly generated set of points of the Convex Hull.
- If the point (X, Y) lies outside the polygon, it will then lie on the Convex Hull formed and hence would be present in the newly generated set of points of the Convex Hull.
Below are the steps to solve the problem:
- Sort the given points along with the query point in the increasing order of their abscissa values. If the abscissa values(x-coordinates) of any two points are the same, then sort them on the basis of their ordinate value.
- Set the bottom-left point as the start point and top-right point as the end point of the convex hull.
- Iterate over all the points and find out the points, forming the convex polygon, that lies in between the start and endpoints in the clockwise direction. Store these points in a vector.
- Iterate over all the points and find out the points, forming the convex polygon, that lies in between the start and endpoints in the counter-clockwise direction. Store these points in the vector.
- Check if the query point exists in the vector then the point lies outside the convex hull. So return “No”.
- If the point doesn’t exist in the vector, then the point lies inside the convex hull print “Yes”.
Below is the implementation based on the above approach:
CPP
// C++ program for the above approach#include <bits/stdc++.h>using namespace std; // Sorting Function to sort pointsbool cmp(pair<int, int>& a, pair<int, int>& b){ if (a.first == b.first) return a.second < b.second; return a.first < b.first;} // Function To Check Clockwise// Orientationint cw(pair<int, int>& a, pair<int, int>& b, pair<int, int>& c){ int p = a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second); return p < 0ll;} // Function To Check Counter// Clockwise Orientationint ccw(pair<int, int>& a, pair<int, int>& b, pair<int, int>& c){ int p = a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second); return p > 0ll;} // Graham Scan algorithm to find Convex// Hull from given pointsvector<pair<int, int> > convexHull( vector<pair<int, int> >& v){ // Sort the points sort(v.begin(), v.end(), cmp); int n = v.size(); if (n <= 3) return v; // Set starting and ending points as // left bottom and top right pair<int, int> p1 = v[0]; pair<int, int> p2 = v[n - 1]; // Vector to store points in // upper half and lower half vector<pair<int, int> > up, down; // Insert StartingEnding Points up.push_back(p1); down.push_back(p1); // Iterate over points for (int i = 1; i < n; i++) { if (i == n - 1 || !ccw(p1, v[i], p2)) { while (up.size() > 1 && ccw(up[up.size() - 2], up[up.size() - 1], v[i])) { // Exclude this point // if we can form better up.pop_back(); } up.push_back(v[i]); } if (i == n - 1 || !cw(p1, v[i], p2)) { while (down.size() > 1 && cw(down[down.size() - 2], down[down.size() - 1], v[i])) { // Exclude this point // if we can form better down.pop_back(); } down.push_back(v[i]); } } // Combine upper and lower half for (int i = down.size() - 2; i > 0; i--) up.push_back(down[i]); // Remove duplicate points up.resize(unique(up.begin(), up.end()) - up.begin()); // Return the points on Convex Hull return up;} // Function to find if point lies inside// a convex polygonbool isInside(vector<pair<int, int> > points, pair<int, int> query){ // Include the query point in the // polygon points points.push_back(query); // Form a convex hull from the points points = convexHull(points); // Iterate over the points // of convex hull for (auto x : points) { // If the query point lies // on the convex hull // then it wasn't inside if (x == query) return false; } // Otherwise it was Inside return true;} // Driver Codeint main(){ // Points of the polygon // given in any order int n = 7; vector<pair<int, int> > points; points = { { 1, 1 }, { 2, 1 }, { 3, 1 }, { 4, 1 }, { 4, 2 }, { 4, 3 }, { 4, 4 } }; // Query Points pair<int, int> query = { 3, 2 }; // Check if its inside if (isInside(points, query)) { cout << "YES" << endl; } else { cout << "NO" << endl; } return 0;} |
Java
import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class GFG { // Function To Check Clockwise Orientation static boolean cw(int[] a, int[] b, int[] c) { int p = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]); return p < 0; } // Function To Check Counter Clockwise Orientation static boolean ccw(int[] a, int[] b, int[] c) { int p = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]); return p > 0; } // Graham Scan Algorithm To Find Convex Hull From Given // Points static int[][] convexHull(int[][] v) { // Sort The Points Arrays.sort(v, (a, b) -> a[0] - b[0]); int n = v.length; if (n <= 3) { return v; } // Set Starting And Ending Points As Left Bottom And // Top Right int[] p1 = v[0]; int[] p2 = v[n - 1]; // Vector To Store Points In Upper Half And Lower // Half List<int[]> up = new ArrayList<int[]>(); List<int[]> down = new ArrayList<int[]>(); // Insert Starting/Ending Points up.add(p1); down.add(p1); // Iterate Over Points for (int i = 1; i < n; i++) { if (i == n - 1 || !ccw(p1, v[i], p2)) { while (up.size() > 1 && ccw(up.get(up.size() - 2), up.get(up.size() - 1), v[i])) { // Exclude This Point If We Can Form // Better up.remove(up.size() - 1); } up.add(v[i]); } if (i == n - 1 || !cw(p1, v[i], p2)) { while (down.size() > 1 && cw(down.get(down.size() - 2), down.get(down.size() - 1), v[i])) { // Exclude This Point If We Can Form // Better down.remove(down.size() - 1); } down.add(v[i]); } } // Combine Upper And Lower Half for (int i = down.size() - 2; i >= 0; i--) { up.add(down.get(i)); } // Return The Points On Convex Hull return up.toArray(new int[0][]); } // Function To Find If Point Lies Inside A convex // polygon static boolean isInside(int[][] points, int[] query) { // Include the query point in the // polygon points int[][] points1 = new int[points.length + 1][]; for (int i = 0; i < points.length; i++) points1[i] = points[i]; points1[points.length] = query; // Form a convex hull from the points points = convexHull(points); // Iterate over the points // of convex hull for (int[] x : points) { // If the query point lies // on the convex hull // then it wasn't inside if (Arrays.equals(x, query)) return false; } // Otherwise it was Inside return true; } // Driver Code public static void main(String[] args) { // Points of the polygon // given in any order int n = 7; int[][] points = { new int[] { 1, 1 }, new int[] { 2, 1 }, new int[] { 3, 1 }, new int[] { 4, 1 }, new int[] { 4, 2 }, new int[] { 4, 3 }, new int[] { 4, 4 } }; // Query Points int[] query = { 3, 2 }; // Check if its inside if (isInside(points, query)) { System.out.println("YES"); } else { System.out.println("NO"); } }} |
Python3
# Python3 program for the above approach# Function To Check Clockwise# Orientationdef cw(a, b, c): p = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]); return p < 0;# Function To Check Counter# Clockwise Orientationdef ccw(a, b, c): p = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]); return p > 0;# Graham Scan algorithm to find Convex# Hull from given pointsdef convexHull(v): # Sort the points v.sort(); n = len(v); if (n <= 3): return v; # Set starting and ending points as # left bottom and top right p1 = v[0]; p2 = v[n - 1]; # Vector to store points in # upper half and lower half up = [] down = []; # Insert StartingEnding Points up.append(tuple(p1)); down.append(p1); # Iterate over points for i in range(1, n): if i == n - 1 or (not ccw(p1, v[i], p2)): while len(up) > 1 and ccw(up[len(up) - 2], up[len(up) - 1], v[i]): # Exclude this point # if we can form better up.pop(); up.append(tuple(v[i])); if i == n - 1 and (not cw(p1, v[i], p2)): while (len(down) > 1) and cw(down[len(down) - 2], down[len(down) - 1], v[i]): # Exclude this point # if we can form better down.pop(); down.append(v[i]); # Combine upper and lower half for i in range(len(down) - 2, -1, -1): up.append(tuple(down[i])); # Remove duplicate points up = set(up) up = list(up) # Return the points on Convex Hull return up;# Function to find if point lies inside# a convex polygondef isInside( points, query): # Include the query point in the # polygon points points.append(query); # Form a convex hull from the points points = convexHull(points); # Iterate over the points # of convex hull for x in points: # If the query point lies # on the convex hull # then it wasn't inside if x == query: return False; # Otherwise it was Inside return True;# Driver Code# Points of the polygon# given in any ordern = 7;points = [[1, 1 ], [2, 1 ], [ 3, 1 ], [ 4, 1 ], [ 4, 2 ], [4, 3 ], [ 4, 4 ]]; # Query Pointsquery = [ 3, 2 ]; # Check if its insideif (isInside(points, query)) : print("YES"); else : print("NO"); # This code is contributed by phasing17. |
C#
using System;using System.Linq;using System.Collections.Generic;class GFG { // Function To Check Clockwise Orientation static bool cw(int[] a, int[] b, int[] c) { int p = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]); return p < 0; } // Function To Check Counter Clockwise Orientation static bool ccw(int[] a, int[] b, int[] c) { int p = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]); return p > 0; } // Graham Scan Algorithm To Find Convex Hull From Given // Points static int[][] convexHull(int[][] v) { // Sort The Points Array.Sort(v, (a, b) => a[0] - b[0]); int n = v.Length; if (n <= 3) { return v; } // Set Starting And Ending Points As Left Bottom And // Top Right int[] p1 = v[0]; int[] p2 = v[n - 1]; // Vector To Store Points In Upper Half And Lower // Half List<int[]> up = new List<int[]>(); List<int[]> down = new List<int[]>(); // Insert Starting/Ending Points up.Add(p1); down.Add(p1); // Iterate Over Points for (int i = 1; i < n; i++) { if (i == n - 1 || !ccw(p1, v[i], p2)) { while (up.Count > 1 && ccw(up[up.Count - 2], up[up.Count - 1], v[i])) { // Exclude This Point If We Can Form // Better up.RemoveAt(up.Count - 1); } up.Add(v[i]); } if (i == n - 1 || !cw(p1, v[i], p2)) { while (down.Count > 1 && cw(down[down.Count - 2], down[down.Count - 1], v[i])) { // Exclude This Point If We Can Form // Better down.RemoveAt(down.Count - 1); } down.Add(v[i]); } } // Combine Upper And Lower Half for (int i = down.Count - 2; i >= 0; i--) { up.Add(down[i]); } // Remove Duplicate Points up = new List<int[]>(new HashSet<int[]>(up)); // Return The Points On Convex Hull return up.ToArray(); } // Function To Find If Point Lies Inside A // convex polygon static bool isInside(int[][] points, int[] query) { // Include the query point in the // polygon points int[][] points1 = new int[points.Length + 1][]; for (int i = 0; i < points.Length; i++) points1[i] = points[i]; points1[points.Length] = query; // Form a convex hull from the points points = convexHull(points); // Iterate over the points // of convex hull foreach(var x in points) { // If the query point lies // on the convex hull // then it wasn't inside if (Enumerable.SequenceEqual(x, query)) return false; } // Otherwise it was Inside return true; } // Driver Code public static void Main(string[] args) { // Points of the polygon // given in any order int n = 7; int[][] points = { new int[] { 1, 1 }, new int[] { 2, 1 }, new int[] { 3, 1 }, new int[] { 4, 1 }, new int[] { 4, 2 }, new int[] { 4, 3 }, new int[] { 4, 4 } }; // Query Points int[] query = { 3, 2 }; // Check if its inside if (isInside(points, query)) { Console.WriteLine("YES"); } else { Console.WriteLine("NO"); } }} |
Javascript
// JS program for the above approach // Sorting Function to sort pointsfunction cmp(a, b){ if (a[0] == b[0]) return a[1] < b[1]; return a[0] < b[0];} // Function To Check Clockwise// Orientationfunction cw(a, b, c){ let p = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]); return p < 0;} // Function To Check Counter// Clockwise Orientationfunction ccw(a, b, c){ let p = a[0] * (b[1] - c[1]) + b[0] * (c[1] - a[1]) + c[0] * (a[1] - b[1]); return p > 0;} // Graham Scan algorithm to find Convex// Hull from given pointsfunction convexHull(v){ // Sort the points v.sort(cmp); let n = v.length; if (n <= 3) return v; // Set starting and ending points as // left bottom and top right let p1 = v[0]; let p2 = v[n - 1]; // Vector to store points in // upper half and lower half let up = [], down = []; // Insert StartingEnding Points up.push(p1); down.push(p1); // Iterate over points for (var i = 1; i < n; i++) { if (i == n - 1 || !ccw(p1, v[i], p2)) { while (up.length > 1 && ccw(up[up.length - 2], up[up.length - 1], v[i])) { // Exclude this point // if we can form better up.pop(); } up.push(v[i]); } if (i == n - 1 || !cw(p1, v[i], p2)) { while (down.length > 1 && cw(down[down.length - 2], down[down.length - 1], v[i])) { // Exclude this point // if we can form better down.pop(); } down.push(v[i]); } } // Combine upper and lower half for (var i = down.length - 2; i > 0; i--) up.push(down[i]); // Remove duplicate points up = new Set(up) up = Array.from(up) // Return the points on Convex Hull return up;} // Function to find if point lies inside// a convex polygonfunction isInside( points, query){ // Include the query point in the // polygon points points.push(query); // Form a convex hull from the points points = convexHull(points); // Iterate over the points // of convex hull for (let x of points) { // If the query point lies // on the convex hull // then it wasn't inside if (x == query) return false; } // Otherwise it was Inside return true;} // Driver Code // Points of the polygon // given in any orderlet n = 7;let points = [[1, 1 ], [2, 1 ], [ 3, 1 ], [ 4, 1 ], [ 4, 2 ], [4, 3 ], [ 4, 4 ]]; // Query Points let query = [ 3, 2 ]; // Check if its inside if (isInside(points, query)) { console.log("YES"); } else { console.log("NO"); } |
Output:
YES
Time Complexity: O(N * log(N)) Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
