首页
学习
活动
专区
工具
TVP
发布
您找到你想要的搜索结果了吗?
是的
没有找到

java 计算坐标点距离,平行线交点算法详解

前言 主要记录一些关于坐标线段的计算方法。因为经常会碰见,需要在平面上,计算坐标点。 例如两个坐标点之间的距离,两个线段是否平行,两个不相交的线段交点。 由于程序中的坐标原点,都是左上角开始的。...Math.sqrt()是 java 提供的开平方工具。 我们得到的X轴的距离和Y轴的距离,都是相对于x轴和y轴垂直的。所以这两个距离组合的就是直角三角形的两条直角边。...计算两个线段交点 计算:在平面直角坐标系中点A和点B组成了线段A,点C和点D组成了线段B。如果他们有交点。那么交点坐标是多少。 而在平面直角坐标系中,同一平面内两条直线只有相交和平行两种情况。...我们如果知道交点的X轴就可以计算出Y轴坐标。反之当我们知道Y轴坐标也可以计算出X轴坐标。 3.2 计算线段交点 在某种情况下,交点坐标的某个值是可以快速确定的。例如其中一条线段垂直X轴。...//解释2:我在其他方法中判断过平行线的情况,所以如果线段1垂直,那么线段2肯定不会垂直。 //因为是交点,所以交点坐标是满足线段2的斜率公式的。

43230

空间或平面判断两线段相交(求交点)

(s >= 0) && (s <= 1)) { flag = true; } } return flag; } 可以看出这个算法其实并不严密,其实缺少了对一些极端条件的判断,比如与坐标轴平行的情况...同侧法 这种算法的思想是:如果两条线段相交,那么一条线段的两端点必然位于另一条线段的两端点的异侧。那么问题就可以转换成点是否在一条线段的同侧。...不过这个算法可以判断定性判断,无法定量判断准确的交点。而且实际使用过程中,似乎精度不太准确(个人实验结论,尤其是位于三角形边上的点)。 2.3. 向量方程法 2.3.1....如果要求两线段交点,很显然可以将两个线段进行联立: \[\begin{cases} P = O_1 + t_1 D_1 \\ P = O_2 + t_2 D_2 \\ \end{cases} \]...可以继续求解原来的2行2列的线性方程组,只有当得到的t1,t2也能满足Z方向上的式子成立,才能说明存在交点。 3. 参考 计算几何-判断线段是否相交 详细代码

2K10

解析几何:计算两条线段交点

今天来实现计算两条线段交点的解析几何算法。 我们要实现 getLineSegIntersection 方法:提供两条线段,计算它们的交点。 每条线段会用两个点坐标表示。...如果无解或多解,说明直线平行,交点不存在。 如果有解,可拿到唯一交点,但也只能说明直线有交点,还需要判断线段是否有交点。 所以我们需要判断交点是否在线段的区间上。如果是,说明两线段交点,返回交点。...变体1:两线段是否有交点。 返回值换成布尔值即可。 判断两线段是否有交点,我之前还写了另一种解法,感兴趣可以看看: 《几何算法:判断两条线段是否相交》 变体2:计算两直线的交点。...把判断直线交点是否在线段上的逻辑去掉,然后直接返回点坐标即可。 优化点 1、重叠但却只有一个交点的情况。...结尾 总结一下,求两线段交点,本质就是解方程,需要用到克莱姆法则,计算出来的交点是直线交点,不一定是线段交点,需要再判断点是否在线段范围内。 不复杂,就是有一点点小细节。

24920

计算几何算法概览

因此我们可以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序(X坐标小的排在前面,对于X坐标相同的点,Y坐标小的排在前面,这种排序准则也是为了保证水平和垂直情况的判断正确),这样相邻的两个点就是在线段上相邻的两交点...若P1的纵坐标和Q1的纵坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段交点"的算法求他们的交点(该方法在前文已讨论过);     ii....如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1平行于Y轴,则交点坐标为Q1的横坐标,代入到L0的直线方程中可以计算出交点坐标;  4....若P1的横坐标和Q1的横坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段交点"的算法求他们的交点(该方法在前文已讨论过);     ii....如果P1和P2纵坐标不同,但是Q1和Q2纵坐标相同,即L1平行于X轴,则交点坐标为Q1的纵坐标,代入到L0的直线方程中可以计算出交点坐标;  6.

1.4K40

形状识别之直线检测

在极坐标系下的一点即定义一条直线,其中表示极坐标原点到直线的距离,为如图所示夹角。如图5。 图5 此时不难看出,身份证同一边上的线段应该具有相近的极坐标点。...具体做法是,先选取极坐标系的原点O为图像的重点(w/2,h/2)。建立笛卡尔坐标系;其中是图像坐标系。极坐标系与笛卡尔坐标系的转换关系为。因此,当已知一线段的两个端点,即可求解出对应的。...具体角度的计算请参考直线检测之极坐标表示。 代码如下: 将图4中检测到的所有直线线段利用极坐标表示,然后进行分类,同类的直线分配相同的标签号。...如图6红色线段为LSD检测结果,红色直线为线段对应极坐标表示的直线。 ...---- 4.交点计算 这里给出极坐标系下直线的求交点方法,这里主要注意两点:首先,两条直线不是平行的,其次,直线的交点在图像范围内。

2.2K31

挑战程序竞赛系列(83):3.6计算几何基础

题意: 桌上放着n根木棍,木棍i的两端的坐标分别是(pix,piy)和(qix,qiy)(p_{ix}, p_{iy})和(q_{ix}, q_{iy})。...思路: 因为边和边是否相连就看交点是否在线段内,可以把每条线段想象成图中的顶点,只要有交点,就认为可达,最后判断任意两条线段是否相交,只需要判断它们是否可达。...所以问题就转换成了线段线段相交的判断。分为两种情况: 边平行,需要判断任何一条线段的两个顶点是否在另一条线段上。 非平行边,求出两条线段交点,判断交点是否分别在这两条线段内。 ?...代码如下: import java.io.BufferedReader; import java.io.File; import java.io.FileInputStream; import java.io.IOException...; import java.io.InputStream; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.Arrays

61550

位置和方向的世界,计算几何的基本问题

进一步地,如果存在唯一交点,试求出相交的交点坐标 判断线段相交 考虑以下基本问题: 判断平面上两条线段是否相交 输入:4个点,分别表示第一条线段的两个端点和第二条线段的两个端点....可是,问题本身仅仅对相交与否感兴趣而已(虽然后续的计算几何的问题会涉及到求交点坐标), 于是,我们希望发展更为简洁高效的算法来解决这个问题. 首先,两条线段AB 和 CD相交等价于 ?...非规范相交有以下两种情况 情况1: 线段重合, 线段有无穷多个交点. 情况2: 线段有唯一交点,但是此交点恰好是其中一条线段的一个端点....交点坐标 好了,讲清楚了判断线段相交的问题,进一步的问题就是计算交点坐标. 已知平面上两直线 L1(P, u), L2(Q, v) 相交,且恰有一个交点, 试计算该交点坐标....计算相交线段(或者直线)交点坐标的伪代码如下 Point getintersect(cp &p, cp &u, cp &q, cp &v) { return p + sc(u, ((q - p

83210

计算几何之线段相交问题(平面扫描)

给出n条平行于x轴或y轴的线段,输出其交点数 求n条线段交点,可以用抽选配对的方式来遍历所有的情况,这样子时间复杂度为O(n2)....与轴平行的线段相交问题(曼哈顿几何)可以通过平面扫描(sweep)高效求解。平面扫描算法的思路是将一条与x轴(y轴)平行的直线向上(向右)平行移动,在移动过程中寻找交点,这条直线被称为扫描线。...扫描线在每次遇到平面上线段的端点的时候停止移动,并且检查该位置上的线段交点。 为了进行上述的处理,我们需要先将输入的线段的端点按照y的大小进行排序,然后让扫描线向y轴正向移动。...在扫描线移动的过程中,算法会将扫描线穿过的垂直线段(与y轴平行)临时记录下来,等到扫描线与水平线段重叠的时候,检查水平线段的范围内是否存在垂直线段上的点,然后将这些点作为交点输出。...其实我们在处理的时候,只需要按顺序保存线段的端点,并为每个端点标记上它的性质(上下左右),在遇到下端点的时候,把它的横坐标加入二叉搜索树,遇到上端点的时候,把它对应的下端点的横坐标从二叉搜索树中删除。

81530

模拟试题B

,则输出线段SP与裁剪线的交点和P ?...( ) A)多边形被两条扫描线分割成许多梯形,梯形的底边在扫描线上,腰在多边形的边上,并且相间排列; B)多边形与某扫描线相交得到偶数个交点,这些交点间构成的线段分别在多边形内、外,且相间排列;...( ) A)对称变换 B)旋转变换 C)比例变换 D)错切变换 三、判断题(1′*9 = 9′) 1.编码裁剪算法需要求线段与窗口边界的交点,中点分割算法则不需求交点。...在直线段的编码裁剪算法中,按TBRL给出四位编码,若线段端点的编码为1010,说明该端点的X坐标比XR ____________,端点的Y坐标比YT ____________。 3....已知窗口及线段坐标分别为A(0,0)、B(0,6)、C(10,6)、D(10,0),P1(-1,10)、P2(11,0)。试用中点分割法求出P1的最远可见点,当线段长度≤0.5时算法结束。

4.1K10

程序员面试金典 - 面试题 16.13. 平分正方形(数学)

每个正方形的数据square包含3个数值,正方形的左下顶点坐标[X,Y] = [square[0],square[1]],以及正方形的边长square[2]。...所求直线穿过两个正方形会形成4个交点,请返回4个交点形成线段的两端点坐标(两个端点即为4个交点中距离最远的2个点,这2个点所连成的线段一定会穿过另外2个交点)。...2个端点坐标[X1,Y1]和[X2,Y2]的返回格式为{X1,Y1,X2,Y2},要求若X1 != X2,需保证X1 < X2,否则需保证Y1 <= Y2。...: 输入: square1 = {-1, -1, 2} square2 = {0, -1, 2} 输出: {-1,0,2,0} 解释: 直线 y = 0 能将两个正方形同时分为等面积的两部分,返回的两线段端点为...cx2, cy2, r1, r2; r1 = square1[2]/2.0; r2 = square2[2]/2.0; cx1 = square1[0]+r1;//中心坐标

25220

明月机器学习系列029:表格识别(三)表格结构解释

在解释表格之前,我们已经计算得到了每个线段的方程及端点坐标,还有每个交点坐标。在实现之前,首先需要定义一个表格的数据结构,这是我们工作的目标。...2.1 顶点vertexes 这个结构其实比较简单,实现这个其实比较简单,关键就两点: 首先,计算每个交点所在的行和列,不过这稍微有点技巧的是,需要分别对交点的行坐标和列坐标进行聚类,行和列都是使用聚类的方式实现...,只需要对交点的行或者列的坐标进行聚类即可。...2.2 边edges 这个的实现就有点曲折了,开始的时候是通过每个线段聚类行线和列线,然后将交点匹配到对应的行线和列线上来实现的。...然后就只能重构了这个实现,这次的思路不再是从线段聚类出发,而是前面的线段交点图出发,直接统计两交点之间的最大白色像素点的数量,大于一定比例就可以基本判定两交点之间是相连的(显然这个条件也并不是那么强,不过应该够用了

1.3K10

实用技巧 | OpenCV快速计算直线网格线交点坐标(附源码)

导读 本期将介绍使用OpenCV用两种不同的方法实现快速查找计算直线/网格线交点坐标。...直线交点计算思路与常用方法 直线交点的计算这里列举几个比较常用的方法: ① 在知道直线方程的前提下(或知道直线上一点和直线角度),联立方程求解交点坐标(注意数学坐标系和图像坐标系的关系); ② 不知道直线方程...,通过检测直线的方法(例如霍夫变换)计算直线方程,然后联立方程求解交点坐标; ---- 第一种方法当然是最理想的情况,这样计算的交点也最准确。...---- 综上来看,前面两种方法并不是非常好用,下面来介绍两种简单实用的方法: ③ 利用角点检测方法粗定位角点,然后通过形态学操作计算出直线交点位置; ④ 利用直线交点出特征,使用形态学操作直接定位直线交点位置...本文使用方法③和方法④,设置合适的参数即可检测到直线交点位置。

3.1K10
领券