Я надеюсь, что с тобой все в порядке. Я пишу код, который находит объединение нескольких многоугольников. Я знаю, что это делают библиотеки, но мне нужно сделать это с нуля. Когда я запустил свой код, я получил этот вывод, который явно был неправильным из-за левой нижней части.
Я действительно не знаю, в чем может быть причина этой проблемы.
Когда я искал в своем коде и писал несколько тестовых кодов, я нашел еще одну ошибку, которая не знаю, связана ли она с ошибкой части объединения или нет, но в любом случае это часть этой функции объединения. проблема в функции 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), но правильно.
Я думаю, что проблема с вычислением объединения заключается в функции 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 точки оно заходит внутрь (или за пределы) многоугольника, но случается это очень редко. Я понятия не имею, как решить эту новую проблему.
Вы используете правило намотки. Это исключит точки на правом краю. Ваша проблема, безусловно, связана с плавающей запятой. Вы не можете сравнивать значения с плавающей запятой на равенство, как вы это делаете. Вам может понадобиться функция «is_very_close_to».