# Detect loop in rectilinear path

Given a rectilinear path, find if it has a loop. A rectilinear path is made up of made up of alternating horizontal and vertical segments.

Input => Ordered set of points representing ra ectilinear path. Points have been sanitised to ensure that they represent alternating horizontal and vertical segments. This means there are no two consecutive horizontal (or vertical) segments.

Output => True if it has loop, False otherwise. I could think of two algorithms.

# Algorithm 1

For a loop, there must be crossing between horizontal and vertical line segments.
Crossing/Overlap of two horizontal (or vertical) line segments can't lead to loop.

1. Break path into horizontal and vertical line segments.
2. Check if any horizontal line segment crosses any vertical line segment.
3. If crossing found return True. Else return False

## Algorithm 1 Complexity:

• N points means N-1 line segments.
• Vertical segment count is (N-1)/2. Same for horizontal segment count.
• Checking each pair of horizontal and vertical segments means (N-1)(N-2)/4 check. That gives complexity O(N²).

# Algorithm 2

For a loop, there must be crossing between horizontal and vertical line segments.
These line segments shouldn't be consecutive to each other in rectilinear path.

1. Break path into horizontal and vertical line segments.
2. Sort vertical line segments based on their x-values.
3. Iterate over horizontal line segments and check if any vertical line segment falls in its x-range. Use binary search over sorted vertical segments to find candidate vertical segments.
4. Check if horizontal line segment cross with any of the vertical line segments.
5. If crossing found return True. Else return False

## Algorithm 2 Complexity:

• Split into horizontal and vertical segments = O(N).
• vertical segment count = (N-1)/2.
• Sorting vertical segments: O(NLogN)
• Iteration over horizontal segment = O(N).
• For each iteration, Binary search O(LogN).
For each iteration, Check for crossing with candidate vertical segments. Worst case (N-1)/4.
• Worst case complexity remains O(N²). But number of pairs checked will be less than for Algorithm 1.

# Implementation of Algorithm 2

#Code for Algorithm 2
from  functools import cmp_to_key

# Represents line_segment which is either horizontal or vertical.
class line_segment:
__start_point = (0, 0)
__end_point = (0, 0)

def __init__(self, start_point, end_point):
if start_point == end_point:
self.__start_point = (start_point, end_point)[start_point > end_point]
self.__end_point = (start_point, end_point)[start_point < end_point]
else:
self.__start_point = (start_point, end_point)[start_point > end_point]
self.__end_point = (start_point, end_point)[start_point < end_point]

def does_intersect(self, target_line_segment):
is_vertical = self.is_segment_vertical()
is_traget_vertical = target_line_segment.is_segment_vertical()

# Check for parallel segments
if is_vertical and is_traget_vertical:
return False

if is_vertical:
return self.__start_point >= target_line_segment.__start_point and \
self.__start_point <= target_line_segment.__end_point and \
target_line_segment.__start_point >= self.__start_point and \
target_line_segment.__start_point <= self.__end_point
else:
return target_line_segment.__start_point >= self.__start_point and \
target_line_segment.__start_point <= self.__end_point and \
self.__start_point >= target_line_segment.__start_point and \
self.__start_point <= target_line_segment.__end_point

def is_segment_vertical(self):
return self.__start_point ==  self.__end_point

def get_value(self):
if self.is_segment_vertical():
return self.__start_point
else:
return self.__start_point

def get_non_constant_start_coordinate(self):
if self.is_segment_vertical():
return self.__start_point
else:
return self.__start_point

def get_non_constant_end_coordinate(self):
if self.is_segment_vertical():
return self.__end_point
else:
return self.__end_point

# Line segment comparator
def compare(item_1, item_2):
return item_1.get_value() - item_2.get_value()

def binary_serach_comparator(segment, search_value):
return segment.get_value() - search_value

def binary_serach(sorted_collection, serach_value, comparator):
high = len(sorted_collection) - 1
low = 0
index = -1
mid = 0
while(low <= high):
mid = int((low + high)/2)
comparator_value = comparator(sorted_collection[mid], serach_value)
if comparator_value < 0:
low = mid + 1
elif comparator_value > 0:
high = mid - 1
else:
index = mid
break

return (index, low, high)

def split_path_in_segments(path_points):
vertical_segment_start_index = (0, 1) [path_points == path_points]

vertical_segments  = [(line_segment(path_points[index], path_points[index + 1]), index)\
for index in range(vertical_segment_start_index, len(path_points) - 1, 2)]

horizontal_segments  = [(line_segment(path_points[index], path_points[index + 1]), index)\
for index in range(int(not(vertical_segment_start_index)), len(path_points) - 1, 2)]

return vertical_segments, horizontal_segments

def find_segments_in_range(segments, range_start, range_end):
(start_index, start_low, start_high) = binary_serach(segments, range_start, binary_serach_comparator)
(end_index, end_low, end_high) = binary_serach(segments, range_end, binary_serach_comparator)
return (start_low, end_high)

# Input: Ordered set of points representing rectilinear paths
# which is made up of alternating horizontal and vertical segments
def check_loop(path_points):

# For loop we need 4 or more segments. Hence more than 5 points
if len(path_points) <= 4:
return False

vertical_segments, horizontal_segments = split_path_in_segments(path_points)

# Sort vertical segmnets for easy serach
vertical_segments = sorted(vertical_segments,  key=cmp_to_key(compare))

# Iterate through horizontal segments, find vertical segments
# which fall in rane of horizontal segment and check for intersection
for horizontal_counter in range(len(horizontal_segments)):
horizontal_segment = horizontal_segments[horizontal_counter]
horizontal_segment_index = horizontal_segments[horizontal_counter]

(start, end) =  find_segments_in_range(vertical_segments,\
horizontal_segment.get_non_constant_start_coordinate(),\
horizontal_segment.get_non_constant_end_coordinate())

for vertical_counter in range(start, end + 1):
vertical_segment = vertical_segments[vertical_counter]
vertical_segment_index = vertical_segments[vertical_counter]

# Avoid adjacent segments. They will always have one endpoint in common
if abs(horizontal_segment_index - vertical_segment_index) <= 1:
continue

if horizontal_segment.does_intersect(vertical_segment):
return True

return False

print(check_loop([(0,0), (5,0), (5, 5)])) # False
print(check_loop([(0,0), (5,0), (5, 5), (0, 5), (0, 0)])) # True
print(check_loop([(0,0), (5,0), (5, 5), (4, 5)])) # False
print(check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 2)])) # False
print(check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, -1)])) # True
print(check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 0)])) # True
print(check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2)]))# False
print(check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2), (11, 2), (11, 1), (-5, 1), (-5, 15)]))# False
print(check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2), (10, -1), (2, -1), (2, 15)]))# True


# Review request

1. Algorithm improvements.
2. Functional correctness of implemented algorithm.
3. Boundary and error cases.
4. Python-specific feedback.
• “For loop there must be crossing between horizontal and vertical line segments” – What about the path (1, 0) -> (3, 0) -> (3, 1) -> (0, 1) -> (0, 0) -> (2, 0) ? Sep 7 at 11:00
• @MartinR: There is an assumption that overlapping segments will be merged during sanitization step before calling into check_loop. So in your example, input should become (3, 0) -> (3, 1) ->(0, 1)->(0, 0)->(3, 0). It will become a loop. Sep 7 at 12:17
• Coordinates are guaranteed to be integers. No restriction on number of points. Sep 7 at 15:55
• @Reinderien: No restriction on range assumed. Sep 7 at 16:21
• binary_serach? You'll make your code more maintainable if you correct the spellings. Sep 9 at 7:48

print(check_loop([(0,0), (5,0), (5, 5)])) # False
print(check_loop([(0,0), (5,0), (5, 5), (0, 5), (0, 0)])) # True
print(check_loop([(0,0), (5,0), (5, 5), (4, 5)])) # False
print(check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 2)])) # False
print(check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, -1)])) # True
print(check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 0)])) # True
print(check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2)]))# False
print(check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2), (11, 2), (11, 1), (-5, 1), (-5, 15)]))# False
print(check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2), (10, -1), (2, -1), (2, 15)]))# True


This looks like a candidate for a proper unit test:

def check_loop(path_points):
"""
>>> check_loop([(0,0), (5,0), (5, 5)])
False
>>> check_loop([(0,0), (5,0), (5, 5), (0, 5), (0, 0)])
True
>>> check_loop([(0,0), (5,0), (5, 5), (4, 5)])
False
>>> check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 2)])
False
>>> check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, -1)])
True
>>> check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 0)])
True
>>> check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2)])
False
>>> check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2), (11, 2), (11, 1), (-5, 1), (-5, 15)])
False
>>> check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2), (10, -1), (2, -1), (2, 15)])
True
"""
⋮

if __name__ == "__main__":
import doctest
doctest.testmod()


Now, instead of an error-prone visual check (or diff against expected results, with error-prone lookup of which one failed), we get useful diagnostic output, just by running the code. For example, if we add the case from my algorithm answer:

>>> check_loop([(4,0), (0,0), (0, 1), (5, 1), (5, 0), (1,0)])
True


Then we get this output:

**********************************************************************
File "267737.py", line 105, in __main__.check_loop
Failed example:
check_loop([(4,0), (0,0), (0, 1), (5, 1), (5, 0), (1,0)])
Expected:
True
Got:
False
**********************************************************************
1 of  10 in __main__.check_loop
***Test Failed*** 1 failures.


I'm not going to really talk much about the algorithm for the first part, and more about Python usage.

• line_segment needs to be LineSegment by PEP8
• __start_point should not be double-underscored, and should not be declared at the static level, so delete __start_point = (0, 0)
• Don't index  and  when you actually just mean .x and .y, for which named tuples are well-suited
• Convert many (most?) of your class methods to @properties
• Do not implement your own binary search; call into bisect (I have not shown this in my reference implementation)
• Fix up minor typos such as segmnets, serach
• Replace your prints with asserts to magically get actual unit tests

## Suggested

# Code for Algorithm-2
from functools import cmp_to_key
from typing import Tuple, Sequence, List, NamedTuple, Callable

class Point(NamedTuple):
x: int
y: int

class LineSegment:
"""
Represents line_segment which is either horizontal or vertical.
"""

def __init__(self, start_point: Point, end_point: Point) -> None:
if start_point.x == end_point.x:
self._start_point = (start_point, end_point)[start_point.y > end_point.y]
self._end_point = (start_point, end_point)[start_point.y < end_point.y]
else:
self._start_point = (start_point, end_point)[start_point.x > end_point.x]
self._end_point = (start_point, end_point)[start_point.x < end_point.x]

def does_intersect(self, target_line_segment: 'LineSegment') -> bool:
is_vertical = self.is_segment_vertical
is_target_vertical = target_line_segment.is_segment_vertical

# Check for parallel segments
if is_vertical and is_target_vertical:
return False

if is_vertical:
return (
target_line_segment._start_point.x <= self._start_point.x <= target_line_segment._end_point.x and
self._start_point.y <= target_line_segment._start_point.y <= self._end_point.y
)
else:
return (
target_line_segment._start_point.y <= self._start_point.y <= target_line_segment._end_point.y and
self._start_point.x <= target_line_segment._start_point.x <= self._end_point.x
)

@property
def is_segment_vertical(self) -> bool:
return self._start_point.x == self._end_point.x

@property
def value(self) -> int:
if self.is_segment_vertical:
return self._start_point.x
else:
return self._start_point.y

@property
def non_constant_start_coordinate(self) -> int:
if self.is_segment_vertical:
return self._start_point.y
else:
return self._start_point.x

@property
def non_constant_end_coordinate(self) -> int:
if self.is_segment_vertical:
return self._end_point.y
else:
return self._end_point.x

class IndexedSegment(NamedTuple):
segment: LineSegment
index: int

# Line segment comparator
def compare(item_1: IndexedSegment, item_2: IndexedSegment) -> int:
return item_1.segment.value - item_2.segment.value

def binary_search_comparator(segment: IndexedSegment, search_value: int) -> int:
return segment.segment.value - search_value

def binary_search(
sorted_collection: Sequence[IndexedSegment],
search_value: int,
comparator: Callable[[IndexedSegment, int], int],
) -> Tuple[
int,  # index
int,  # low
int,  # high
]:
high = len(sorted_collection) - 1
low = 0
index = -1

while low <= high:
mid = (low + high)//2
comparator_value = comparator(sorted_collection[mid], search_value)
if comparator_value < 0:
low = mid + 1
elif comparator_value > 0:
high = mid - 1
else:
index = mid
break

return index, low, high

def split_path_in_segments(path_points: Sequence[Point]) -> Tuple[
List[IndexedSegment],  # vert segments
List[IndexedSegment],  # horz segments
]:
vertical_segment_start_index = (0, 1) [path_points.x == path_points.x]

vertical_segments = [
IndexedSegment(LineSegment(path_points[index], path_points[index + 1]), index)
for index in range(vertical_segment_start_index, len(path_points) - 1, 2)
]

horizontal_segments = [
IndexedSegment(LineSegment(path_points[index], path_points[index + 1]), index)
for index in range(int(not vertical_segment_start_index), len(path_points) - 1, 2)
]

return vertical_segments, horizontal_segments

def find_segments_in_range(
segments: Sequence[IndexedSegment],
range_start: int,
range_end: int,
) -> Tuple[
int,  # start low
int,  # end high
]:
start_index, start_low, start_high = binary_search(segments, range_start, binary_search_comparator)
end_index, end_low, end_high = binary_search(segments, range_end, binary_search_comparator)
return start_low, end_high

# Input: Ordered set of points representing rectilinear paths
# which is made up of alternating horizontal and vertical segments
def check_loop(path_points: Sequence[Tuple[int, int]]) -> bool:

# For loop we need 4 or more segments. Hence more than 5 points
if len(path_points) <= 4:
return False

points = [Point(*point) for point in path_points]

vertical_segments, horizontal_segments = split_path_in_segments(points)

# Sort vertical segments for easy search
vertical_segments = sorted(vertical_segments,  key=cmp_to_key(compare))

# Iterate through horizontal segments, find vertical segments
# which fall in range of horizontal segment and check for intersection
for horizontal_counter in range(len(horizontal_segments)):
horizontal_segment = horizontal_segments[horizontal_counter]
horizontal_segment_index = horizontal_segments[horizontal_counter]

start, end = find_segments_in_range(
vertical_segments,
horizontal_segment.non_constant_start_coordinate,
horizontal_segment.non_constant_end_coordinate,
)

for vertical_counter in range(start, end + 1):
vertical_segment = vertical_segments[vertical_counter]
vertical_segment_index = vertical_segments[vertical_counter]

# Avoid adjacent segments. They will always have one endpoint in common
if abs(horizontal_segment_index - vertical_segment_index) <= 1:
continue

if horizontal_segment.does_intersect(vertical_segment):
return True

return False

def test() -> None:
assert not check_loop([(0,0), (5,0), (5, 5)])
assert not check_loop([(0,0), (5,0), (5, 5), (4, 5)])
assert not check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 2)])
assert not check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2)])
assert not check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2),
(11, 2), (11, 1), (-5, 1), (-5, 15)])
assert check_loop([(0,0), (5,0), (5, 5), (0, 5), (0, 0)])
assert check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, -1)])
assert check_loop([(0,0), (5,0), (5, 5), (4, 5), (4, 0)])
assert check_loop([(0,0), (5,0), (5, 5), (8, 5), (8, 2), (10, 2), (10, -1), (2, -1), (2, 15)])

if __name__ == '__main__':
test()


## Correctness

Are you sure that your second-last test case is correct? It seems to me that there's clear segment collision but you've marked it False. It seems that your original algorithm is not able to find this collision.

## Vectorization

A somewhat brute-force but straightforwardly vectorized solution stands a chance at being performance-competitive:

• Use the discrete differential to find segment groups
• Broadcast to arrays representing the Cartesian product of the horizontal and vertical segments
• Ignore diagonals k=0 and k=1 as those represent adjacent line segments that, whereas they share one endpoint by definition, are not considered collisions

This passes your tests, so long as the second-last one is adjusted to assert True which I think is necessary. For what it's worth, it's also much more terse.

def new(points: Sequence[Tuple[int, int]]) -> bool:
# shape: points, x/y
continuous_points = np.array(points)

def sanitise_segments(axis: int) -> np.ndarray:
# This does NOT check for contiguous segments, only segments that fail
# to alternate in orientation
on_axis = continuous_points[:, axis]
groups = np.split(continuous_points, np.where(np.diff(on_axis) == 0) + 1)
segment_list = []
for group in groups:
if group.shape > 1:
segment = np.empty((2, 2), dtype=np.int64)
segment[:, 1 - axis] = group[0, 1 - axis]
segment[0, axis] = np.min(group[:, axis])
segment[1, axis] = np.max(group[:, axis])
segment_list.append(segment)
return np.stack(segment_list)

# Each of these is of shape (segments, start/end, x/y)
horz_segs = sanitise_segments(0)
vert_segs = sanitise_segments(1)

# Given linear equations x = xc, y = yc
# they would intersect (in a segment or not) at xc, yc.
# If xc, yc is within the bounds for both segments, that's a "loop".
x = vert_segs[:, 0, 0:1]
in_x1 = horz_segs[:, 0, 0:1].T <= x
in_x2 = horz_segs[:, 1, 0:1].T >= x

y = horz_segs[:, 0, 1:2].T
in_y1 = vert_segs[:, 0, 1:2] <= y
in_y2 = vert_segs[:, 1, 1:2] >= y


+---O  <--+