两个多边形相交其闵可夫斯基差必过原点import tkinter as tk import math import numpy as np def idx2char(i): 0→A,1→B,2→C... 返回大写字母 return chr(ord(A) i) class PolyDrawApp: def __init__(self, root): self.root root self.root.title(闵可夫斯基差Y轴向上为正(右上正)) self.root.geometry(1000x750) self.is_drawing False self.current_points [] self.close_threshold 8 # polygons: {points_canvas:[[x,y],...], item_id:canvas_id, vertex_text_ids:[]} self.polygons [] self.max_poly_count 2 self.drag_poly_idx None self.drag_start_mx 0 self.drag_start_my 0 self.minkowski_item None self.minkowski_text_ids [] # 点标记 A1A2 self.minkowski_formula_ids [] # 计算公式文本 frame_top tk.Frame(root) frame_top.pack(filltk.X, padx5, pady5) self.btn_create tk.Button(frame_top, text创建多边形, commandself.start_create) self.btn_create.pack(sidetk.LEFT) self.btn_clear tk.Button(frame_top, text清空全部, commandself.clear_all) self.btn_clear.pack(sidetk.LEFT, padx10) self.canvas tk.Canvas(root, bgwhite) self.canvas.pack(filltk.BOTH, expandTrue, padx5, pady5) self.canvas.bind(Button-1, self.on_canvas_click) self.canvas.bind(B1-Motion, self.on_drag_move) self.canvas.bind(ButtonRelease-1, self.on_drag_release) self.root.update() self.redraw_axis() def redraw_axis(self): self.canvas.delete(axis) w self.canvas.winfo_width() h self.canvas.winfo_height() self.ox w / 2 # 画布原点像素x self.oy h / 2 # 画布原点像素y # X轴 self.canvas.create_line(0, self.oy, w, self.oy, fill#aaaaaa, dash(4,2), tagsaxis) # Y轴 self.canvas.create_line(self.ox, 0, self.ox, h, fill#aaaaaa, dash(4,2), tagsaxis) # 原点O标记 self.canvas.create_oval(self.ox-5,self.oy-5,self.ox5,self.oy5,fillblack,tagsaxis) self.canvas.create_text(self.ox12,self.oy12,textO,font(Consolas,11),tagsaxis) # X Y箭头标签 self.canvas.create_text(w-15, self.oy12, textX, font(Consolas,10), tagsaxis) self.canvas.create_text(self.ox12,15, textY, font(Consolas,10), tagsaxis) def canvas_to_math(self,cx,cy): 画布像素坐标 →数学坐标系Y向上为正 mx cx - self.ox my self.oy - cy return mx, my def math_to_canvas(self,mx,my): 数学坐标 →画布像素 cx mx self.ox cy self.oy - my return cx, cy def start_create(self): if len(self.polygons) self.max_poly_count: print(已经存在2个多边形不能继续创建) return self.is_drawing True self.current_points.clear() print(开始绘制多边形点击顶点点回第一个顶点闭合) self.canvas.delete(temp) def on_canvas_click(self, event): x, y event.x, event.y hit_idx self.pick_polygon(x, y) if hit_idx is not None and not self.is_drawing: self.drag_poly_idx hit_idx self.drag_start_mx event.x self.drag_start_my event.y return if not self.is_drawing: return if len(self.current_points) 1: sx, sy self.current_points[0] dist math.hypot(x - sx, y - sy) if dist self.close_threshold and len(self.current_points) 3: self.finish_polygon() return self.current_points.append([x, y]) self.canvas.create_oval(x-4, y-4, x4, y4, fillred, outlinered, tagstemp) if len(self.current_points) 2: x0,y0 self.current_points[-2] self.canvas.create_line(x0,y0, x,y, fillblue, width2, tagstemp) def finish_polygon(self): pts_canvas self.current_points.copy() item_id self.canvas.create_polygon(pts_canvas, outlineblue, fill#cce5ff, width2) poly_index len(self.polygons)1 # 1 /2 text_ids [] for i,(px,py) in enumerate(pts_canvas): char idx2char(i) label f{char}{poly_index} tid self.canvas.create_text(px8, py-8, textlabel, font(Consolas,10), fill#0000bb) text_ids.append(tid) self.polygons.append({ points_canvas: pts_canvas, item_id: item_id, vertex_text_ids: text_ids }) self.is_drawing False self.current_points.clear() self.canvas.delete(temp) print(f已完成多边形{poly_index}当前数量:{len(self.polygons)}) if len(self.polygons)2: self.draw_minkowski_diff() def pick_polygon(self, mx, my): for idx,poly in enumerate(self.polygons): pts poly[points_canvas] if self.point_in_polygon(mx,my,pts): return idx return None staticmethod def point_in_polygon(x,y,polygon): insideFalse nlen(polygon) for i in range(n): j(i1)%n xi,yipolygon[i] xj,yjpolygon[j] intersect((yiy)!(yjy)) if intersect: x_intersect ((y-yi)*(xj-xi))/(yj-yi)xi if xx_intersect: insidenot inside return inside def on_drag_move(self, event): if self.drag_poly_idx is None: return dx event.x - self.drag_start_mx dy event.y - self.drag_start_my poly self.polygons[self.drag_poly_idx] self.canvas.move(poly[item_id], dx, dy) for tid in poly[vertex_text_ids]: self.canvas.move(tid, dx, dy) # 更新画布坐标 for p in poly[points_canvas]: p[0] dx p[1] dy self.drag_start_mx event.x self.drag_start_my event.y if len(self.polygons)2: self.draw_minkowski_diff() def on_drag_release(self, event): self.drag_poly_idx None self.drag_start_mx 0 self.drag_start_my 0 def get_math_poly(self,poly_data): 把多边形canvas像素点列表转为数学坐标系点列表(Y向上为正) pts_canvas poly_data[points_canvas] math_pts [] for cx,cy in pts_canvas: mx,my self.canvas_to_math(cx,cy) math_pts.append([mx,my]) return math_pts def minkowski_difference(self, A_math, B_math): A⊖B a−b返回 (ia,ib,a_pt,b_pt,diff_pt)全部数学坐标 diff_points [] for ia,a in enumerate(A_math): for ib,b in enumerate(B_math): diff [a[0]-b[0], a[1]-b[1]] diff_points.append((ia, ib, a, b, diff)) return diff_points def draw_minkowski_diff(self): if self.minkowski_item is not None: self.canvas.delete(self.minkowski_item) for tid in self.minkowski_text_ids: self.canvas.delete(tid) for tid in self.minkowski_formula_ids: self.canvas.delete(tid) self.minkowski_text_ids.clear() self.minkowski_formula_ids.clear() A_math self.get_math_poly(self.polygons[0]) B_math self.get_math_poly(self.polygons[1]) diff_all self.minkowski_difference(A_math,B_math) diff_pts_only [d[4] for d in diff_all] if len(diff_pts_only)3: return hull_pts self.convex_hull(diff_pts_only) # 凸包数学坐标转画布 draw_hull [self.math_to_canvas(p[0],p[1]) for p in hull_pts] self.minkowski_item self.canvas.create_polygon(draw_hull, outline#c82423, fill#ffcccc, width2) for ia, ib, a_pt, b_pt, diff_pt in diff_all: # diff_pt 数学坐标 px_canvas, py_canvas self.math_to_canvas(diff_pt[0], diff_pt[1]) charA idx2char(ia) charB idx2char(ib) label_name f{charA}1{charB}2 ax, ay round(a_pt[0],1), round(a_pt[1],1) bx, by round(b_pt[0],1), round(b_pt[1],1) dx, dy round(diff_pt[0],1), round(diff_pt[1],1) formula_text f{label_name}{charA}1-{charB}2({ax},{ay})-({bx},{by})({dx},{dy}) tid_name self.canvas.create_text(px_canvas6, py_canvas-8, textlabel_name, font(Consolas,9), fill#bb0000) tid_formula self.canvas.create_text(px_canvas6, py_canvas8, textformula_text, font(Consolas,7), fill#600000) self.minkowski_text_ids.append(tid_name) self.minkowski_formula_ids.append(tid_formula) staticmethod def convex_hull(points): pts sorted(points) lower [] for p in pts: while len(lower)2: a np.array(lower[-2]) b np.array(lower[-1]) c np.array(p) cross np.cross(b-a, c-a) if cross 0: lower.pop() else: break lower.append(p) upper [] for p in reversed(pts): while len(upper)2: a np.array(upper[-2]) b np.array(upper[-1]) c np.array(p) cross np.cross(b-a, c-a) if cross 0: upper.pop() else: break upper.append(p) full lower[:-1] upper[:-1] if not full: return pts[:3] return full def clear_all(self): self.canvas.delete(tk.ALL) self.polygons.clear() self.is_drawing False self.current_points.clear() self.minkowski_item None self.minkowski_text_ids.clear() self.minkowski_formula_ids.clear() self.drag_poly_idx None self.redraw_axis() if __name__ __main__: win tk.Tk() app PolyDrawApp(win) win.mainloop()