RobustDeterminant.js 3.4 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196
  1. export default class RobustDeterminant {
  2. static orientationIndex(p1, p2, q) {
  3. const dx1 = p2.x - p1.x
  4. const dy1 = p2.y - p1.y
  5. const dx2 = q.x - p2.x
  6. const dy2 = q.y - p2.y
  7. return RobustDeterminant.signOfDet2x2(dx1, dy1, dx2, dy2)
  8. }
  9. static signOfDet2x2(x1, y1, x2, y2) {
  10. let sign = null
  11. let swap = null
  12. let k = null
  13. let count = 0
  14. sign = 1
  15. if (x1 === 0.0 || y2 === 0.0)
  16. if (y1 === 0.0 || x2 === 0.0)
  17. return 0
  18. else if (y1 > 0)
  19. if (x2 > 0)
  20. return -sign
  21. else
  22. return sign
  23. else
  24. if (x2 > 0)
  25. return sign
  26. else
  27. return -sign
  28. if (y1 === 0.0 || x2 === 0.0)
  29. if (y2 > 0)
  30. if (x1 > 0)
  31. return sign
  32. else
  33. return -sign
  34. else
  35. if (x1 > 0)
  36. return -sign
  37. else
  38. return sign
  39. if (0.0 < y1) {
  40. if (0.0 < y2) {
  41. if (y1 <= y2) {
  42. } else {
  43. sign = -sign
  44. swap = x1
  45. x1 = x2
  46. x2 = swap
  47. swap = y1
  48. y1 = y2
  49. y2 = swap
  50. }
  51. } else
  52. if (y1 <= -y2) {
  53. sign = -sign
  54. x2 = -x2
  55. y2 = -y2
  56. } else {
  57. swap = x1
  58. x1 = -x2
  59. x2 = swap
  60. swap = y1
  61. y1 = -y2
  62. y2 = swap
  63. }
  64. } else
  65. if (0.0 < y2) {
  66. if (-y1 <= y2) {
  67. sign = -sign
  68. x1 = -x1
  69. y1 = -y1
  70. } else {
  71. swap = -x1
  72. x1 = x2
  73. x2 = swap
  74. swap = -y1
  75. y1 = y2
  76. y2 = swap
  77. }
  78. } else
  79. if (y1 >= y2) {
  80. x1 = -x1
  81. y1 = -y1
  82. x2 = -x2
  83. y2 = -y2
  84. } else {
  85. sign = -sign
  86. swap = -x1
  87. x1 = -x2
  88. x2 = swap
  89. swap = -y1
  90. y1 = -y2
  91. y2 = swap
  92. }
  93. if (0.0 < x1) {
  94. if (0.0 < x2)
  95. if (x1 <= x2)
  96. ;
  97. else
  98. return sign
  99. else
  100. return sign
  101. } else
  102. if (0.0 < x2) {
  103. return -sign
  104. } else
  105. if (x1 >= x2) {
  106. sign = -sign
  107. x1 = -x1
  108. x2 = -x2
  109. } else {
  110. return -sign
  111. }
  112. while (true) {
  113. count = count + 1
  114. k = Math.floor(x2 / x1)
  115. x2 = x2 - k * x1
  116. y2 = y2 - k * y1
  117. if (y2 < 0.0)
  118. return -sign
  119. if (y2 > y1)
  120. return sign
  121. if (x1 > x2 + x2) {
  122. if (y1 < y2 + y2)
  123. return sign
  124. } else {
  125. if (y1 > y2 + y2) {
  126. return -sign
  127. } else {
  128. x2 = x1 - x2
  129. y2 = y1 - y2
  130. sign = -sign
  131. }
  132. }
  133. if (y2 === 0.0)
  134. if (x2 === 0.0)
  135. return 0
  136. else
  137. return -sign
  138. if (x2 === 0.0)
  139. return sign
  140. k = Math.floor(x1 / x2)
  141. x1 = x1 - k * x2
  142. y1 = y1 - k * y2
  143. if (y1 < 0.0)
  144. return sign
  145. if (y1 > y2)
  146. return -sign
  147. if (x2 > x1 + x1) {
  148. if (y2 < y1 + y1)
  149. return -sign
  150. } else {
  151. if (y2 > y1 + y1) {
  152. return sign
  153. } else {
  154. x1 = x2 - x1
  155. y1 = y2 - y1
  156. sign = -sign
  157. }
  158. }
  159. if (y1 === 0.0)
  160. if (x1 === 0.0)
  161. return 0
  162. else
  163. return sign
  164. if (x1 === 0.0)
  165. return -sign
  166. }
  167. }
  168. }