This implementation is a little too simple: when a -> b is oriented positive along x, but v0 -> v1 is oriented negative along x, the t values (the projection on a vector) are not comparable. An orientation check is required first.
Secondly, the cross product here may generate unnecessarily large values. Where this function is used primarily, it will have already checked that the bounding boxes of the segment and the polygon overlap. The norm n is defined from (0.0, 0.0); v0 and v1 may be very far away. Better to work in local coordinates, choosing a as the reference.
@nb.njit(inline="always")
def collinear_case(a: Point, b: Point, v0: Point, v1: Point) -> Tuple[Point, Point]:
# Project on the same axis (t), take inner values
n = Vector(-(b.y - a.y), (b.x - a.x))
ta = cross_product(n, a)
tb = cross_product(n, b)
t0 = cross_product(n, v0)
t1 = cross_product(n, v1)
if not overlap(ta, tb, t0, t1):
return NO_INTERSECTION
if t0 < ta:
p0 = v0
else:
p0 = a
if t1 > tb:
p1 = v1
else:
p1 = b
return True, p0, p1
This implementation is a little too simple: when a -> b is oriented positive along x, but v0 -> v1 is oriented negative along x, the
t
values (the projection on a vector) are not comparable. An orientation check is required first.Secondly, the cross product here may generate unnecessarily large values. Where this function is used primarily, it will have already checked that the bounding boxes of the segment and the polygon overlap. The norm
n
is defined from (0.0, 0.0); v0 and v1 may be very far away. Better to work in local coordinates, choosinga
as the reference.