遇到一个有问题,三顾大牛求辅佐!!
1.问题:
现有一条线段,已知线段的两个端点。
求出该线段的中点,以该中点半径为 smallRadius 的圆,求该线段中垂线与圆的两个交点。2.按理说:
过圆中心做一条直线,必有2解(画图可以看到直线和圆有两个交点)3.蛋疼的地方:
求解的过程中竟然时不时的出现 delta = b^2-4*a*c < 0 的情况,和2 严重矛盾。4.我的测试方案:
我写了一个方法,传入线段的两个点,和以线段中点为圆心的一个圆。
我100%确定,该线段的长度大于上述圆的直径(必须保证有两个交点么~)。
返回一个点数组,点数组包含了2解。5。尾声:
为什么出现 delta < 0 这种奇葩的情况,求指点。
如能点醒我这块朽木,100整分奉送,在线等!!高手素来~~~代码如下:package org.bruce.vertices.controller.geometry;/**
* @author Bruce Yang
* 用于打印调试~
*/
public class CGDbg {
public static final boolean DEBUG_MODE = true;
// 方便进行调试信息的输出,开关~
public static void println(Object info) {
if(DEBUG_MODE) {
System.out.println(info);
}
}
public static void print(Object info) {
if(DEBUG_MODE) {
System.out.print(info);
}
}
}***********************************************package org.bruce.vertices.controller.geometry;
/**
* @author BruceYang
* 这个是对通用一次直线方程 A*x + B*y + C = 0 的封装~
* 本来封装的是斜截式,不过发现当斜率k不存在的时候会比较麻烦,因此该用一般式
* 再个就是接着用一般式的演变方式 x + B/A*y + C/A = 0,但是考虑到可能存在x == 0 的情况,因此又舍弃~
*
* 娘的,一般式还是他妈的无济于事啊,改回斜截式,多提供两个成员变量:
* 一个boolean表示k是否存在,一个额外的float表示k不存在的时候直线方程 x=***, *** 等于多少~
*/
public class CGLine {
// 特别声明为public类型,免得到时候访问的时候麻烦,到时候直接点就行了
private boolean kExists; // 大部分情况下 k 都应该是存在的,因此提供一个 true 的默认值~ public float k = 77885.201314f;
public float b = 13145.207788f;
public float extraX = 52077.881314f;
/**
* 这是当 k 存在时的构造方法~
* @param k
* @param b
*/
public CGLine(float k, float b) {
this.kExists = true;
this.k = k;
this.b = b;
}
/**
* 已知两点,求直线的方程~
* @param p1
* @param p2
*/
public CGLine(CGPoint p1, CGPoint p2) {
if((p1.x - p2.x) != 0) {
CGDbg.println("y = k*x + b, k exits!!");
this.kExists = true;
this.k = (p1.y - p2.y)/(p1.x - p2.x);
this.b = (p1.y - p1.x * k);
} else {
CGDbg.println("y = k*x + b, k doesn't exists!!");
// 如果走进这个分支,表示直线垂直于x轴,斜率不存在,保留k的默认值~
this.kExists = false;
this.extraX = p1.x;
}
CGDbg.print("过p1("+p1.x+", " +p1.y + "), p2("+p2.x+", "+p2.y+")两点的直线方程表达式为: ");
if(kExists) {
CGDbg.println("y = " + k + "*x + " + b);
} else {
CGDbg.println("x = " + extraX + "(垂直于x轴!)");
}
}
/**
* 点斜式~
* @param p 某点
* @param k 过该点的直线的斜率
*/
public CGLine(float k, CGPoint p) {
/**
* (y-y') = k*(x-x')
* 变形成斜截式为:
* y = k*x + y' - k*x'
* k = k, b = y'-k*x'
*/
this.kExists = true;
this.k = k;
this.b = p.y - k * p.y;
}
/**
* 这是当 k 不存在时的构造方法~
* @param extraX
*/
public CGLine(float extraX) {
this.kExists = false;
this.extraX = extraX;
}
@Override
public String toString() {
return "Line.toString()方法被调用,y = k*x + b斜截式, k=" + this.k + ", b=" + this.b
+", kExists=" + this.kExists + ", extraX=" + this.extraX;
}
public boolean iskExists() {
return kExists;
}
public void setkExists(boolean kExists) {
this.kExists = kExists;
}
}***********************************************package org.bruce.vertices.controller.geometry;/**
* @author BruceYang
* 对点的抽象~
*/
public class CGPoint {
public float x;
public float y;
public CGPoint() {
}
public CGPoint(float x, float y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "x=" + this.x + ", y=" + this.y;
}
}***********************************************package org.bruce.vertices.controller.geometry;/**
* @author BruceYang
*/
public class CGGeometryLib {
/**
* @param p0 第一个点的坐标
* @param p1 第二个点的坐标
* @return 两个点之间的距离
* 计算出两点之间的距离
*/
public static float getDistanceBetween2Points(CGPoint p0, CGPoint p1) {
float distance = (float)Math.sqrt(Math.pow(p0.y - p1.y, 2) + Math.pow(p0.x - p1.x, 2));
return distance;
}
/**
* 获取传入两点的中点~
* @param p1
* @param p2
* @return
*/
public static CGPoint getMiddlePoint(CGPoint p1, CGPoint p2) {
return new CGPoint((p1.x + p2.x) / 2.0f, (p1.y + p2.y) / 2.0f);
}
/**
* 封装一下 Math 的 pow 、sqrt 方法,调用起来方便一些~
* @param d1
* @param d2
* @return
*/
public static double pow(double d1, double d2) {
return Math.pow(d1, d2);
}
public static double sqrt(double d) {
return Math.sqrt(d);
}
public static double sin(double theta) {
return Math.sin(theta);
}
public static double cos(double theta) {
return Math.cos(theta);
}
/**
* 传入线段的两个端点,获取中点,以该中点为圆心做半径为 radius 的圆,
* 经过线段中点做线段的垂线,返回垂线与圆的两个交点~
* Objective-C 里面的结果有点儿问题,不知道是什么原因,来java 里面碰碰有运气~
* @param p1 线段端点1
* @param p2 线段端点2
* @param radius 圆半径
* @return 线段中垂线与圆的两个交点~
*/
public static CGPoint[] getWhatIWanted(CGPoint p1, CGPoint p2, float radius) {
CGPoint[] target = new CGPoint[2];
CGPoint pMiddle = getMiddlePoint(p1, p2);
// float segLength = getDistanceBetween2Points(p1, p2);
CGLine l1 = new CGLine(p1, p2);
if(l1.iskExists()) {
if(l1.k != 0) {
float kOfNewLine = -1 / l1.k;
CGLine newLine = new CGLine(kOfNewLine, pMiddle);
// 经过数学运算,得出二元一次方程组的表达式
double A = pow(newLine.k, 2) + 1;
double B = 2 * (newLine.k * newLine.b - newLine.k * pMiddle.y - pMiddle.x);
double C = pow(pMiddle.x, 2) + pow((newLine.b - pMiddle.y), 2) - pow(radius, 2);
double delta = pow(B, 2) - 4 * A * C;
if(delta < 0) { // 经实践检验有一定几率走入该分支,必须做特殊化处理~
CGDbg.println("竟然会无解,他妈的怎么回事儿啊!");
target[0] = new CGPoint(pMiddle.x, pMiddle.y - radius);
target[1] = new CGPoint(pMiddle.x, pMiddle.y + radius);
} else {
double x1 = (-B + sqrt(delta)) / (2 * A);
double y1 = newLine.k * x1 + newLine.b;
target[0] = new CGPoint((float)x1, (float)y1);
double x2 = (-B - sqrt(delta)) / (2 * A);
double y2 = newLine.k * x2 + newLine.b;
target[1] = new CGPoint((float)x2, (float)y2);
}
} else {
target[0] = new CGPoint(pMiddle.x, pMiddle.y - radius);
target[1] = new CGPoint(pMiddle.x, pMiddle.y + radius);
}
} else {
target[0] = new CGPoint(pMiddle.x - radius, pMiddle.y);
target[1] = new CGPoint(pMiddle.x + radius, pMiddle.y);
}
System.out.println("target[0] 距离中点的距离为:" + getDistanceBetween2Points(target[0], pMiddle));
System.out.println("target[1] 距离中点的距离为:" + getDistanceBetween2Points(target[1], pMiddle));
return target;
}
/**
* @param args
*/
public static void main(String[] args) {
double currentRadian = 0;
double deltaRadian = Math.PI / 180;
float bigRadius = 50;
float smallRadius = 20;
CGPoint origin = new CGPoint(0, 0); // 原点~
CGPoint tail = null; // tail 是尾巴、末梢的意思~
for(int i = 0; i < 360; ++ i) {
System.out.println(" -- 第 "+ i + "度!");
tail = new CGPoint(bigRadius*(float)cos(currentRadian), bigRadius*(float)sin(currentRadian));
currentRadian += deltaRadian;
getWhatIWanted(origin, tail, smallRadius);
}
}
}
1.问题:
现有一条线段,已知线段的两个端点。
求出该线段的中点,以该中点半径为 smallRadius 的圆,求该线段中垂线与圆的两个交点。2.按理说:
过圆中心做一条直线,必有2解(画图可以看到直线和圆有两个交点)3.蛋疼的地方:
求解的过程中竟然时不时的出现 delta = b^2-4*a*c < 0 的情况,和2 严重矛盾。4.我的测试方案:
我写了一个方法,传入线段的两个点,和以线段中点为圆心的一个圆。
我100%确定,该线段的长度大于上述圆的直径(必须保证有两个交点么~)。
返回一个点数组,点数组包含了2解。5。尾声:
为什么出现 delta < 0 这种奇葩的情况,求指点。
如能点醒我这块朽木,100整分奉送,在线等!!高手素来~~~代码如下:package org.bruce.vertices.controller.geometry;/**
* @author Bruce Yang
* 用于打印调试~
*/
public class CGDbg {
public static final boolean DEBUG_MODE = true;
// 方便进行调试信息的输出,开关~
public static void println(Object info) {
if(DEBUG_MODE) {
System.out.println(info);
}
}
public static void print(Object info) {
if(DEBUG_MODE) {
System.out.print(info);
}
}
}***********************************************package org.bruce.vertices.controller.geometry;
/**
* @author BruceYang
* 这个是对通用一次直线方程 A*x + B*y + C = 0 的封装~
* 本来封装的是斜截式,不过发现当斜率k不存在的时候会比较麻烦,因此该用一般式
* 再个就是接着用一般式的演变方式 x + B/A*y + C/A = 0,但是考虑到可能存在x == 0 的情况,因此又舍弃~
*
* 娘的,一般式还是他妈的无济于事啊,改回斜截式,多提供两个成员变量:
* 一个boolean表示k是否存在,一个额外的float表示k不存在的时候直线方程 x=***, *** 等于多少~
*/
public class CGLine {
// 特别声明为public类型,免得到时候访问的时候麻烦,到时候直接点就行了
private boolean kExists; // 大部分情况下 k 都应该是存在的,因此提供一个 true 的默认值~ public float k = 77885.201314f;
public float b = 13145.207788f;
public float extraX = 52077.881314f;
/**
* 这是当 k 存在时的构造方法~
* @param k
* @param b
*/
public CGLine(float k, float b) {
this.kExists = true;
this.k = k;
this.b = b;
}
/**
* 已知两点,求直线的方程~
* @param p1
* @param p2
*/
public CGLine(CGPoint p1, CGPoint p2) {
if((p1.x - p2.x) != 0) {
CGDbg.println("y = k*x + b, k exits!!");
this.kExists = true;
this.k = (p1.y - p2.y)/(p1.x - p2.x);
this.b = (p1.y - p1.x * k);
} else {
CGDbg.println("y = k*x + b, k doesn't exists!!");
// 如果走进这个分支,表示直线垂直于x轴,斜率不存在,保留k的默认值~
this.kExists = false;
this.extraX = p1.x;
}
CGDbg.print("过p1("+p1.x+", " +p1.y + "), p2("+p2.x+", "+p2.y+")两点的直线方程表达式为: ");
if(kExists) {
CGDbg.println("y = " + k + "*x + " + b);
} else {
CGDbg.println("x = " + extraX + "(垂直于x轴!)");
}
}
/**
* 点斜式~
* @param p 某点
* @param k 过该点的直线的斜率
*/
public CGLine(float k, CGPoint p) {
/**
* (y-y') = k*(x-x')
* 变形成斜截式为:
* y = k*x + y' - k*x'
* k = k, b = y'-k*x'
*/
this.kExists = true;
this.k = k;
this.b = p.y - k * p.y;
}
/**
* 这是当 k 不存在时的构造方法~
* @param extraX
*/
public CGLine(float extraX) {
this.kExists = false;
this.extraX = extraX;
}
@Override
public String toString() {
return "Line.toString()方法被调用,y = k*x + b斜截式, k=" + this.k + ", b=" + this.b
+", kExists=" + this.kExists + ", extraX=" + this.extraX;
}
public boolean iskExists() {
return kExists;
}
public void setkExists(boolean kExists) {
this.kExists = kExists;
}
}***********************************************package org.bruce.vertices.controller.geometry;/**
* @author BruceYang
* 对点的抽象~
*/
public class CGPoint {
public float x;
public float y;
public CGPoint() {
}
public CGPoint(float x, float y) {
this.x = x;
this.y = y;
}
@Override
public String toString() {
return "x=" + this.x + ", y=" + this.y;
}
}***********************************************package org.bruce.vertices.controller.geometry;/**
* @author BruceYang
*/
public class CGGeometryLib {
/**
* @param p0 第一个点的坐标
* @param p1 第二个点的坐标
* @return 两个点之间的距离
* 计算出两点之间的距离
*/
public static float getDistanceBetween2Points(CGPoint p0, CGPoint p1) {
float distance = (float)Math.sqrt(Math.pow(p0.y - p1.y, 2) + Math.pow(p0.x - p1.x, 2));
return distance;
}
/**
* 获取传入两点的中点~
* @param p1
* @param p2
* @return
*/
public static CGPoint getMiddlePoint(CGPoint p1, CGPoint p2) {
return new CGPoint((p1.x + p2.x) / 2.0f, (p1.y + p2.y) / 2.0f);
}
/**
* 封装一下 Math 的 pow 、sqrt 方法,调用起来方便一些~
* @param d1
* @param d2
* @return
*/
public static double pow(double d1, double d2) {
return Math.pow(d1, d2);
}
public static double sqrt(double d) {
return Math.sqrt(d);
}
public static double sin(double theta) {
return Math.sin(theta);
}
public static double cos(double theta) {
return Math.cos(theta);
}
/**
* 传入线段的两个端点,获取中点,以该中点为圆心做半径为 radius 的圆,
* 经过线段中点做线段的垂线,返回垂线与圆的两个交点~
* Objective-C 里面的结果有点儿问题,不知道是什么原因,来java 里面碰碰有运气~
* @param p1 线段端点1
* @param p2 线段端点2
* @param radius 圆半径
* @return 线段中垂线与圆的两个交点~
*/
public static CGPoint[] getWhatIWanted(CGPoint p1, CGPoint p2, float radius) {
CGPoint[] target = new CGPoint[2];
CGPoint pMiddle = getMiddlePoint(p1, p2);
// float segLength = getDistanceBetween2Points(p1, p2);
CGLine l1 = new CGLine(p1, p2);
if(l1.iskExists()) {
if(l1.k != 0) {
float kOfNewLine = -1 / l1.k;
CGLine newLine = new CGLine(kOfNewLine, pMiddle);
// 经过数学运算,得出二元一次方程组的表达式
double A = pow(newLine.k, 2) + 1;
double B = 2 * (newLine.k * newLine.b - newLine.k * pMiddle.y - pMiddle.x);
double C = pow(pMiddle.x, 2) + pow((newLine.b - pMiddle.y), 2) - pow(radius, 2);
double delta = pow(B, 2) - 4 * A * C;
if(delta < 0) { // 经实践检验有一定几率走入该分支,必须做特殊化处理~
CGDbg.println("竟然会无解,他妈的怎么回事儿啊!");
target[0] = new CGPoint(pMiddle.x, pMiddle.y - radius);
target[1] = new CGPoint(pMiddle.x, pMiddle.y + radius);
} else {
double x1 = (-B + sqrt(delta)) / (2 * A);
double y1 = newLine.k * x1 + newLine.b;
target[0] = new CGPoint((float)x1, (float)y1);
double x2 = (-B - sqrt(delta)) / (2 * A);
double y2 = newLine.k * x2 + newLine.b;
target[1] = new CGPoint((float)x2, (float)y2);
}
} else {
target[0] = new CGPoint(pMiddle.x, pMiddle.y - radius);
target[1] = new CGPoint(pMiddle.x, pMiddle.y + radius);
}
} else {
target[0] = new CGPoint(pMiddle.x - radius, pMiddle.y);
target[1] = new CGPoint(pMiddle.x + radius, pMiddle.y);
}
System.out.println("target[0] 距离中点的距离为:" + getDistanceBetween2Points(target[0], pMiddle));
System.out.println("target[1] 距离中点的距离为:" + getDistanceBetween2Points(target[1], pMiddle));
return target;
}
/**
* @param args
*/
public static void main(String[] args) {
double currentRadian = 0;
double deltaRadian = Math.PI / 180;
float bigRadius = 50;
float smallRadius = 20;
CGPoint origin = new CGPoint(0, 0); // 原点~
CGPoint tail = null; // tail 是尾巴、末梢的意思~
for(int i = 0; i < 360; ++ i) {
System.out.println(" -- 第 "+ i + "度!");
tail = new CGPoint(bigRadius*(float)cos(currentRadian), bigRadius*(float)sin(currentRadian));
currentRadian += deltaRadian;
getWhatIWanted(origin, tail, smallRadius);
}
}
}
/**
* (y-y') = k*(x-x')
* 变形成斜截式为:
* y = k*x + y' - k*x'
* k = k, b = y'-k*x'
*/
this.kExists = true;
this.k = k;
this.b = p.y - k * p.y;
}
this.b = p.y - k*p.x;
这里错了,查了好久,先查delta发现没问题。在查k也没问题。中点也没问题
查到这里出问题了
float kOfNewLine = -1 / l1.k;
CGLine newLine = new CGLine(kOfNewLine, pMiddle);
发现那个b有错误。。
y = k*x + b, k exits!!
过p1(0.0, 0.0), p2(-50.0, 5.390303E-13)两点的直线方程表达式为: y = -1.0780606E-14*x + 0.0
竟然会无解,他妈的怎么回事儿啊!
target[0] 距离中点的距离为:20.0
target[1] 距离中点的距离为:20.0
public static void main(String[] args) {
test(-3, 7, 5, -3, 3);
} static void test(double x1,double y1,double x2,double y2,double r){
double k = (y2 -y1) / (x2 - x1);//斜率
double k2 = -1.0 / k;//中垂线斜率
double midX = (x1 + x2) / 2;//中点x
double midY = (y1 + y2) / 2;//中点y
double a = Math.atan(k2);//中垂线与x轴夹角
double y = r * Math.sin(a);//y轴偏移量
double x = r * Math.cos(a);//x轴偏移量
double resultX1 = k > 0 ? midX - x : midX + x;//上方交点x坐标
double resultY1 = midY + y;//上方交点y坐标
double resultX2 = k > 0 ? midX + x : midX - x ;//下方交点x坐标
double resultY2 = midY - y;//下方交点y坐标
System.out.println("result: ");
System.out.println(resultX1 + "," + resultY1);
System.out.println(resultX2 + "," + resultY2);
}
}
public class NiDongDe
{ /**
* @param args
*/
public static void main(String[] args)
{
Point one = new Point(0, 0);
Point two = new Point();
double smallR = 20;
double bigR = 50;
for (int i = 0; i < 360; ++i)
{
two.x = bigR * Math.cos(i * Math.PI / 180);
two.y = bigR * Math.sin(i * Math.PI / 180);
System.out.println(i + "度 " + two.toString() + " " + countCrossPoint(one, two, smallR));
}
} private static String countCrossPoint(Point one, Point two, double smallR)
{
// 转90度后use ax + by + c = 0
double a = 1;
double b = 1;
double k = 0;
if (one.x == two.x || (Math.abs(one.x - two.x))<Math.pow(1, -10))
{
a = 0;
}
else if (one.y == two.y|| (Math.abs(one.y - two.y))<Math.pow(1, -10))
{
b = 0;
}
else
{
k = (two.x - one.x) / (two.y - one.y);
} if (k == 0)
{
// 两种特殊情况
if (a == 0)
{
double y = (one.y + two.y) / 2;
double x1 = smallR + (one.x + two.x) / 2;
double x2 = (one.x + two.x) / 2 - smallR;
return "(" + x1 + ", " + y + ") (" + x2 + ", " + y + ")";
}
else if (b == 0)
{
double x = (one.x + two.x) / 2;
double y1 = smallR + (one.y + two.y) / 2;
double y2 = (one.y + two.y) / 2 - smallR;
return "(" + x + ", " + y1 + ") (" + x + ", " + y2 + ")"; }
}
else
{
// 一般情况了啦
// 公式整理你懂的:
// [(y2-y1)/(x2-x1)*x + y2 -x2*(y2-y1)/(x2-x1) -(y1+y2)/2]^2 + [x - (x1+x2)/2]^2 = smallR^2
// |<- p ->| |<- w ->| |<- q ->|
double p = (two.y -one.y)/(two.x - one.x);
double w = two.y - two.x * (two.y - one.y)/(two.x - one.x) - (one.y + two.y)/2;
double q = (one.x + two.x)/2;
// reserve = y2 -x2*(y2-y1)/(x2-x1) we'll use it later
double reserve = two.y - two.x*(two.y - one.y)/(two.x - one.x);
// now we have [px + w]^2 + [x - q]^2 = smallR^2
//再整理你懂的:
// (p^2 + 1)x^2 + (2pw -2q)x + (q^2-smallR^2)=0
// a1 b1 c1
double a1 = Math.pow(p, 2) + 1;
double b1 = 2*p*w - 2*q;
double c1 = Math.pow(q, 2) - Math.pow(smallR, 2);
// finally~
double x1 = (-1*b1 + Math.sqrt((Math.pow(b1, 2) - 4*a1*c1))) / (2*a1);
double x2 = (-1*b1 - Math.sqrt((Math.pow(b1, 2) - 4*a1*c1))) / (2*a1);
// y = px + reserve
double y1 = p * x1 + reserve;
double y2 = p * x1 + reserve;
return "(" + x1 + ", " + y1 + ") (" + x2 + ", " + y2 + ")";
}
return "";
}
}class Point
{ public double x; public double y; Point()
{ } Point(double x, double y)
{
this.x = x;
this.y = y;
}
public String toString(){
return "(" + this.x + ", " + this.y + ")";
}
}e...我也搞了一下,少了些判断,LZ您看下呢,结果送上。
不过,哥们儿你是印象派啊,不足还是比较明显:
直接就求了线段和圆的交点,whatIWant是线段的中垂线和圆的两个交点
另外,少点儿测试没有说服力啊
最后,再次感谢!!
中点 x0,y0,源直线的角度d。中垂线角度是d- 90 小圆半径 r
一个点是
x1 = x0 + r*cos(d- 90)
y1 = y0 + r*sin(d- 90)另外一个点x2 = x0 - r*cos(d- 90)
y2 = y0 - r*sin(d- 90)
前面说到在180度的时候还是无解,我发现原因了,
主要还是精度不过,出现结果误差,换成double之后就精确多了
没有再出现无解的情况。
其实我的主要问题应该是在无解这个问题上面~
嘿嘿,问题圆满解决,还有赖于各位哥们儿的给力回复啊~
让我重温了大学时代发帖等回帖的快感、期待