在多边形内查找点并计算多个多边形的并集时存在未知错误

Question

希望你一切都好。 我正在编写一个代码来查找多个多边形的并集。我知道图书馆会这样做，但我需要从头开始。 当我运行代码时，我得到的输出显然是错误的，因为左下部分。

我真的不知道这个问题的原因是什么。

当我在代码中搜索并编写一些测试代码时，我发现了另一个错误，我不知道该错误是否与联合部分的错误有关，但无论如何，这是该联合功能的一部分。问题出在 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），但要正确。

Answer 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 坐标中减去阈值时点它进入多边形内部（或外部），但这种情况很少发生。我不知道如何解决这个新问题。