SHOW:
|
|
- or go back to the newest paste.
| 1 | -- line segment intersections | |
| 2 | function setup() | |
| 3 | w = 0 | |
| 4 | l1ax,l1ay,l1bx,l1by,l2ax,l2ay,l2bx,l2by = randlines() | |
| 5 | watch("l1ax")
| |
| 6 | watch("l1ay")
| |
| 7 | watch("l1bx")
| |
| 8 | watch("l1by")
| |
| 9 | watch("l2ax")
| |
| 10 | watch("l2ay")
| |
| 11 | watch("l2bx")
| |
| 12 | watch("l2by")
| |
| 13 | end | |
| 14 | ||
| 15 | -- This function gets called once every frame | |
| 16 | function draw() | |
| 17 | background(0, 0, 0, 255) | |
| 18 | strokeWidth(3) | |
| 19 | showlines(l1ax,l1ay,l1bx,l1by,l2ax,l2ay,l2bx,l2by) | |
| 20 | if w % 30 == 0 then | |
| 21 | l1ax,l1ay,l1bx,l1by,l2ax,l2ay,l2bx,l2by = randlines() | |
| 22 | w = 0 | |
| 23 | end | |
| 24 | w = w + 1 | |
| 25 | end | |
| 26 | ||
| 27 | function randlines() | |
| 28 | l1ax = math.random()*WIDTH | |
| 29 | l1ay = math.random()*HEIGHT | |
| 30 | l1bx = math.random()*WIDTH | |
| 31 | l1by = math.random()*HEIGHT | |
| 32 | l2ax = math.random()*WIDTH | |
| 33 | l2ay = math.random()*HEIGHT | |
| 34 | l2bx = math.random()*WIDTH | |
| 35 | l2by = math.random()*HEIGHT | |
| 36 | return l1ax,l1ay,l1bx,l1by,l2ax,l2ay,l2bx,l2by | |
| 37 | end | |
| 38 | ||
| 39 | function showlines(l1ax,l1ay,l1bx,l1by,l2ax,l2ay,l2bx,l2by) | |
| 40 | stroke(255, 0, 0, 255) | |
| 41 | line(l1ax,l1ay,l1bx,l1by) | |
| 42 | stroke(0, 0, 255, 255) | |
| 43 | line(l2ax,l2ay,l2bx,l2by) | |
| 44 | stroke(0,255,0,255) | |
| 45 | strokeWidth(9) | |
| 46 | it, iax, iay, ibx, iby = getintersection(l1ax,l1ay,l1bx,l1by,l2ax,l2ay,l2bx,l2by) | |
| 47 | if it then | |
| 48 | line(iax,iay,ibx,iby) | |
| 49 | elseif not it then | |
| 50 | line(iax+10,iay+10,ibx-10,iby-10) | |
| 51 | line(iax-10,iay+10,ibx+10,iby-10) | |
| 52 | else | |
| 53 | line(iax,iay,ibx,iby) | |
| 54 | end | |
| 55 | end | |
| 56 | ||
| 57 | function getintersection(x1, y1, x2, y2, x3, y3, x4, y4) | |
| 58 | --special thanks to voiceofreason | |
| 59 | d = (y4-y3)*(x2-x1)-(x4-x3)*(y2-y1) | |
| 60 | Ua_n = ((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3)) | |
| 61 | Ub_n = ((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3)) | |
| 62 | if d == 0 then | |
| 63 | if Ua_n == 0 and Ua_n == Ub_n then | |
| 64 | --they are on the same plane | |
| 65 | --they are either | |
| 66 | --the same point | |
| 67 | --the same line | |
| 68 | --two unconnected lines | |
| 69 | --slightly overlapping | |
| 70 | --one within the other | |
| 71 | --find max and least x for line 1 | |
| 72 | if x1 > x2 then | |
| 73 | mxl1 = x1 -- max x of line 1 | |
| 74 | lxl1 = x2 -- least x of line 1 | |
| 75 | elseif l1ax <= l1bx then | |
| 76 | mxl1 = x2 -- max x of line 1 | |
| 77 | lxl1 = x1 -- least x of line 1 | |
| 78 | end | |
| 79 | --find max and least x for line 2 | |
| 80 | if x3 > x4 then | |
| 81 | mxl2 = x3 -- max x of line 2 | |
| 82 | lxl2 = x4 -- least x of line 2 | |
| 83 | elseif x3 <= x4 then | |
| 84 | mxl2 = x4 -- max x of line 2 | |
| 85 | lxl2 = x3 -- least x of line 2 | |
| 86 | end | |
| 87 | if (mxl1 < lxl2) or (lxl1 > mxl2) then | |
| 88 | -- no shared x | |
| 89 | mx = (l1ax+l1bx+l2ax+l2bx)/4 --midx | |
| 90 | my = (l1ay+l1by+l2ay+l2by)/4 --midy | |
| 91 | return false,mx,my,mx,my | |
| 92 | end | |
| 93 | --find max and least y for line 1 | |
| 94 | if y1 > y2 then | |
| 95 | myl1 = y1 -- max y of line 1 | |
| 96 | lyl1 = y2 -- least y of line 1 | |
| 97 | elseif y1 <= y2 then | |
| 98 | myl1 = y2 -- max y of line 1 | |
| 99 | lyl1 = y1 -- least y of line 1 | |
| 100 | end | |
| 101 | --find max and least y for line 2 | |
| 102 | if y3 > y4 then | |
| 103 | myl2 = y3 -- max y of line 2 | |
| 104 | lyl2 = y4 -- least y of line 1 | |
| 105 | elseif y3 <= y4 then | |
| 106 | myl2 = y4 -- max y of line 1 | |
| 107 | lyl2 = y3 -- least y of line 1 | |
| 108 | end | |
| 109 | ||
| 110 | if (myl1 < lyl2) or (lyl1 > myl2) then | |
| 111 | -- no shared y | |
| 112 | mx = (l1ax+l1bx+l2ax+l2bx)/4 --midx | |
| 113 | my = (l1ay+l1by+l2ay+l2by)/4 --midy | |
| 114 | return false,mx,my,mx,my | |
| 115 | end | |
| 116 | ||
| 117 | if (lxl1 == lxl2) and (mxl1 == mxl2) and (lxl1 == mxl1) then | |
| 118 | --x is the same for all points | |
| 119 | if (lyl1 == lyl2) then --the least y is common | |
| 120 | if (myl1 == myl2) then -- the max y is common | |
| 121 | if (lyl1 == myl2) then | |
| 122 | --the lines are really just one point | |
| 123 | return true, x1, y1, x1, y1 | |
| 124 | else --they are the same vertical line | |
| 125 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 126 | end | |
| 127 | elseif (myl1 > myl2) then | |
| 128 | --the vertical line 1 is longer | |
| 129 | return math.huge, lxl1, lyl1, mxl2, myl2 | |
| 130 | else --the vertical line 2 is longer | |
| 131 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 132 | end | |
| 133 | elseif (myl1 == myl2) then -- the max y is common | |
| 134 | --point and same vertical line handled above | |
| 135 | if (lyl1 > lyl2) then -- the vertcal line 2 is longer | |
| 136 | --aka line 2 starts lower than line 1 | |
| 137 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 138 | else -- the vertcal line 1 is longer | |
| 139 | return math.huge, lxl1, lyl1, mxl2, myl2 | |
| 140 | end | |
| 141 | elseif (lyl1 == myl2) then | |
| 142 | --the vertical lines are end to end | |
| 143 | --with line 1 above line 2 | |
| 144 | return true, lxl1, lyl1, mxl2, myl2 | |
| 145 | elseif (lyl2 == myl1) then | |
| 146 | --the vertical lines are end to end | |
| 147 | --with line 2 above line 1 | |
| 148 | return true, lxl2, lyl2, mxl1, myl1 | |
| 149 | elseif (lyl1 < lyl2) then | |
| 150 | --line 1 is lowest | |
| 151 | if (myl1 < myl2) then | |
| 152 | --line 2 is highest | |
| 153 | --overlapping lines | |
| 154 | return math.huge, lxl2, lyl2, mxl1, myl1 | |
| 155 | else | |
| 156 | --line 1 is highest | |
| 157 | --line 2 lies within line 1 | |
| 158 | return math.huge, lxl2, lyl2, mxl2, myl2 | |
| 159 | end | |
| 160 | else --line 2 is lowest | |
| 161 | if (myl1 < myl2) then | |
| 162 | --line 2 is highest | |
| 163 | --line 1 lies within line 2 | |
| 164 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 165 | else | |
| 166 | --line 1 is highest | |
| 167 | --overlapping lines | |
| 168 | return math.huge, lxl1, lyl1, mxl2, myl2 | |
| 169 | end | |
| 170 | end --all vertical line tests | |
| 171 | end --vertical lines | |
| 172 | ||
| 173 | if (lyl1 == lyl2) and (myl1 == myl2) and (lyl1 == myl1) then | |
| 174 | --y is the same for all points | |
| 175 | if (lxl1 == lxl2) then --the least x is common | |
| 176 | if (mxl1 == mxl2) then -- the max x is common | |
| 177 | --same point handled under vertical lines | |
| 178 | --they are the same horizontal line | |
| 179 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 180 | elseif (mxl1 > mxl2) then | |
| 181 | --the horizontal line 1 is longer | |
| 182 | return math.huge, lxl1, lyl1, mxl2, myl2 | |
| 183 | else --the horizontal line 2 is longer | |
| 184 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 185 | end | |
| 186 | elseif (mxl1 == mxl2) then -- the max x is common | |
| 187 | --point and same line handled above | |
| 188 | if (lxl1 > lxl2) then -- the horizontal line 2 is longer | |
| 189 | --aka line 2 starts left of line 1 | |
| 190 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 191 | else -- the horizontal line 1 is longer | |
| 192 | return math.huge, lxl1, lyl1, mxl2, myl2 | |
| 193 | end | |
| 194 | elseif (lxl1 == mxl2) then | |
| 195 | --the horizontal lines are end to end | |
| 196 | --with line 1 to the right of line 2 | |
| 197 | return true, lxl1, lyl1, mxl2, myl2 | |
| 198 | elseif (lxl2 == mxl1) then | |
| 199 | --the horizontal lines are end to end | |
| 200 | --with line 2 to the right of line 1 | |
| 201 | return true, lxl2, lyl2, mxl1, myl1 | |
| 202 | elseif (lxl1 < lxl2) then | |
| 203 | --line 1 is left | |
| 204 | if (mxl1 < mxl2) then | |
| 205 | --line 2 is right | |
| 206 | --overlapping lines | |
| 207 | return math.huge, lxl2, lyl2, mxl1, myl1 | |
| 208 | else | |
| 209 | --line 1 is right | |
| 210 | --line 2 lies within line 1 | |
| 211 | return math.huge, lxl2, lyl2, mxl2, myl2 | |
| 212 | end | |
| 213 | else --line 2 is left | |
| 214 | if (mxl1 < mxl2) then | |
| 215 | --line 2 is right | |
| 216 | --line 1 lies within line 2 | |
| 217 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 218 | else | |
| 219 | --line 1 is left | |
| 220 | --overlapping lines | |
| 221 | return math.huge, lxl1, lyl1, mxl2, myl2 | |
| 222 | end | |
| 223 | end --all horizontal line tests | |
| 224 | end --horizontal lines | |
| 225 | ||
| 226 | if ((lxl1 == lxl2) and (mxl1 == mxl2)) then | |
| 227 | --((lyl1 = lyl2) and (myl1 = myl2)) | |
| 228 | --all remaining same lines | |
| 229 | return math.huge, x1, y1, x2, y2 | |
| 230 | end | |
| 231 | ||
| 232 | if (lxl1 == lxl2) then --the least x is common | |
| 233 | if (mxl1 > mxl2) then | |
| 234 | --the line 1 is longer | |
| 235 | return math.huge, lxl1, lyl1, mxl2, myl2 | |
| 236 | else --the line 2 is longer | |
| 237 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 238 | end | |
| 239 | elseif (mxl1 == mxl2) then --the max x is common | |
| 240 | if (lxl1 > lxl2) then | |
| 241 | --the line 1 is longer | |
| 242 | return math.huge, lxl2, lyl2, mxl2, myl2 | |
| 243 | else --the line 2 is longer | |
| 244 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 245 | end | |
| 246 | elseif (lxl1 == mxl2) then | |
| 247 | --the horizontal lines are end to end | |
| 248 | --with line 1 to the right of line 2 | |
| 249 | return true, lxl1, lyl1, mxl2, myl2 | |
| 250 | elseif (lxl2 == mxl1) then | |
| 251 | --the horizontal lines are end to end | |
| 252 | --with line 2 to the right of line 1 | |
| 253 | return true, lxl2, lyl2, mxl1, myl1 | |
| 254 | elseif (lxl1 < lxl2) then | |
| 255 | --line 1 is left | |
| 256 | if (mxl1 < mxl2) then | |
| 257 | --line 2 is right | |
| 258 | --overlapping lines | |
| 259 | return math.huge, lxl2, lyl2, mxl1, myl1 | |
| 260 | else | |
| 261 | --line 1 is right | |
| 262 | --line 2 lies within line 1 | |
| 263 | return math.huge, lxl2, lyl2, mxl2, myl2 | |
| 264 | end | |
| 265 | else --line 2 is left | |
| 266 | if (mxl1 < mxl2) then | |
| 267 | --line 2 is right | |
| 268 | --line 1 lies within line 2 | |
| 269 | return math.huge, lxl1, lyl1, mxl1, myl1 | |
| 270 | else | |
| 271 | --line 1 is left | |
| 272 | --overlapping lines | |
| 273 | return math.huge, lxl1, lyl1, mxl2, myl2 | |
| 274 | end | |
| 275 | end | |
| 276 | --return true,x1,y1,x2,y2 | |
| 277 | end --lines in same plane / parallel | |
| 278 | mx = (l1ax+l1bx+l2ax+l2bx)/4 --midx | |
| 279 | my = (l1ay+l1by+l2ay+l2by)/4 --midy | |
| 280 | return false,mx,my,mx,my | |
| 281 | --return false | |
| 282 | end | |
| 283 | Ua = Ua_n / d | |
| 284 | Ub = Ub_n / d | |
| 285 | ia = x1 + (Ua*(x2-x1)) | |
| 286 | ib = y1 + (Ua*(y2-y1)) | |
| 287 | if Ua >= 0 and Ua <= 1 and Ub >= 0 and Ub <= 1 then | |
| 288 | --return true | |
| 289 | return true,ia,ib,ia,ib | |
| 290 | end | |
| 291 | mx = (l1ax+l1bx+l2ax+l2bx)/4 --midx | |
| 292 | my = (l1ay+l1by+l2ay+l2by)/4 --midy | |
| 293 | --return false | |
| 294 | return false,mx,my,mx,my | |
| 295 | end | |
| 296 | ||
| 297 | function segmentIntersects(x1, y1, x2, y2, x3, y3, x4, y4) | |
| 298 | --special thanks to voiceofreason | |
| 299 | d = (y4-y3)*(x2-x1)-(x4-x3)*(y2-y1) | |
| 300 | Ua_n = ((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3)) | |
| 301 | Ub_n = ((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3)) | |
| 302 | if d == 0 then | |
| 303 | if Ua_n == 0 and Ua_n == Ub_n then | |
| 304 | return true | |
| 305 | end | |
| 306 | return false | |
| 307 | end | |
| 308 | Ua = Ua_n / d | |
| 309 | Ub = Ub_n / d | |
| 310 | if Ua >= 0 and Ua <= 1 and Ub >= 0 and Ub <= 1 then | |
| 311 | ||
| 312 | return true | |
| 313 | end | |
| 314 | ||
| 315 | return false | |
| 316 | - | end |
| 316 | + | |
| 317 | ||
| 318 |
