倒角算法推导

article/2025/10/6 23:56:08

倒角算法推导
推导原理基本很简单:

已知AB, BC两条线段,且交于B点,求倒角半径为 L,AB,BC的倒角

以最短边(假定为AB)长 LAB,
在BC中,以B为起点,找出与LAB同长度的点D,
即BD的长度等于AB的长度

(或 以B为圆心,LAB为半径, 绘制一个圆,
圆与AB交于A点, 于BC交于D点)

连接AD, 找出AD的中点P,

连接BP,
则BP为ABC夹角的角平分线

此时构成的 ABD,为一个等腰三角形
可轻松得出 垂直于BP的线, 到AB与BD的距离相等,即AP = PD
可样可用直角三角形法则得出 BP上的任意点,到AB的垂线,与到BC的垂线相等
即 XM = XN = L 圆弧半径

以X点作圆心,XM作半径,绘制圆,
该圆与AB, BC分别相切,

则圆弧 MN 则为AB与BC的倒角,倒角半径为L = XM

加上角度,长度,坐标的标记,如下:
倒角算法推导


python算法:

import numpy as np
import math# 求单位向量
def unit_vector(vector):""" Returns the unit vector of the vector.  """return vector / np.linalg.norm(vector)# 角度
def angle_between(v1, v2):""" Returns the angle in radians between vectors 'v1' and 'v2'::>>> angle_between((1, 0, 0), (0, 1, 0))1.5707963267948966>>> angle_between((1, 0, 0), (1, 0, 0))0.0>>> angle_between((1, 0, 0), (-1, 0, 0))3.141592653589793"""v1_u = unit_vector(v1)v2_u = unit_vector(v2)return np.arccos(np.clip(np.dot(v1_u, v2_u), -1.0, 1.0))# 点乘
def dotproduct(v1, v2):return sum((a * b) for a, b in zip(v1, v2))# 向量的长度
def length(v):return math.sqrt(dotproduct(v, v))# 向量角度
def angle(v1, v2):return math.acos(dotproduct(v1, v2) / (length(v1) * length(v2)))def funcChamfer(ptA, ptB, ptC, lR):# ABC点 组成的部分向量vBA = [ptA[0] - ptB[0], ptA[1] - ptB[1]]vBC = [ptC[0] - ptB[0], ptC[1] - ptB[1]]# 求ABC的夹角aABC = angle_between(vBA, vBC)print(f'ABC的夹角 Radius {aABC}, Angle:{180.0 / math.pi * aABC}')# 向量 BA BC的长度lBA = length(vBA)lBC = length(vBC)print(f'向量 BA BC的长度  lBA:{lBA}, lBC:{lBC}')# 获得 BA BC 最短边边长 lShort# 以及需要长边的端点 ptLast, 用于计算D点lShort = 0  # 存储 AB BC中, 短边的边长ptShortS = None # 存储短边的起始点vShort = None    # 存储短边的向量vLong = None    # 存储长边的向量if(lBA <= lBC):lShort = lBAptShortS = ptAvShort = vBAvLong = vBCelse:lShort = lBCptShortS = ptCvShort = vBCvLong = lBA# --------------------求D点方式1(三角函数,复杂,仅做示范):# 和X轴的夹角aShort = angle_between([1, 0], vShort)aLong = angle_between([1, 0], vLong)print(f'短边和X轴的夹角: Radius: {aShort}, Angle:{180.0 / math.pi * aShort}')print(f'长边和X轴的夹角: Radius: {aLong}, Angle:{180.0 / math.pi * aLong}')test = dotproduct(vBC, [1, 0])print(f'Test {test}')ptD = []ptD.append(ptB[0] + lShort * math.cos(math.pi * 2 - aLong))ptD.append(ptB[1] + lShort * math.sin(math.pi * 2 - aLong))print(f'point D:({ptD[0]}, {ptD[1]})')# --------------------求D点方式2(向量法):# BC (长边)转单位向量:vNBC = unit_vector(vLong)x = [ptB[0], ptB[1]] + (vNBC * lShort)print(f'{vNBC}, ptD: {x}')# --------------------# AD点的中点PptPX = (ptD[0] + ptShortS[0]) * 0.5ptPY = (ptD[1] + ptShortS[1]) * 0.5 print(f'point P:({ptPX}, {ptPY})')# BP向量vBP = [ptPX - ptB[0], ptPY - ptB[1]]# 假定点为 X, X到AB的垂线为 XM,且XM = lR# 角ABP度数为 ABC的一半, 已知角度与XM的长度,# 则可求出 BX 长度 lBXlBX = lR / math.sin(aABC * 0.5)ptX = ptB + unit_vector(vBP) * lBXprint(f'ptX: {ptX}')return ptXif __name__ == '__main__':# AB,BC两线段交于B点  A,B,C如下ptA = [707, 181]ptB = [850, 640]    # 公共点ptC = [1578, 167]lR = 130.0   # 倒角圆半径ptX = funcChamfer(ptA, ptB, ptC, lR)print(f'以此点: {ptX} 为圆心,绘制圆弧') 
ABC的夹角 Radius 1.2966305334118693, Angle:74.29145715229679
向量 BA BC的长度  lBA:480.7598152924181, lBC:868.1664586932624
短边和X轴的夹角: Radius: 1.8728126012699295, Angle:107.30425787168404
长边和X轴的夹角: Radius: 0.5761820678580603, Angle:33.01280071938726
Test 728
point D:(1253.1405982438891, 378.0693640530776)
[ 0.83854887 -0.54482639], ptD: [1253.14059824  378.06936405]
point P:(980.0702991219446, 279.5346820265388)
ptX: [923.07255377 437.49319016]
以此点: [923.07255377 437.49319016] 为圆心,绘制圆弧

cpp算法:

待补充


http://chatgpt.dhexx.cn/article/b5rWQQai.shtml

相关文章

[控制算法]

[常用控制算法] 0.博览众长 0.1 视频 1. DR_CAN b站 0.2 文章 1.控制算法整理 0.3 传统 VS 现代控制算法 1. 传统 传统控制算法&#xff1a;PID&#xff0c;模糊&#xff0c;神经网络控制算法。 2. 现代 现代控制算法有比例&#xff0c;LQR算法(用于线性系统)&#x…

求树的直径证明

树的直径&#xff08;最长路&#xff09; 的详细证明 主要是利用了反证法&#xff1a; 假设 s-t这条路径为树的直径&#xff0c;或者称为树上的最长路 现有结论&#xff0c;从任意一点u出发搜到的最远的点一定是s、t中的一点&#xff0c;然后在从这个最远点开始搜&#xff0c;就…

树的直径和树的重心

1.树包括有根树和无根树&#xff0c;有根树是有向图的子图&#xff0c;无根树是无向图的子图&#xff0c;都满足边数等于节点数减一。根是入度为零或没有父亲的节点 2.树的直径&#xff1a;树上最长的简单路径&#xff08;不重复经过点的路径&#xff09; 3.求解算法&#xf…

树的直径总结

树的直径 一、定义 在一棵树中&#xff0c;最远的两个子节点之间的距离被称为树的直径&#xff1b; 链接这两个点的路径被称为树的最长链&#xff1b; 有两种求法&#xff0c;时间复杂度均为 O ( n ) O(n) O(n) &#xff1b; 二、树形DP 1. 状态 由于一个点的最长路通过…

基础算法 - 树的直径

题目地址&#xff1a;https://leetcode-cn.com/problems/tree-diameter/ 1245. 树的直径 难度中等48收藏分享切换为英文接收动态反馈 给你这棵「无向树」&#xff0c;请你测算并返回它的「直径」&#xff1a;这棵树上最长简单路径的 边数。 我们用一个由所有「边」组成的数…

树的直径-c++

题目 实验室里原先有一台电脑(编号为1)&#xff0c;最近氪金带师咕咕东又为实验室购置了N-1台电脑&#xff0c;编号为2到N。每台电脑都用网线连接到一台先前安装的电脑上。但是咕咕东担心网速太慢&#xff0c;他希望知道第i台电脑到其他电脑的最大网线长度&#xff0c;但是可怜…

求树的直径算法以及证明

以下为两次dfs&#xff08;bfs&#xff09;的做法以及正确性证明。 算法步骤 &#xff08;1&#xff09;任取树上一点S&#xff0c;以S为源点BFS得S到各个顶点的d值&#xff1b; &#xff08;2&#xff09;取d值最大者之一为P&#xff0c;再以P为源点BFS得P到各个顶点的d值&am…

求树的直径

树的直径&#xff0c;即树上的最长路径&#xff0c;显然&#xff0c;树的直径可以有很多条&#xff08;考虑一棵菊花&#xff09;。 接下来我们考虑如何求出一棵树的直径。有很多种O(n)的算法。 算法1&#xff1a;我们任取树中的一个节点x&#xff0c;找出距离它最远的点y&am…

数据结构 树的直径

学习的最大理由是想摆脱平庸&#xff0c;早一天就多一份人生的精彩&#xff1b;迟一天就多一天平庸的困扰。 学习日记 目录 学习日记 一、定义 二、两次DFS 定理&#xff1a; 反证法证明&#xff1a; 1、若y在d(t,s)上 2、若y不在d(s,t)上&#xff0c;且d(y,z)与d(s.t)…

树的直径(最长的简单路径)

题解&#xff1a;分析一下&#xff0c;由于是树&#xff0c;所以两点之间的路径有且只有一条&#xff0c;为了求出欧拉路&#xff0c;所以必然会向回走&#xff0c;从递归的角度来看&#xff0c;假设x看作一个树根&#xff0c;有t个孩子y1…yt。其中每个孩子为根的子树欧拉路都…

树的直径概念及求解

文章目录 1. 使用两次DFS求得树的直径2. 使用树形DP求得树的直径3. 性质4. 参考文献和习题 树上任意两节点之间最长的简单路径即为树的「直径」。显然&#xff0c;一棵树可以有多条直径&#xff0c;他们的长度相等。可以用两次 D F S / B F S DFS/BFS DFS/BFS 或者树形 D P D…

树的直径两种求法

首先先介绍一下什么是树的直径&#xff0c;树的直径就是树中所有最短路经距离的最大值。 求树的直径通常有两种方法&#xff0c;一种是通过两次搜索&#xff08;bfs和dfs均可&#xff09;&#xff0c;另一种就是通过树形dp来求了。 先来介绍一下用两次深搜来求树的直径&#x…

树的直径的概念

树的直径的定义: 在一棵树中&#xff0c;每一条边都有权值&#xff0c;树中的两个点之间的距离&#xff0c;定义为连接两点的路径上边权之和&#xff0c; 那么树上最远的两个点&#xff0c;他们之间的距离&#xff0c;就被称之为&#xff0c;树的直径。 树的直径的别称&#x…

树的直径

【定义】 我们将一棵树T ( V&#xff0c;E )的直径定义为maxδ ( u&#xff0c;v ) ( u&#xff0c;v ∈ V )&#xff0c;也就是说&#xff0c;树中所有最短路径距离的最大值即为树的直径。 【做法】 例题传送门Cow Marathon&#xff08;POJ 1985&#xff09; 对于树的直径…

浅谈树的直径

一、定义&#xff1a; 我们将一棵树T(V,E)的直径定义为max(u,v) (u,v∈V)&#xff0c;也就是说&#xff0c;树中所有最短路径距离的最大值即为树的直径。&#xff08;就是树中的最长路径的长度&#xff09; 二、求解树德直径&#xff1a; 求得树的直径有两种方法&#xff0c;一…

3.网络基础-三层路由网络

3.1、IP地址 初识IP地址 • 在IP网络中&#xff0c;通信节点需要有一个唯一的IP地址&#xff1b; • IP地址用于IP报文的寻址以及标识一个节点&#xff1b; • IPv4地址一共32bits&#xff0c;使用点分十进制的形式表示&#xff1b; IP地址的分类 E类是保留地址 公有IP及私有…

计算机网络——配置动态路由实验

配置动态路由实验 实验目的实验软件实验要求实验知识实验步骤实验结果 实验目的 掌握 RIP 协议配置。RIP 协议配置的命令为&#xff1a;router(config)#network <connected-network> 其中参数 <connected-network> 表示路由器的直连网络号。 实验软件 Cisco Pac…

路由技术基础

路由技术是在网络拓扑结构中为不同节点的数据提供传输路径的技术&#xff0c;路由选择算法是其核心内容。路由选择算法分为静态路由选择算法和动态路由选择算法。 一.路由基础 1.路由的基本概念 路由、路由器 &#xff08;1&#xff09;路由 路由是指导IP报文从源发送到目…

网络路由交换 -- 静态路由 和 缺省路由

1.IP路由基础 1.什么是静态路由&#xff1f; 静态路由是由管理员手工添加的路由条目&#xff1b;通过静态路由添加的都是非直连网段。 2.静态路由的特点&#xff1f; 静态路由的添加和删除都需要手工完成&#xff1b;静态路由无法适应网络的动态变更&#xff0c;即缺乏适应…

cisco packet tracer配置网络路由

广州大学 计算机网络实验 配置网络路由 利用packet tracer搭建如图网络 中间是三个路由器&#xff0c;两边各接一台计算机。 首先先把网络搭建出来 1是路由器&#xff0c;2是终端设备&#xff0c;3是连接设备的线缆。左键点击1或者2或3&#xff0c;区域4就会出现不同的路由器…