6
\$\begingroup\$

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(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[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.
\$\endgroup\$
8
  • \$\begingroup\$ “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) ? \$\endgroup\$ Commented Sep 7, 2021 at 11:00
  • \$\begingroup\$ @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. \$\endgroup\$ Commented Sep 7, 2021 at 12:17
  • 1
    \$\begingroup\$ Coordinates are guaranteed to be integers. No restriction on number of points. \$\endgroup\$ Commented Sep 7, 2021 at 15:55
  • 1
    \$\begingroup\$ @Reinderien: No restriction on range assumed. \$\endgroup\$ Commented Sep 7, 2021 at 16:21
  • 1
    \$\begingroup\$ binary_serach? You'll make your code more maintainable if you correct the spellings. \$\endgroup\$ Commented Sep 9, 2021 at 7:48

3 Answers 3

Reset to default
2
\$\begingroup\$

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)
\$\endgroup\$
2
\$\begingroup\$ 
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.
\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.