Detect loop in rectilinear path

Question

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 a rectilinear 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.

enter image description here

---

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(N2).

---

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(N2). 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[0] == end_point[0]:
 self.__start_point = (start_point, end_point)[start_point[1] > end_point[1]]
 self.__end_point = (start_point, end_point)[start_point[1] < end_point[1]]
 else:
 self.__start_point = (start_point, end_point)[start_point[0] > end_point[0]]
 self.__end_point = (start_point, end_point)[start_point[0] < end_point[0]]
 
 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[0] >= target_line_segment.__start_point[0] and \
 self.__start_point[0] <= target_line_segment.__end_point[0] and \
 target_line_segment.__start_point[1] >= self.__start_point[1] and \
 target_line_segment.__start_point[1] <= self.__end_point[1] 
 else:
 return target_line_segment.__start_point[0] >= self.__start_point[0] and \
 target_line_segment.__start_point[0] <= self.__end_point[0] and \
 self.__start_point[1] >= target_line_segment.__start_point[1] and \
 self.__start_point[1] <= target_line_segment.__end_point[1] 
 
 
 def is_segment_vertical(self):
 return self.__start_point[0] == self.__end_point[0]
 
 def get_value(self):
 if self.is_segment_vertical():
 return self.__start_point[0]
 else:
 return self.__start_point[1] 
 
 def get_non_constant_start_coordinate(self):
 if self.is_segment_vertical():
 return self.__start_point[1]
 else:
 return self.__start_point[0]
 
 def get_non_constant_end_coordinate(self):
 if self.is_segment_vertical():
 return self.__end_point[1]
 else:
 return self.__end_point[0]
 
# Line segment comparator
def compare(item_1, item_2):
 return item_1[0].get_value() - item_2[0].get_value()
def binary_serach_comparator(segment, search_value):
 return segment[0].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[0][0] == path_points[1][0]]
 
 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][0]
 horizontal_segment_index = horizontal_segments[horizontal_counter][1] 
 
 (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][0]
 vertical_segment_index = vertical_segments[vertical_counter][1]
 
 # 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.

• Martin R: "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) ?
• nkvns: @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.
• nkvns: Coordinates are guaranteed to be integers. No restriction on number of points.
• nkvns: @Reinderien: No restriction on range assumed.
• Toby Speight: binary_serach? You'll make your code more maintainable if you correct the spellings.

Answer 1

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)
• Add PEP484 type hints
• Don't index [0] and [1] 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[0].x == path_points[1].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][0]
 horizontal_segment_index = horizontal_segments[horizontal_counter][1]
 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][0]
 vertical_segment_index = vertical_segments[vertical_counter][1]
 # 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)[0] + 1)
 segment_list = []
 for group in groups:
 if group.shape[0] > 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
 # Mask out adjacent segments, which are assumed not to collide.
 collisions = in_x1 & in_x2 & in_y1 & in_y2
 masked = np.tril(collisions, k=-1) | np.triu(collisions, k=2)
 return np.any(masked)

Answer 2

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 items had failures:
 1 of 10 in __main__.check_loop
***Test Failed*** 1 failures.

Answer 3

There is a problem with the algorithm described - if the first and last segment are both horizontal or both vertical, they could overlap without meeting a line of opposite direction:

+---O <--+
| |
+---------+

You might be able to catch this by simply adding a zero-length segment to the end if the input has an odd number of segments.