Statistics

Problem Statement for "PointInPolygon"

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 " " (quotes for clarity). With exactly one space between and and no leading or trailing spaces.
  • and will consist of an optional minus sign followed by between 1 and 4 digit characters inclusive. There will be no leading zeros.
  • Each and 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

  1. {"0 0", "0 10", "10 10", "10 0"}

    5

    5

    Returns: "INTERIOR"

    A simple example of a square of side 10.

  2. {"0 0", "0 10", "10 10", "10 0"}

    10

    15

    Returns: "EXTERIOR"

    Outside the same square.

  3. {"0 0", "0 10", "10 10", "10 0"}

    5

    10

    Returns: "BOUNDARY"

    On an edge of the square

  4. {"-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

  5. {"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"

  6. {"0 0", "0 1000", "1000 1000","1000 800", "200 800","200 600","600 600", "600 400", "200 400","200 200","1000 200", "1000 0"}

    300

    300

    Returns: "EXTERIOR"

  7. {"0 0", "0 1000", "1000 1000","1000 800", "200 800","200 600","600 600", "600 400", "200 400","200 200","1000 200", "1000 0"}

    0

    500

    Returns: "BOUNDARY"

  8. {"0 1000", "1000 1000","1000 800", "200 800","200 600","600 600", "600 400", "200 400","200 200","1000 200", "1000 0", "0 0"}

    0

    500

    Returns: "BOUNDARY"

  9. {"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"

  10. {"0 1000", "1000 1000","1000 800", "200 800","200 600","600 600", "600 400", "200 400","200 200","1000 200", "1000 0", "0 0"}

    555

    999

    Returns: "INTERIOR"

  11. {"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"

  12. {"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"}

    400

    200

    Returns: "BOUNDARY"

  13. {"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"}

    400

    400

    Returns: "EXTERIOR"

  14. {"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"}

    400

    -400

    Returns: "EXTERIOR"

  15. {"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"}

    -400

    -400

    Returns: "EXTERIOR"

  16. {"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"}

    -400

    400

    Returns: "EXTERIOR"

  17. {"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"}

    42

    42

    Returns: "INTERIOR"

  18. {"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"}

    499

    1

    Returns: "INTERIOR"

  19. {"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", "500 0"}

    200

    200

    Returns: "INTERIOR"

  20. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    1

    -1

    Returns: "INTERIOR"

  21. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    1

    1

    Returns: "EXTERIOR"

  22. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    -1

    1

    Returns: "EXTERIOR"

  23. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    -1

    -1

    Returns: "EXTERIOR"

  24. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    5

    -10

    Returns: "INTERIOR"

  25. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    10

    -15

    Returns: "INTERIOR"

  26. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    15

    0

    Returns: "EXTERIOR"

  27. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    15

    -5

    Returns: "EXTERIOR"

  28. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    10

    5

    Returns: "EXTERIOR"

  29. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    -5

    5

    Returns: "EXTERIOR"

  30. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    -15

    15

    Returns: "INTERIOR"

  31. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    0

    -1

    Returns: "BOUNDARY"

  32. {"0 0","10 0","10 -10","20 -10","20 10", "-10 10","-10 -30","40 -30","40 30","-30 30", "-30 -50","60 -50","60 50","-50 50","-50 -70", "80 -70","80 70","-70 70","-70 -90","100 -90", "100 90","-90 90","-90 -110","120 -110","120 110", "-120 110","-120 120","130 120", "130 -120","-100 -120","-100 100","110 100","110 -100", "-80 -100","-80 80","90 80","90 -80","-60 -80", "-60 60","70 60","70 -60","-40 -60","-40 40", "50 40","50 -40","-20 -40","-20 20","30 20", "30 -20","0 -20"}

    1

    -20

    Returns: "BOUNDARY"

  33. {"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"

  34. { "0 0", "0 10", "10 10", "10 0" }

    5

    10

    Returns: "BOUNDARY"

  35. { "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"

  36. { "0 0", "0 10", "10 10", "10 0" }

    10

    15

    Returns: "EXTERIOR"

  37. { "0 0", "3 0", "3 4", "-2 4", "-2 0", "-1 0", "-1 3", "2 3", "2 1", "0 1" }

    1

    2

    Returns: "EXTERIOR"

  38. { "0 0", "0 10", "10 10", "10 0" }

    10

    10

    Returns: "BOUNDARY"

  39. { "0 0", "0 1", "1 1", "1 0" }

    0

    10

    Returns: "EXTERIOR"

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: