Неизвестная ошибка при поиске точек внутри многоугольника и расчете объединения нескольких многоугольников

Я надеюсь, что с тобой все в порядке. Я пишу код, который находит объединение нескольких многоугольников. Я знаю, что это делают библиотеки, но мне нужно сделать это с нуля. Когда я запустил свой код, я получил этот вывод, который явно был неправильным из-за левой нижней части.

Я действительно не знаю, в чем может быть причина этой проблемы.

Когда я искал в своем коде и писал несколько тестовых кодов, я нашел еще одну ошибку, которая не знаю, связана ли она с ошибкой части объединения или нет, но в любом случае это часть этой функции объединения. проблема в функции contains_point. Это прекрасно работает, когда точка находится внутри или снаружи многоугольника.

но не тогда, когда точка находится на краях многоугольника.

Сначала я подумал, что, может быть, из-за чисел с плавающей запятой некоторые точки находятся внутри, а остаются снаружи, но потом я понял, что в верхнем и левом верхнем сегментах многоугольника нет красной точки. так что это не может быть связано с поведением с плавающей запятой, но я не знаю причину этой ошибки.

пожалуйста, помогите мне найти его. проблема в моем алгоритме или реализации или в чем-то еще?

союзная часть кода

def find_intersect(a1: Point, a2: Point, b1: Point, b2: Point) -> dict | None:
    t_top = (b2.x - b1.x) * (a1.y - b1.y) - (b2.y - b1.y) * (a1.x - b1.x)
    u_top = (b1.y - a1.y) * (a1.x - a2.x) - (b1.x - a1.x) * (a1.y - a2.y)
    bottom = (b2.y - b1.y) * (a2.x - a1.x) - (b2.x - b1.x) * (a2.y - a1.y)
    if bottom != 0:
        t = t_top / bottom
        u = u_top / bottom
        if 0 <= t <= 1 and 0 <= u <= 1:
            return {
                "x": lerp(a1.x, a2.x, t),
                "y": lerp(a1.y, a2.y, t),
                "offset": t,
            }
    return None


class Polygon:
    def __init__(self, points: list) -> None:
        self.points = points
        self.segments = []
        for i, _ in enumerate(self.points):
            self.segments.append(
                Segment(self.points[i], self.points[(i + 1) % len(self.points)])
            )

    @staticmethod
    def union(polygons: list) -> list:
        i = 0
        while i < len(polygons) - 1:
            j = i + 1
            while j < len(polygons):
                polygons[i].break_segments(polygons[j])
                j += 1
            i += 1
        kept_segments = []
        for i, polygon_i in enumerate(polygons):
            for segment in polygon_i.segments:
                keep = True
                for j, polygon_j in enumerate(polygons):
                    if i != j:
                        if polygon_j.contains_segment(segment):
                            keep = False
                            break
                if keep:
                    kept_segments.append(segment)
        return kept_segments

    def break_segments(self, other: Self) -> None:
        segments_1 = self.segments
        segments_2 = other.segments
        for i, _ in enumerate(segments_1):
            for j, _ in enumerate(segments_2):
                intersection = find_intersect(
                    segments_1[i].start,
                    segments_1[i].end,
                    segments_2[j].start,
                    segments_2[j].end,
                )
                if (
                    intersection
                    and intersection["offset"] != 0
                    and intersection["offset"] != 1
                ):
                    point = Point(intersection["x"], intersection["y"])
                    temporary = segments_1[i].end
                    segments_1[i].end = point
                    segments_1.insert(i + 1, Segment(point, temporary))
                    temporary = segments_2[j].end
                    segments_2[j].end = point
                    segments_2.insert(j + 1, Segment(point, temporary))

    def contains_segment(self, segment: Segment) -> bool:
        return self.contains_point(segment.midpoint())

функция contains_point класса многоугольника

def contains_point(self, point: Point) -> bool:
    px = point.x
    py = point.y
    intersections = 0
    for segment in self.segments:
        x1 = segment.start.x
        y1 = segment.start.y
        x2 = segment.end.x
        y2 = segment.end.y
        if (py < y1) != (py < y2):
            if ((px < x1) != (px < x2)) and (
                (x2 - x1) * (py - y1) == (px - x1) * (y2 - y1)
            ):
                return True
            if px < (x2 - x1) * (py - y1) / (y2 - y1) + x1:
                intersections += 1
    if intersections % 2 == 1:
        return True
    return False

Я хочу посчитать объединение многоугольников (рисунок 1), но правильно.

Вы используете правило намотки. Это исключит точки на правом краю. Ваша проблема, безусловно, связана с плавающей запятой. Вы не можете сравнивать значения с плавающей запятой на равенство, как вы это делаете. Вам может понадобиться функция «is_very_close_to».

Tim Roberts 04.04.2024 07:14
Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
0
1
61
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Я думаю, что проблема с вычислением объединения заключается в функции contains_point, и ваша проблема в этой функции связана именно со сравнением чисел с плавающей запятой. Как вы сказали, некоторые точки стоят на правой стороне линии, а другие — на левой, и найти точку точно на прямой почти никогда нельзя. Следовательно, первая проверка оператора if на одинаковый наклон между линией и новой линией от начала до новой точки не требуется. Однако для второго оператора if вам следует включить крошечный порог для учета точек, которые почти совпадают с линиями.

Вам может понадобиться что-то вроде этого кода:

def contains_point(self, point: Point, threshold: float = 0.01) -> bool:
    px = point.x
    py = point.y
    intersections = 0
    for segment in self.segments:
        x1 = segment.start.x
        y1 = segment.start.y
        x2 = segment.end.x
        y2 = segment.end.y
        if (py < y1) != (py < y2):
            if px - threshold < (x2 - x1) * (py - y1) / (y2 - y1) + x1:
                intersections += 1
    if intersections % 2 == 1:
        return True
    return False

В коде есть проблема.

Теоретически возможно, что точка находилась справа от одной из правых линий (или справа от одной из левых линий) многоугольника, но настолько близко к нему, что при вычитании порога из координаты x точки оно заходит внутрь (или за пределы) многоугольника, но случается это очень редко. Я понятия не имею, как решить эту новую проблему.

Другие вопросы по теме