F. Antonio, "Faster Line Segment Intersection", Graphics Gems III, 1992
(zs []Point, a0, a1, b0, b1 Point)
| 185 | |
| 186 | // F. Antonio, "Faster Line Segment Intersection", Graphics Gems III, 1992 |
| 187 | func intersectionLineLineBentleyOttmann(zs []Point, a0, a1, b0, b1 Point) []Point { |
| 188 | // fast line-line intersection code, with additional constraints for the BentleyOttmann code: |
| 189 | // - a0 is to the left and/or bottom of a1, same for b0 and b1 |
| 190 | // - an intersection z must keep the above property between (a0,z), (z,a1), (b0,z), and (z,b1) |
| 191 | // note that an exception is made for (z,a1) and (z,b1) to allow them to become vertical, this |
| 192 | // is because there isn't always "space" between a0.X and a1.X, eg. when a1.X = nextafter(a0.X) |
| 193 | if a1.X < b0.X || b1.X < a0.X { |
| 194 | return zs |
| 195 | } |
| 196 | |
| 197 | aMin, aMax, bMin, bMax := a0, a1, b0, b1 |
| 198 | if a1.Y < a0.Y { |
| 199 | aMin.Y, aMax.Y = aMax.Y, aMin.Y |
| 200 | } |
| 201 | if b1.Y < b0.Y { |
| 202 | bMin.Y, bMax.Y = bMax.Y, bMin.Y |
| 203 | } |
| 204 | if aMax.Y < bMin.Y || bMax.Y < aMin.Y { |
| 205 | return zs |
| 206 | } else if (aMax.X == bMin.X || bMax.X == aMin.X) && (aMax.Y == bMin.Y || bMax.Y == aMin.Y) { |
| 207 | return zs |
| 208 | } |
| 209 | |
| 210 | // only the position and T values are valid for each intersection |
| 211 | A := a1.Sub(a0) |
| 212 | B := b0.Sub(b1) |
| 213 | C := a0.Sub(b0) |
| 214 | denom := B.PerpDot(A) |
| 215 | if denom == 0.0 { |
| 216 | // colinear |
| 217 | if C.PerpDot(B) == 0.0 { |
| 218 | // overlap, rotate to x-axis |
| 219 | a, b, c, d := a0.X, a1.X, b0.X, b1.X |
| 220 | if math.Abs(A.X) < math.Abs(A.Y) { |
| 221 | // mostly vertical |
| 222 | a, b, c, d = a0.Y, a1.Y, b0.Y, b1.Y |
| 223 | } |
| 224 | if c < b && a < d { |
| 225 | if a < c { |
| 226 | zs = append(zs, b0) |
| 227 | } else if c < a { |
| 228 | zs = append(zs, a0) |
| 229 | } |
| 230 | if d < b { |
| 231 | zs = append(zs, b1) |
| 232 | } else if b < d { |
| 233 | zs = append(zs, a1) |
| 234 | } |
| 235 | } |
| 236 | } |
| 237 | return zs |
| 238 | } |
| 239 | |
| 240 | // find intersections within +-Epsilon to avoid missing near intersections |
| 241 | ta := C.PerpDot(B) / denom |
| 242 | if ta < -Epsilon || 1.0+Epsilon < ta { |
| 243 | return zs |
| 244 | } |