Preliminary version of a random polygon generation based on Nourollah2017 paper

random_polygon.py

from functools import partial

from _ctypes import ArgumentError
from hypothesis.strategies import (floats,
                                   tuples,
                                   lists)
from lz.iterating import pairwise
from shapely.geometry import (LineString,
                              Point,
                              Polygon)


def to_chain(coords):
    coords = coords.copy()
    for i in range(3, len(coords)):
        old_line = LineString(coords[:i])
        new_line = LineString(coords[i - 1:i + 1])

        for _ in range(len(coords)):
            if not new_line.crosses(old_line):
                break
            crossed_segment = first_to_cross(new_line, old_line)
            n = list(segments(old_line)).index(crossed_segment)
            m = n + 1

            fn = LineString([coords[i - 1], coords[n]])

            if not fn.crosses(old_line):
                coords[:i + 1] = coords[:n] + [coords[n], coords[i - 1]] + coords[i - 2:m:-1] + [coords[m], coords[i]]
                old_line = LineString(coords[:i])
                new_line = LineString(coords[i - 1:i + 1])
            else:
                coords[:i] = list(modify_chain(LineString(coords[:i][::-1]), x=0, y=i - 1 - n).coords)
                old_line = LineString(coords[:i])
                new_line = LineString(coords[i - 1:i + 1])
        else:
            coords = list(modify_chain(LineString(coords), x=0, y=len(coords) - 1).coords)
    return coords


def modify_chain(chain, x, y):
    connector = LineString([chain.coords[x], chain.coords[y]])

    if not connector.crosses(chain):
        return chain

    points = list(chain.coords)
    crossed_segment = first_to_cross(connector, chain)
    m = list(segments(chain)).index(crossed_segment)
    n = m + 1

    xn = LineString([points[x], points[n]])
    if not xn.crosses(chain):
        y_point = chain.coords[y]
        points = points[x:m + 1][::-1] + points[n:]
        chain = LineString(points)
        y = list(chain.coords).index(y_point)
        return modify_chain(chain, x=0, y=y)
    chain = modify_chain(chain, x=x, y=n)
    return modify_chain(chain, x=0, y=len(chain.coords) - 1)


def first_to_cross(new_line: LineString,
                   old_line: LineString) -> LineString:
    crossed_segments = [segment for segment in segments(old_line) if
                        segment.crosses(new_line)]
    intersections = [new_line.intersection(segment) for segment in
                     crossed_segments]
    closest_point = min(intersections, key=new_line.boundary[0].distance)
    index = intersections.index(closest_point)
    return crossed_segments[index]


def segments(ring: LineString):
    """Yields consecutive lines from the given ring"""
    pairs = pairwise(ring.coords)
    yield from map(LineString, pairs)


if __name__ == '__main__':
    n = 20
    to_finite_floats = partial(floats, allow_nan=False, allow_infinity=False)
    floats_in_range = to_finite_floats(min_value=-100, max_value=100)
    coordinates = tuples(floats_in_range, floats_in_range)
    coordinates_lists = lists(coordinates, min_size=n, max_size=n, unique=True)

    for j in range(1000):
        points_ = coordinates_lists.example()
        try:
            chain = LineString(to_chain(points_))
            modified = modify_chain(chain, 0, len(chain.coords) - 1)
        except (RecursionError, ArgumentError):
            print("recursion error on", j)
            break
        if not Polygon(modified).is_valid or len(modified.coords) != n:
            print("invalid result. breaking on", j)
            break