Statistics

Problem Statement for "Boxes"

Problem Statement

In computer graphics, determining if two polygons intersect is very important but is also very resource intensive (O(N^2)). Often, to save time, it is first determined if the bounding boxes of the two polygons intersect. If the bounding boxes do not intersect it is very quickly (O(1), once the bounding boxes are known) known that the polygons don't intersect. If the bounding boxes do intersect, the program can go on to more expensive operations to determine if the actual polygons intersect.

The bounding box B of a polygon P is the smallest rectangle that has sides parallel to the vertical and horizontal axis such that P lies entirely within or on the edges of B. The smallest rectangle is defined as the rectangle with the shortest diagonal (distance between opposite corners). Note the bounding box may have area 0. In this case the bounding box is either a line segment or a point. If the bounding box is a line segment, the length of the diagonal is the length of the segment and the segment must be either vertical or horizontal. If the bounding box is a point, the length of the diagonal is 0.

You are to write a program which takes two String[]'s, poly1 and poly2 as parameters which contain the vertices of two polygons and returns a String that is

  • "NESTED" if one bounding box is entirely nested within the other and neither bounding box has an intersection or a tangency with the other.
  • "SEGMENT" if the two bounding boxes share at least one line segment (intersect at infinitely many points)
  • "POINT" if the two bounding boxes intersect at exactly one point and share 0 line segments.
  • "POINTS" if the two bounding boxes intersect at more than one point but share 0 line segments (intersect at a finite number of points).
  • "NONE" if the bounding boxes of the two polygons do not intersect, do not share a line segment, and are not nested.

Each element of poly1 and poly2 are of the form "<x>,<y>" where x and y are integers between -1000 and 1000, inclusive. x and y may contain leading zeros.
The first polygon is the polygon connecting the point poly1[0] to poly1[1] to ... to poly1[LAST] to poly1[0], where LAST is one less than the number of vertices in the polygon.
The second polygon is the polygon connecting the point poly2[0] to poly2[1] to ... to poly2[LAST] to poly2[0], where LAST is one less than the number of vertices in the polygon.

Definition

Class:
Boxes
Method:
check
Parameters:
String[], String[]
Returns:
String
Method signature:
String check(String[] poly1, String[] poly2)
(be sure your method is public)

Notes

  • The shapes described by poly1 and poly2 may be self-intersecting, or have 0 area, or have duplicate vertices (no guarantee about the shapes of the polygons).
  • There is an implied line segment (possibly of 0 length) connecting the last and first vertex in each polygon.
  • In computing intersection, the bounding box refers only to the boundary of the box, not the area inside.

Constraints

  • poly1 and poly2 will both contain between 1 and 50 elements, inclusive.
  • Each element of poly1 and poly2 will be formatted exactly as "," (quotes and angle brackets for clarity only).
  • and will both be between -1000 and 1000, inclusive (leading zeroes allowed).

Examples

  1. {"0,0","4,0","2,2"}

    {"-5,-02","-5,-02","-3,-02","-5,-02"}

    Returns: "NONE"

    The bounding box for poly1 is the rectangle with a diagonal (0,0) - (4,2) and the bounding box for poly2 is just a line (-5,-2) - (-3, -2). There is no intersection of the bounding boxes here so the method returns "NONE".

  2. {"0,0","4,0","3,3"}

    {"1,1","1,2","2,2","2,1"}

    Returns: "NESTED"

    The bounding box for poly1 is the rectangle with a diagonal (0,0) - (4,3) and the bounding box for poly2 is the rectangle with a diagonal (1,1) - (2,2). The bounding box for poly2 is inside that for poly1 so the method returns "NESTED".

  3. {"0,0","4,0","2,2"}

    {"1,001","1,02","2,2","2,1"}

    Returns: "SEGMENT"

    The bounding box for poly1 is the rectangle with a diagonal (0,0) - (4,2) and the bounding box for poly2 is the rectangle with a diagonal (1,1) - (2,2). These two bounding boxes share the line segment (1,2) - (2,2) so the method returns "SEGMENT".

  4. {"0,0","4,0","2,2"}

    {"1,1","1,3","2,2","2,1"}

    Returns: "POINTS"

    The bounding box for poly1 is the rectangle with a diagonal (0,0) - (4,2) and the bounding box for poly2 is the rectangle with a diagonal (1,1) - (2,3). These two bounding boxes intersect at (1,2) and (2,2), so the method returns "POINTS".

  5. {"0,0","4,0","2,2"}

    {"1,1","1,3","1,1","1,1"}

    Returns: "POINT"

    The bounding box for poly1 is the rectangle with a diagonal (0,0) - (4,2) and the bounding box for poly2 is just a line from (1,1) - (1,3). This line intersects poly1's bounding box at (1,2) so the method returns "POINT".

  6. {"0,0","1,1"}

    {"1,1","2,1","3,2","4,4","1,10"}

    Returns: "POINT"

    The bounding boxes intersect at (1,1) so the method returns "POINT".

  7. {"-10,-8","2,2"}

    {"-800,-600","-400,-100","-100,-800","-800,-600","-1000,2","-10,-1000"}

    Returns: "SEGMENT"

  8. {"-10,-8","2,2"}

    {"-800,-600","-400,-100","-100,-800","-800,-600","-1000,-8","-10,-1000"}

    Returns: "POINT"

  9. {"-10,-10","10,1","1,10"}

    {"0,-999","0,999"}

    Returns: "POINTS"

  10. {"-362,-332","-436,-130","296,393","-847,514","-599,124","501,6","501,691","-490,8","-710,-234","-367,251","-891,-478","459,-851","-374,-273","-550,149","-449,486","174,226","110,-373","-447,-37","556,248","-379,-191","548,-304","-573,-459","629,256","463,-391","-59,286","101,-548","-147,139","-200,-718","-187,294","-569,-297","-257,-371","-508,718","53,140","-383,-450","-330,-144","-282,270","-343,-192","148,-191","-40,-145","391,-68","-108,-703","-559,-58","-277,-856","174,232","-885,-576","80,-267","-351,108"}

    {"-362,-332","-436,-130","296,393","-847,514","-599,124","501,6","501,691","-490,8","-710,-234","-367,251","-891,-478","459,-851","-374,-273","-550,149","-449,486","174,226","110,-373","-447,-37","556,248","-379,-191","548,-304","-573,-459","629,256","463,-391","-59,286","101,-548","-147,139","-200,-718","-187,294","-569,-297","-257,-371","-508,718","53,140","-383,-450","-330,-144","-282,270","-343,-192","148,-191","-40,-145","391,-68","-108,-703","-559,-58","-277,-856","174,232","-885,-576","80,-267","-351,108"}

    Returns: "SEGMENT"

  11. {"0,0","1,1"}

    {"0,0","1,1"}

    Returns: "SEGMENT"

    The bounding boxes are the same and share four line segments so the method returns "SEGMENT".

  12. {"-393,-151","-188,1","-436,558","125,-226","409,490","169,-226","8,520","-695,-701","-298,206","-44,-651","498,-363","231,-586","584,908","-823,-113","-549,98","102,271","-461,568","869,846","-212,739"}

    {"499,-729","56,309","-254,215","305,-546","241,197","72,507","-972,386","-364,-279","-701,-578","-298,343","241,150","214,-362","508,189","-914,-66","-207,-681","-793,227","-89,676","531,479","-587,-185","-249,-342","73,-465","7,-234","-543,-27","-726,-490","382,-167","-501,-731","477,186","-937,-213","-782,107","100,-388","-477,-269","-404,-485"}

    Returns: "POINTS"

  13. {"471,-232","348,-552","272,245","168,-876","360,644","-124,-767","-508,899","752,112","-521,60","-395,-97","170,-739","-518,314","44,384","-812,-678","-825,-184","681,394","271,225","-648,-131","-445,-827","199,-529","-144,546","-153,-306","84,-134","-156,-628","-157,-790","536,119","690,-580","475,302","-115,-195","128,-961","-31,203","367,-729","398,-754","117,450","532,212","-303,514","647,-369","640,-465","-589,-531","-273,-325","-75,656","498,307","-221,146"}

    {"-793,341","17,-195","740,275","189,-165","-237,-569","-769,-465","440,-631","-372,115","-689,449","482,-352","703,-360","-174,635","-249,-701","-738,-133","-925,801","-422,63","-581,-698","-681,-345","-417,98","294,31","-75,-526","236,741","-304,508","-40,-700","-771,218","-291,311","319,-652","-392,188","-418,641","776,-207","458,-16","463,702","-763,488","-330,-83"}

    Returns: "POINTS"

  14. {"-1,1","1,-1"}

    {"-2,2","2,-2"}

    Returns: "NESTED"

  15. {"58,357","-411,-648","-776,-326","-496,-381","124,47","-929,304","-214,-76","-210,-2","-299,-234","-566,-493","592,588","236,-293","60,-944","-711,-227","58,406","-765,-330","148,-185","-552,-79","-589,122","-150,124","-714,-634","26,-593","-305,338","-53,638","-303,-164","147,-145","-917,-265","-21,593","640,-154","-720,452","-875,495","-117,-390","433,-314","-163,-613","-736,-145","212,-82","-431,-238","-270,-752","-422,782","-406,229","-536,-473","109,-594","-805,95","-232,119","-70,-802","485,240","-802,342"}

    {"1,1"}

    Returns: "NESTED"

  16. {"58,357","-411,-648","-776,-326","-496,-381","124,47","-929,304","-214,-76","-210,-2","-299,-234","-566,-493","592,588","236,-293","60,-944","-711,-227","58,406","-765,-330","148,-185","-552,-79","-589,122","-150,124","-714,-634","26,-593","-305,338","-53,638","-303,-164","147,-145","-917,-265","-21,593","640,-154","-720,452","-875,495","-117,-390","433,-314","-163,-613","-736,-145","212,-82","-431,-238","-270,-752","-422,782","-406,229","-536,-473","109,-594","-805,95","-232,119","-70,-802","485,240","-802,342"}

    {"1000,1000"}

    Returns: "NONE"

  17. {"58,357","-411,-648","-776,-326","-496,-381","124,47","-929,304","-214,-76","-210,-2","-299,-234","-566,-493","592,588","236,-293","60,-944","-711,-227","58,406","-765,-330","148,-185","-552,-79","-589,122","-150,124","-714,-634","26,-593","-305,338","-53,638","-303,-164","147,-145","-917,-265","-21,593","640,-154","-720,452","-875,495","-117,-390","433,-314","-163,-613","-736,-145","212,-82","-431,-238","-270,-752","-422,782","-406,229","-536,-473","109,-594","-805,95","-232,119","-70,-802","485,240","-802,342"}

    {"-665,458","-70,-333","-133,-102","105,-716","433,-280","570,-880","-954,-904","-216,-393","-503,195","-682,-828","122,-769","-697,390","278,-435","-150,-674","-567,56","-653,-503","-108,-498","-630,-696","-494,363","-990,-473","-162,513","-694,-42","207,161","-589,-816","-447,-594","770,199","295,-647","-478,-826","-30,40","-246,-542","70,-936","-821,387","269,-236","702,799","-315,326","-827,-445","142,-783"}

    Returns: "POINTS"

  18. {"100,100","-100,-100","3,3"}

    {"88,56","99,56","765,56"}

    Returns: "POINT"

  19. {"-100,-100","100,100","85,12"}

    {"88,56","99,56","-765,56"}

    Returns: "POINT"

  20. {"0,0","4,0","3,3"}

    {"1,1","1,2","2,2","2,1"}

    Returns: "NESTED"

  21. {"-2,-1","2,1"}

    {"-1,-2","1,2"}

    Returns: "POINTS"

  22. {"-999,-999","-999,-999"}

    {"-999,-999","-999,-999"}

    Returns: "POINT"

  23. {"1,1"}

    {"0,1","2,1"}

    Returns: "POINT"

  24. {"0,0"}

    {"0,0"}

    Returns: "POINT"

  25. {"0,8","0,0","0,7"}

    {"0,0"}

    Returns: "POINT"

  26. {"1,1"}

    {"0,1","2,1"}

    Returns: "POINT"

  27. {"0,0","4,0","4,4","0,4"}

    {"2,2","2,4"}

    Returns: "POINT"

  28. {"1,1","2,2","3,3"}

    {"1,1","2,2","3,3"}

    Returns: "SEGMENT"

  29. {"0,1","0,2"}

    {"01,02","4,5"}

    Returns: "NONE"

  30. {"0,0","4,0","4,4","0,4"}

    {"2,2","2,4"}

    Returns: "POINT"

  31. {"0,0","1,1"}

    {"1,1","2,1","3,2","4,4","1,10"}

    Returns: "POINT"

  32. {"0,0","0,0"}

    {"-1,0","1,0"}

    Returns: "POINT"

  33. {"1000,1000"}

    {"999,999"}

    Returns: "NONE"

  34. {"1,1"}

    {"0,0"}

    Returns: "NONE"

  35. {"0,0","2,0","2,2","0,2"}

    {"0,1","2,1"}

    Returns: "POINTS"

  36. {"1,1"}

    {"0,1","2,1"}

    Returns: "POINT"

  37. {"0,0","4,-00","4,4"}

    {"2,4"}

    Returns: "POINT"

  38. {"-10,-1","30,50"}

    {"30,50","20,40"}

    Returns: "SEGMENT"

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

    {"4,0","-1,0"}

    Returns: "SEGMENT"

  40. {"0,0","900,900"}

    {"1,1","0,0"}

    Returns: "SEGMENT"

  41. {"-999,-999","999,999","12,72","72,12","1,4","32,-999","32,999","32,23"}

    {"32,-999","32,999","32,23","32,-123"}

    Returns: "POINTS"

  42. {"-999,-999","999,999","12,72","72,12","1,4","32,-999","32,999","32,23"}

    {"-999,32","999,32"}

    Returns: "POINTS"

  43. {"0,0","4,0","2,2"}

    {"1,1","1,3","1,1","1,1"}

    Returns: "POINT"

  44. {"0,0","2,2"}

    {"1,2","3,3"}

    Returns: "SEGMENT"

  45. {"0,0"}

    {"0,0"}

    Returns: "POINT"

  46. {"0,0","4,4"}

    {"2,0","2,6"}

    Returns: "POINTS"

  47. {"5,0","5,10"}

    {"0,0","10,10"}

    Returns: "POINTS"

  48. {"0,2","4,4"}

    {"1,1","1,2"}

    Returns: "POINT"

  49. {"0,000","1,000"}

    {"2,000","3,000"}

    Returns: "NONE"

  50. {"0,0","0,2","2,2"}

    {"0,1"}

    Returns: "POINT"

  51. {"0,0","4,4"}

    {"1,2","5,2"}

    Returns: "POINT"

  52. {"1,1","0,0"}

    {"1,1","0,0"}

    Returns: "SEGMENT"

  53. {"0,0","2,2","0,2","2,0"}

    {"0,1"}

    Returns: "POINT"

  54. {"0,0","0,2"}

    {"-1,1","1,1"}

    Returns: "POINT"

  55. {"1,1","1,3","3,3","3,1"}

    {"0,0","0,5","5,5","5,0"}

    Returns: "NESTED"

  56. {"0,0","2,2"}

    {"1,1","1,3"}

    Returns: "POINT"

  57. {"0,0","4,0","4,4","0,4"}

    {"2,2","2,4"}

    Returns: "POINT"

  58. {"0,0","3,5"}

    {"0,1","1,1"}

    Returns: "POINT"

  59. {"0,0","2,2"}

    {"0,1","0,1","0,1"}

    Returns: "POINT"

  60. {"0,0","4,0","2,2"}

    {"1,001","1,02","2,2","2,1"}

    Returns: "SEGMENT"

  61. {"0,0","3,3","6,0"}

    {"10,0","13,3","16,0"}

    Returns: "NONE"

  62. {"0,0","2,2"}

    {"0,1","2,1"}

    Returns: "POINTS"

  63. {"107,-751","-227,-289","-231,-471","491,-462","284,342","-839,-547","183,456","-392,-500","517,281","-441,-717","-590,-211","-818,-406","723,433","-330,175","166,313","-380,-164","-571,59","-129,-719","23,-287","78,278","-459,-614","-580,-36","527,26","148,-109","-799,-437","684,-718","-149,-103","631,31","-465,-628","-656,-441","-597,-47","-83,-215","394,208","-582,226","254,515","4,-725","-125,64","308,-543","-172,149","-250,36","-588,-800","-898,-656","613,823","-46,-129","408,298"}

    {"-1,136","-715,558","-314,-710","-472,719","-535,-52","-668,639","5,403","-493,-157","-430,133","519,154","-2,-25","-565,562","-594,-909","-796,-596","163,-234","414,464","-401,-457","285,-610","-136,-579","-120,13","186,52","521,-907","-257,8","73,-352","736,-804","86,-632","834,-270","483,-429","-473,270","-258,180","172,-595"}

    Returns: "POINTS"

  64. {"551,-117","-637,96","-198,-503","-401,233","-105,-459","-95,-637","-47,-434","-265,-663","-276,-548","-377,-823","649,748","-370,-674","816,163","493,-111","-206,967","-441,-82","-110,-339","-777,634","-580,503","-169,-562","-250,-747","-409,-495","-553,292","-662,-650","-49,-627","-40,43","-733,475","-253,-535","-395,-744","-116,-579","-553,242","-732,373","-839,-579","-226,-929","-453,553","732,-579","-574,-575","69,-481"}

    {"-961,429","-484,-188","860,-247","238,551","552,-75","238,-715","212,235","775,482","-689,-302","-840,-114","-434,-117","0,55","581,-359","-501,129","-251,464","-617,529","335,-466","-622,434","-10,134","142,-829","-804,99","-423,-544","-775,-357","6,-6","-387,-22","-515,-860","-246,-724","184,-565","-704,-173","-925,662","451,-650","337,-650","-289,-691","114,-191","-622,-417"}

    Returns: "POINTS"

  65. {"101,826","-492,-177","498,-934","361,-662","74,19","-433,-599","-912,165","-429,58"}

    {"307,281","98,-438","-223,-124","-700,-490","-631,6","-108,-872","-723,-707","605,760","185,-81","-434,109","-638,-922","-135,20"}

    Returns: "POINTS"

  66. {"0,0","10,0"}

    {"5,-5","5,5"}

    Returns: "POINT"

  67. {"0,0","2,2"}

    {"-1,1","3,1"}

    Returns: "POINTS"

  68. {"0,0","3,5"}

    {"0,1","1,1"}

    Returns: "POINT"

  69. {"0,0","4,0","2,2","0,0","4,0"}

    {"1,1","1,3","1,1","-5,-02","-3,-02","-5,-02"}

    Returns: "POINTS"

  70. {"0,0","1,1","0,1","1,0"}

    {"1,0","1,1","2,1","2,0"}

    Returns: "SEGMENT"

  71. {"0,0","10,10"}

    {"5,5","20,5"}

    Returns: "POINT"

  72. {"0,0","4,0","4,4","0,4"}

    {"2,4","2,2"}

    Returns: "POINT"

  73. {"0,0","4,0","4,4","0,4"}

    {"2,2","2,4"}

    Returns: "POINT"

  74. {"0,0","2,0","2,2","0,2"}

    {"0,1","2,1"}

    Returns: "POINTS"

  75. {"1,1","5,2","3,5"}

    {"5,2","3,5","6,5"}

    Returns: "SEGMENT"

  76. {"0,0","1,1"}

    {"2,0","3,1"}

    Returns: "NONE"

  77. {"0,4","0,0"}

    {"0,2","0,-1"}

    Returns: "SEGMENT"

  78. {"-2,0","-2,-2","-4,-2","-4,0"}

    {"0,0","3,0","3,-2","0,-2"}

    Returns: "NONE"

  79. {"0,0","3,5"}

    {"0,1","1,1"}

    Returns: "POINT"

  80. {"0,0","4,0","2,2"}

    {"1,1","1,3","1,1","1,1"}

    Returns: "POINT"

  81. {"0,0","0,1","1,2"}

    {"0,1","1,1"}

    Returns: "POINTS"

  82. {"0,0","5,5"}

    {"0,2","2,2"}

    Returns: "POINT"

  83. {"0,0","2,2"}

    {"0,1"}

    Returns: "POINT"

  84. {"0,0","0,3","3,0","3,3"}

    {"1,3"}

    Returns: "POINT"

  85. {"1,0","2,0","2,1","1,1"}

    {"0,1","1,1","1,2","0,2"}

    Returns: "POINT"

  86. {"1,1"}

    {"1,1"}

    Returns: "POINT"

  87. {"0,0","1,0","0,2","1,2"}

    {"1,1","2,1"}

    Returns: "POINT"

  88. {"0,0","1,0"}

    {"1,1","1,-1"}

    Returns: "POINT"

  89. {"0,0","0,0"}

    {"0,0","0,0"}

    Returns: "POINT"

  90. {"0,1","0,2"}

    {"1,1","2,2"}

    Returns: "NONE"

  91. {"0,0","0,2","2,2","2,0"}

    {"2,1"}

    Returns: "POINT"

  92. {"0,0","4,4"}

    {"1,0","1,3"}

    Returns: "POINT"

  93. {"-1,-1","1,1"}

    {"0,-1","0,1"}

    Returns: "POINTS"

  94. {"0,0","4,4"}

    {"2,0","2,6"}

    Returns: "POINTS"

  95. {"1,1","1,5","5,1","5,5"}

    {"1,3","6,3"}

    Returns: "POINTS"

  96. {"5,5"}

    {"4,5","10,5"}

    Returns: "POINT"

  97. {"0,0","4,0","2,2"}

    {"1,1","1,3","2,2","2,1"}

    Returns: "POINTS"

  98. {"0,0","1,1"}

    {"1,1","0,2"}

    Returns: "SEGMENT"

  99. {"0,0","2,0"}

    {"0,0","2,0","2,2"}

    Returns: "SEGMENT"

  100. {"0,0","3,0","3,3","0,3"}

    {"1,2","4,2"}

    Returns: "POINT"

  101. {"5,5"}

    {"4,5","10,5"}

    Returns: "POINT"

  102. {"0,0","4,0","4,4","0,4"}

    {"2,4","2,4","2,4","2,4"}

    Returns: "POINT"

  103. {"0,0","0,4"}

    {"-2,2","2,3"}

    Returns: "POINTS"

  104. {"0,0","2,2"}

    {"1,3","1,2"}

    Returns: "POINT"

  105. {"0,0","0,10","10,0","10,10"}

    {"5,5","5,6","5,10"}

    Returns: "POINT"

  106. {"0,0","2,2"}

    {"1,0","1,2"}

    Returns: "POINTS"

  107. {"0,0","2,0"}

    {"1,0"}

    Returns: "POINT"

  108. {"1,1","3,3"}

    {"2,0","2,4"}

    Returns: "POINTS"

  109. {"0,0","0,5","5,5","5,0"}

    {"0,2","5,2"}

    Returns: "POINTS"

  110. {"0,0","2,2"}

    {"0,1","1,3"}

    Returns: "SEGMENT"

  111. {"0,0","2,2"}

    {"1,-2","1,1"}

    Returns: "POINT"

  112. {"0,0","2,2"}

    {"1,1"}

    Returns: "NESTED"

  113. {"1,1","0,0"}

    {"1,1","0,0"}

    Returns: "SEGMENT"

  114. {"0,0","4,4"}

    {"2,0","2,6"}

    Returns: "POINTS"

  115. {"0,0","10,0","10,-10","0,-10"}

    {"5,0","5,5"}

    Returns: "POINT"

  116. {"0,0","2,2"}

    {"1,1","1,30"}

    Returns: "POINT"

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: