Problem Statement |
| | Given a test point, (testPointX, testPointY), and the vertices of a simple polygon, vertices, determine if the test point is in the interior, in the exterior or on the boundary of the polygon. Return the String "INTERIOR", "EXTERIOR", or "BOUNDARY".
For simplicity, all sides of the polygon will be horizontal or vertical, and the vertices and the test
point will all be at integer coordinates. The x and y coordinates of the vertices will given in the String[] vertices where each element represents a single vertex, formatted as "<x> <y>". There is an edge from vertices[i] to vertices[i+1] for i from 0 to n-2, and an edge from vertices[n-1] to vertices[0] where n is the number of vertices (and the number of edges) in the polygon. |
| |
Definition |
| | | Class: | PointInPolygon | | Method: | testPoint | | Parameters: | String[], int, int | | Returns: | String | | Method signature: | String testPoint(String[] vertices, int testPointX, int testPointY) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | A simple polygon is a polygon that may or may not be convex, but self-intersection is not allowed. Not even at a single point. |
| |
Constraints |
| - | vertices will contain an even number of elements between 4 and 50 inclusive. |
| - | Each element of vertices is formatted as follows "<x> <y>" (quotes for clarity). With exactly one space between <x> and <y> and no leading or trailing spaces. |
| - | <x> and <y> will consist of an optional minus sign followed by between 1 and 4 digit characters inclusive. There will be no leading zeros. |
| - | Each <x> and <y> value in each element of vertices will be between -1000 and 1000 inclusive. |
| - | The elements of vertices taken in order will specify the vertices of a valid simple polygon. |
| - | Each edge of this polygon will be either exactly horizontal or exactly vertical. |
| - | No three consecutive vertices will be colinear. |
| - | No two elements of vertices will be the same. |
| - | No edges will overlap or intersect, except where adjacent edges meet pairwise at vertices. |
| - | testPointX and testPointY will both be between -1000 and 1000 inclusive |
| |
Examples |
| 0) | |
| | {"0 0",
"0 10",
"10 10",
"10 0"} | 5 | 5 |
| Returns: "INTERIOR" | | A simple example of a square of side 10. |
|
|
| 1) | |
| | {"0 0",
"0 10",
"10 10",
"10 0"} | 10 | 15 |
| Returns: "EXTERIOR" | |
|
| 2) | |
| | {"0 0",
"0 10",
"10 10",
"10 0"} | 5 | 10 |
| Returns: "BOUNDARY" | |
|
| 3) | |
| | {"-100 -90", "-100 100","100 100", "100 -100",
"-120 -100","-120 100","-130 100","-130 -110",
"110 -110", "110 110", "-110 110","-110 -90"} | 0 | 0 |
| Returns: "EXTERIOR" | 
A more complex geometry |
|
|
| 4) | |
| | {"0 0","0 1000","1000 1000","1000 800",
"200 800","200 600","600 600","600 400",
"200 400","200 200","1000 200","1000 0"} | 100 | 500 |
| Returns: "INTERIOR" | |
|
| 5) | |
| | {"0 1000","1000 1000","1000 800",
"200 800","200 600","600 600","600 400",
"200 400","200 200","1000 200","1000 0","0 0"} | 322 | 333 |
| Returns: "EXTERIOR" | |
|
| 6) | |
| | {"500 0","500 100","400 100","400 200","300 200",
"300 300","200 300","200 400","100 400","100 500",
"0 500","0 400","-100 400","-100 300","-200 300",
"-200 200","-300 200","-300 100","-400 100","-400 0",
"-500 0","-500 -100","-400 -100","-400 -200","-300 -200",
"-300 -300","-200 -300","-200 -400","-100 -400","-100 -500",
"0 -500","0 -400","100 -400","100 -300","200 -300",
"200 -200","300 -200","300 -100","400 -100","400 0"} | 200 | 200 |
| Returns: "INTERIOR" | |
|
| 7) | |
| | {"1 0","2 0","2 1","3 1","3 0","4 0","4 -1","5 -1","5 0",
"6 0","6 2","0 2","0 3","-1 3","-1 4","0 4","0 6","1 6",
"1 7","0 7","0 8","-2 8","-2 2","-8 2","-8 0","-7 0",
"-7 -1","-6 -1","-6 0","-4 0","-4 1","-3 1","-3 0",
"-2 0","-2 -6","0 -6","0 -5","1 -5","1 -4","0 -4",
"0 -3","-1 -3","-1 -2","0 -2","0 -1","1 -1"} | 0 | 0 |
| Returns: "INTERIOR" | |
|
