fork download
copy 
  1. // A C++ program to check if a given point lies inside a given polygon
  2. // Refer https://w...content-available-to-author-only...s.org/check-if-two-given-line-segments-intersect/
  3. // for explanation of functions onSegment(), orientation() and doIntersect()
  4. #include <iostream>
  5. using namespace std;
  6.  
  7. // Define Infinite (Using INT_MAX caused overflow problems)
  8. #define INF 10000
  9.  
  10. struct Point
  11. {
  12. 	int x;
  13. 	int y;
  14. };
  15.  
  16. // Given three colinear points p, q, r, the function checks if
  17. // point q lies on line segment 'pr'
  18. bool onSegment(Point p, Point q, Point r)
  19. {
  20. 	if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
  21. 			q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
  22. 		return true;
  23. 	return false;
  24. }
  25.  
  26. // To find orientation of ordered triplet (p, q, r).
  27. // The function returns following values
  28. // 0 --> p, q and r are colinear
  29. // 1 --> Clockwise
  30. // 2 --> Counterclockwise
  31. int orientation(Point p, Point q, Point r)
  32. {
  33. 	int val = (q.y - p.y) * (r.x - q.x) -
  34. 			(q.x - p.x) * (r.y - q.y);
  35.  
  36. 	if (val == 0) return 0; // colinear
  37. 	return (val > 0)? 1: 2; // clock or counterclock wise
  38. }
  39.  
  40. // The function that returns true if line segment 'p1q1'
  41. // and 'p2q2' intersect.
  42. bool doIntersect(Point p1, Point q1, Point p2, Point q2)
  43. {
  44. 	// Find the four orientations needed for general and
  45. 	// special cases
  46. 	int o1 = orientation(p1, q1, p2);
  47. 	int o2 = orientation(p1, q1, q2);
  48. 	int o3 = orientation(p2, q2, p1);
  49. 	int o4 = orientation(p2, q2, q1);
  50.  
  51. 	// General case
  52. 	if (o1 != o2 && o3 != o4)
  53. 		return true;
  54.  
  55. 	// Special Cases
  56. 	// p1, q1 and p2 are colinear and p2 lies on segment p1q1
  57. 	if (o1 == 0 && onSegment(p1, p2, q1)) return true;
  58.  
  59. 	// p1, q1 and p2 are colinear and q2 lies on segment p1q1
  60. 	if (o2 == 0 && onSegment(p1, q2, q1)) return true;
  61.  
  62. 	// p2, q2 and p1 are colinear and p1 lies on segment p2q2
  63. 	if (o3 == 0 && onSegment(p2, p1, q2)) return true;
  64.  
  65. 	// p2, q2 and q1 are colinear and q1 lies on segment p2q2
  66. 	if (o4 == 0 && onSegment(p2, q1, q2)) return true;
  67.  
  68. 	return false; // Doesn't fall in any of the above cases
  69. }
  70.  
  71. // Returns true if the point p lies inside the polygon[] with n vertices
  72. bool isInside(Point polygon[], int n, Point p)
  73. {
  74. 	// There must be at least 3 vertices in polygon[]
  75. 	if (n < 3) return false;
  76.  
  77. 	// Create a point for line segment from p to infinite
  78. 	Point extreme = {INF, p.y};
  79.  
  80. 	// Count intersections of the above line with sides of polygon
  81. 	int count = 0, i = 0;
  82. 	do
  83. 	{
  84. 		int next = (i+1)%n;
  85.  
  86. 		// Check if the line segment from 'p' to 'extreme' intersects
  87. 		// with the line segment from 'polygon[i]' to 'polygon[next]'
  88. 		if (doIntersect(polygon[i], polygon[next], p, extreme))
  89. 		{
  90. 			// If the point 'p' is colinear with line segment 'i-next',
  91. 			// then check if it lies on segment. If it lies, return true,
  92. 			// otherwise false
  93. 			if (orientation(polygon[i], p, polygon[next]) == 0)
  94. 			return onSegment(polygon[i], p, polygon[next]);
  95.  
  96. 			count++;
  97. 		}
  98. 		i = next;
  99. 	} while (i != 0);
  100.  
  101. 	// Return true if count is odd, false otherwise
  102. 	return count&1; // Same as (count%2 == 1)
  103. }
  104.  
  105. // Driver program to test above functions
  106. int main()
  107. {
  108. 	Point polygon1[] = {{10000, 11111111}, {20000 , 22222222}, {40009 , 44454444}, {50018 ,  55575555},{50027 ,  55585555},{30045 ,  33383333},{20045  , 22272222},{10036  , 11151111},{18  ,    20000},{9 ,   10000}};
  109. 	int n = sizeof(polygon1)/sizeof(polygon1[0]);
  110. 	Point p = {10 , 11112};
  111. 	isInside(polygon1, n, p)? cout << "Yes \n": cout << "No \n";
  112.  
  113. 	return 0;
  114. }
  115.  
Success #stdin #stdout 0s 4472KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Yes
https://ideone.com/X0a5qd
language:
C++14 (gcc 8.3)
created:
6 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!