Implement in Java Goal: Given an ordered of points which represent a polygon, re

Question

Implement in Java

Goal: Given an ordered of points which represent a polygon, return the number of points with integer (x, y) coordinates enclosed by the polygon. Provide a RESTful service which accepts as a POST of JSON an ordered list of points represented as (x, y) coordinates. The points define the perimeter of a polygone. Return the number of points with integer (x, y) coordinates which are fully enclosed by the polygon. Points on the polygon itself are not included in the count - the points to be included in the count the must be wholly within the area bounded by the polygon. For example, assuming all points in the grid below are integers, the result would be "13", as points on the polygon itself are not included. The grid is at maximum 19 times 19. You can assume all points on the polygon are positive integers between 0 and 18 inclusive. Example input: {"inList": [:"x":2, "y": 1}, {"x": 2, "y": 4}:"x": 11, "y": 1} {"x": 8, "y": 4}] } Example output: {"count": 13} Erroneous input (e.g. malformed JSON) should be handled gracefully. Deliverables: Submit to the Blackboard by the due date: An HTTP URL to a RESTful service which must remain up and running 24/7 until grading is complete. Graders will invoke your service with a tool such as curl or Postman at a time of their choosing. AZIP file containing your source code, written in any language you choose.

Explanation / Answer

#include <iostream>
using namespace std;
#define INF 10000
struct Point
{
   int x;
   int y;
};
static int final_count;
// for three colinear points p, q, r, the function checks if point q lies on line segment 'pr'
bool on_Segment(Point p, Point q, Point r)
{
   if (q.x <= max(p.x, r.x) && q.x >= min(p.x, r.x) &&
           q.y <= max(p.y, r.y) && q.y >= min(p.y, r.y))
       return true;
   return false;
}

// To find orientation of ordered triplet (p, q, r).
// 0 --> p, q and r are colinear
// 1 --> Clockwise
// 2 --> Counterclockwise
int orientation_as(Point p, Point q, Point r)
{
   int val = (q.y - p.y) * (r.x - q.x) -
           (q.x - p.x) * (r.y - q.y);

   if (val == 0) return 0; // points are colinear
   return (val > 0)? 1: 2;
}

// The function that returns true if line segment 'p1q1' and 'p2q2' intersect.
bool doIntersect(Point p1, Point q1, Point p2, Point q2)
{
   // Find the four orientations needed for general and
   // special cases
   int o1 = orientation_as(p1, q1, p2);
   int o2 = orientation_as(p1, q1, q2);
   int o3 = orientation_as(p2, q2, p1);
   int o4 = orientation_as(p2, q2, q1);

   if (o1 != o2 && o3 != o4)
       return true;

   // p1, q1 and p2 are colinear and p2 lies on segment p1q1
   if (o1 == 0 && on_Segment(p1, p2, q1)) return true;

   // p1, q1 and p2 are colinear and q2 lies on segment p1q1
   if (o2 == 0 && on_Segment(p1, q2, q1)) return true;

   // p2, q2 and p1 are colinear and p1 lies on segment p2q2
   if (o3 == 0 && on_Segment(p2, p1, q2)) return true;

   // p2, q2 and q1 are colinear and q1 lies on segment p2q2
   if (o4 == 0 && on_Segment(p2, q1, q2)) return true;

   return false; // Doesn't fall in any of the above cases
}

// Returns true if the point p lies inside the polygon[] with n vertices
bool isInside(Point polygon[], int n, Point p)
{
   // There must be at least 3 vertices in polygon[]
   if (n < 3) return false;
   // Create a point for line segment from p to infinite
   Point extreme = {INF, p.y};
   // Count intersections of the above line with sides of polygon
   int count = 0, i = 0;
   do
   {
       int next = (i+1)%n;

       // Check if the line segment from 'p' to 'extreme' intersects
       // with the line segment from 'polygon[i]' to 'polygon[next]'
       if (doIntersect(polygon[i], polygon[next], p, extreme))
       {
           // If the point 'p' is colinear with line segment 'i-next',
           // then check if it lies on segment. If it lies, return true,
           // otherwise false
           if (orientation_as(polygon[i], p, polygon[next]) == 0)
           return on_Segment(polygon[i], p, polygon[next]);

           count++;
       }
       i = next;
   } while (i != 0);

   // Return true if count is odd, false otherwise
   //cout<<"count&1 _-->"<<count&1;
   if(count&1)
   {
       final_count=final_count+1;  
   }
   return count&1; // Same as (count%2 == 1)
}

int main()
{
   Point polygon1[] = {{0, 0}, {10, 0}, {10, 10}, {0, 10}};
   int n = sizeof(polygon1)/sizeof(polygon1[0]);
  
   Point p = {4, 5};
    cout<<isInside(polygon1, n, p)<<" ";
   p = {5, 5};
   //isInside(polygon1, n, p)? cout << "Yes ": cout << "No ";
   cout<<isInside(polygon1, n, p)<<" ";
   cout<<" No. of points : "<<final_count;

   return 0;
}

-------------------------------------------------------------------------

//code to read input from JSOn file

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.