apprenda take home assessment
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

202 lines
5.1 KiB

  1. package rect
  2. import (
  3. "math"
  4. "sort"
  5. )
  6. // Rectangle struct defines a plane figure with four straight sides
  7. // and four right angles, which contains 4 vertixes points, P1 through P4
  8. type Rectangle struct {
  9. P1, P2, P3, P4 Point
  10. }
  11. // maximum error used for floating point math
  12. var ɛ = 0.00001
  13. // IsRect determins if the rectangle provided really is a rectangle, which
  14. // by definition means a plane figure with four straight sides and four
  15. // right angles.
  16. func (r Rectangle) IsRect() bool {
  17. // make sure they aren't all just the same point
  18. if (r.P1.X == r.P2.X && r.P1.X == r.P3.X && r.P1.X == r.P4.X) &&
  19. (r.P1.Y == r.P2.Y && r.P1.Y == r.P3.Y && r.P1.Y == r.P4.Y) {
  20. return false
  21. }
  22. cx := (r.P1.X + r.P2.X + r.P3.X + r.P4.X) / 4.0
  23. cy := (r.P1.Y + r.P2.Y + r.P3.Y + r.P4.Y) / 4.0
  24. dd1 := math.Sqrt(math.Abs(cx-r.P1.X)) + math.Sqrt(math.Abs(cy-r.P1.Y))
  25. dd2 := math.Sqrt(math.Abs(cx-r.P2.X)) + math.Sqrt(math.Abs(cy-r.P2.Y))
  26. dd3 := math.Sqrt(math.Abs(cx-r.P3.X)) + math.Sqrt(math.Abs(cy-r.P3.Y))
  27. dd4 := math.Sqrt(math.Abs(cx-r.P4.X)) + math.Sqrt(math.Abs(cy-r.P4.Y))
  28. return math.Abs(dd1-dd2) < ɛ && math.Abs(dd1-dd3) < ɛ && math.Abs(dd1-dd4) < ɛ
  29. }
  30. // neighbors returns the two points that form the line which creates the right
  31. // angle of the point passed in as a parameter.
  32. func (r Rectangle) neighbors(p Point) (Point, Point) {
  33. keys := []float64{distance(r.P1, p), distance(r.P2, p), distance(r.P3, p), distance(r.P4, p)}
  34. sort.Float64s(keys)
  35. n := []Point{}
  36. d := distance(r.P1, p)
  37. if math.Abs(keys[1]-d) < ɛ || math.Abs(keys[2]-d) < ɛ {
  38. n = append(n, r.P1)
  39. }
  40. d = distance(r.P2, p)
  41. if math.Abs(keys[1]-d) < ɛ || math.Abs(keys[2]-d) < ɛ {
  42. n = append(n, r.P2)
  43. }
  44. d = distance(r.P3, p)
  45. if math.Abs(keys[1]-d) < ɛ || math.Abs(keys[2]-d) < ɛ {
  46. n = append(n, r.P3)
  47. }
  48. d = distance(r.P4, p)
  49. if math.Abs(keys[1]-d) < ɛ || math.Abs(keys[2]-d) < ɛ {
  50. n = append(n, r.P4)
  51. }
  52. return n[0], n[1]
  53. }
  54. // size returns the size of the Rectangle
  55. func (r Rectangle) size() float64 {
  56. n1, n2 := r.neighbors(r.P1)
  57. return distance(r.P1, n1) * distance(r.P1, n2)
  58. }
  59. // inOrder returns a []Point, let us call pts, in which the four sides of the
  60. // Rectangle can be defined as pts[0] -- pts[1], pts[0] -- pts[2],
  61. // pts[3] -- pts[1], and pts[3] -- pts[2]
  62. func (r Rectangle) inOrder() []Point {
  63. n1, n2 := r.neighbors(r.P1)
  64. across := &Point{}
  65. if r.P2 != n1 || r.P2 != n2 {
  66. across = &r.P2
  67. }
  68. if r.P3 != n1 || r.P3 != n2 {
  69. across = &r.P3
  70. }
  71. if r.P4 != n1 || r.P4 != n2 {
  72. across = &r.P4
  73. }
  74. return []Point{r.P1, n1, n2, *across}
  75. }
  76. // Adjacency detects whether two rectangles, r1, and r2, are adjacent.
  77. // Adjacency is defined as the sharing of a side
  78. func Adjacency(r1, r2 Rectangle) bool {
  79. order1 := r1.inOrder()
  80. order2 := r2.inOrder()
  81. sides1 := []line{
  82. {order1[0], order1[1]},
  83. {order1[0], order1[2]},
  84. {order1[3], order1[1]},
  85. {order1[3], order1[2]},
  86. }
  87. sides2 := []line{
  88. {order2[0], order2[1]},
  89. {order2[0], order2[2]},
  90. {order2[3], order2[1]},
  91. {order2[3], order2[2]},
  92. }
  93. for _, i := range sides1 {
  94. for _, j := range sides2 {
  95. if lineOnLine(i, j) {
  96. return true
  97. }
  98. }
  99. }
  100. return false
  101. }
  102. func removeDuplicates(xs *[]Point) {
  103. found := make(map[Point]bool)
  104. j := 0
  105. for i, x := range *xs {
  106. if !found[x] {
  107. found[x] = true
  108. (*xs)[j] = (*xs)[i]
  109. j++
  110. }
  111. }
  112. *xs = (*xs)[:j]
  113. }
  114. // Intersection determine whether two rectangles, r1 and r2, have one or more
  115. // intersecting lines and produce a result, []Point, identifying the points
  116. // of intersection
  117. func Intersection(r1, r2 Rectangle) []Point {
  118. order1 := r1.inOrder()
  119. order2 := r2.inOrder()
  120. sides1 := []line{
  121. {order1[0], order1[1]},
  122. {order1[0], order1[2]},
  123. {order1[3], order1[1]},
  124. {order1[3], order1[2]},
  125. }
  126. sides2 := []line{
  127. {order2[0], order2[1]},
  128. {order2[0], order2[2]},
  129. {order2[3], order2[1]},
  130. {order2[3], order2[2]},
  131. }
  132. pts := []Point{}
  133. for _, i := range sides1 {
  134. for _, j := range sides2 {
  135. p, err := lineIntersection(i, j)
  136. if err == nil {
  137. pts = append(pts, p)
  138. }
  139. }
  140. }
  141. removeDuplicates(&pts)
  142. return pts
  143. }
  144. // sumOfTri determines if the sum of the areas of the triangles created from
  145. // point p to two neighboring vertices of a side of the Rectangle, r, add up
  146. // to the same size as the Rectangle, r. This is one way to determine if
  147. // a point is inside of a Rectangle.
  148. func sumOfTri(r Rectangle, p Point) bool {
  149. n1, n2 := r.neighbors(r.P1)
  150. x1, x2 := Point{}, Point{}
  151. across := &Point{}
  152. if r.P2 != n1 || r.P2 != n2 {
  153. across = &r.P2
  154. x1, x2 = r.neighbors(r.P2)
  155. }
  156. if r.P3 != n1 || r.P3 != n2 {
  157. across = &r.P3
  158. x1, x2 = r.neighbors(r.P3)
  159. }
  160. if r.P4 != n1 || r.P4 != n2 {
  161. across = &r.P4
  162. x1, x2 = r.neighbors(r.P4)
  163. }
  164. sumTri := sizeTriangle(r.P1, n1, p) +
  165. sizeTriangle(r.P1, n2, p) +
  166. sizeTriangle(*across, x1, p) +
  167. sizeTriangle(*across, x2, p)
  168. if math.Abs(r.size()-sumTri) < ɛ {
  169. return true
  170. }
  171. return false
  172. }
  173. // Containment returns whether r2 is contained inside of r1
  174. func Containment(r1, r2 Rectangle) bool {
  175. if r1.size() <= r2.size() {
  176. return false
  177. }
  178. if sumOfTri(r1, r2.P1) && sumOfTri(r1, r2.P2) && sumOfTri(r1, r2.P3) && sumOfTri(r1, r2.P4) {
  179. return true
  180. }
  181. return false
  182. }