# python 3.x – Detect loop in rectilinear path

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

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

Output => Boolean, True if it has loop, False otherwise

I could think of two algorithms.

Algorithm -1 : For 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 cross with any vertical line segment.
3. If crossing found return True. Else return False
Complexity (O(N^2)): 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. It means O(N^2)

Algorithm -2: For 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 there 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.
6. Return False

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^2))). But number of pairs checked will be lesser than Algorithm-1.

``````#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
``````