直線
ベクトル使ってあれやこれやはこちら
直線の方程式
計算幾何: 理論の基礎から実装まで (アルゴリズム・サイエンスシリーズ―数理技法編) 単行本 – 2007/1/24 浅野 哲夫 (著)
陽関数
関数の値 $${y}$$ が変数 $${x}$$ の明示的な式として表される関数のこと。つまり $${y = f(x)}$$ の形で表される関数。特に
$$
y=ax+b
$$
を切片形と呼ぶ
2つのパラメータa,b
ただしこの式はy軸に平行な直線を表現できない。
陰関数
ある方程式において、一方の変数が他方の変数の関数として直接表されていない関数のこと。
陰関数定理によれば、ある条件下で、方程式$${ F(x, y) = 0 }$$が与えられたとき、$${ y }$$を$${ x }$$の関数$${ y = f(x) }$$として解くことができるとされるが、この$${ f(x) }$$が直接的には求められない場合がある。このような場合に$${ y }$$を$${ x }$$の陰関数と呼ぶ。
例えば、円の方程式$${ x^2 + y^2 = r^2 }$$は、$${ y }$$を$${ x }$$の関数として直接的に表しはいないが、$${ y }$$は$${ x }$$に依存する関係にある。このとき、$${ y }$$は$${ x }$$の陰関数と考えることができる。
直線の場合、
$$
ax+by+c=0
$$
を特に一般形と呼び、3つのパラメータa,b,cを持つ。
2つの座標指定
直線上の2点、あるいは線分の端点を$${p(x_1,y_1)}$$と$${p(x_2,y_2)}$$とすると。
$$
\frac{y-y_1}{x-x_1}=\frac{y_2-y_1}{x_2-x_1}\\
(x-x_1)(y_2-y_1)=(y-y_1)(x_2-x_1)
$$
$$
y=\frac{y_2-y_1}{x_2-x_1}(x-x_1)+y_1
$$
ただし$${x_1=x_2}$$の時、傾きの分母がゼロになるためしぬ。
$$
m=\frac{y_2-y_1}{x_2-x_1}\\
b=y_1-mx_1
$$
と置くと
$$
y=mx+b
$$
となって切片形となる。また
$$
(x-x_1)(y_2-y_1)=(y-y_1)(x_2-x_1)\\
(y_2-y_1)x-(x_2-x_1)y+x_2y_1-x_1y_2=0
$$
から
$$
a=(y_2-y_1)\\
b=-(x_2-x_1)\\
c=x_2y_1-x_1y_2
$$
であって陰関数$${ax+by+c=0}$$をなす。
この時用関数$${y=mx+b}$$との関係は
$$
m=-\frac{a}{b}\\
b(\text{陽関数})=-\frac{c}{b(\text{陰関数})}
$$
下の式は係数に用いるアルファベットが被っていることに注意。
2つの座標指定変形および直線の交差判定
上記の式を変形して
$$
(y_2-y_1)x-(x_2-x_1)y=x_1y_2-x_2y_1
$$
右辺は2*2行列$${\begin{bmatrix} x_1 & y_1 \\ x_2 & y_2 \end{bmatrix}}$$の行列式。
この式を2つの直線、あるいは線分に対して立て、
その連立方程式を解くと2つの直線、あるいは線分の交点が求まる。
2*2の連立方程式は
$$
ax+by=p\\
cx+dy=q
$$
なら
$$
\begin{bmatrix}
a & b\\
c & d
\end{bmatrix}
\begin{bmatrix}
x\\
y
\end{bmatrix}
=
\begin{bmatrix}
p\\
q
\end{bmatrix}
$$
$$
\begin{bmatrix}
x\\
y
\end{bmatrix}
=
\frac{1}{ad-bc}
\begin{bmatrix}
d & -b\\
-c & a
\end{bmatrix}
\begin{bmatrix}
p\\
q
\end{bmatrix}
$$
同じことだがクラメルの公式からなら
$$
(y_2-y_1)x-(x_2-x_1)y=x_1y_2-x_2y_1\\
(y_4-y_3)x-(x_4-x_3)y=x_3y_4-x_4y_3
$$
素直に考えると
$$
A=\begin{bmatrix}
(y_2-y_1) & -(x_2-x_1) \\
(y_4-y_3) & -(x_4-x_3)\\
\end{bmatrix},
\quad
\bf{x}=\begin{bmatrix}
x \\
y
\end{bmatrix},
\quad
\bf{b}=\begin{bmatrix}
x_1y_2-x_2y_1 \\
x_3y_4-x_4y_3
\end{bmatrix}
=
\begin{bmatrix}
det\begin{bmatrix} x_1 & y_1 \\ x_2 & y_2 \end{bmatrix} \\
det\begin{bmatrix} x_3 & y_3 \\ x_4 & y_4 \end{bmatrix}
\end{bmatrix}
=
\begin{bmatrix}
b_1\\
b_2
\end{bmatrix}
$$
であるが、教科書では
$$
A=\begin{bmatrix}
(y_2-y_1) & (x_2-x_1) \\
(y_4-y_3) & (x_4-x_3)\\
\end{bmatrix}
$$
であった。
$$
A_1=
\begin{bmatrix}
b_1 & (x_2-x_1) \\
b_2 & (x_4-x_3)\\
\end{bmatrix}, \quad
A_2=
\begin{bmatrix}
(y_2-y_1) & b_1 \\
(y_4-y_3) & b_2\\
\end{bmatrix}
$$
$$
x=\frac{det(A_1)}{det(A)}, \quad y=\frac{det(A_2)}{det(A)}
$$
教科書の方の式をそのまま記述すると
$$
x=\frac{b_1(x_4-x_3)-b_2(x_2-x_1)}{(y_2-y_1)(x_4-x_3)-(y_4-y_3)(x_2-x_1)}\\
y=\frac{b_1(y_4-y_3)-b_2(y_2-y_1)}{(y_2-y_1)(x_4-x_3)-(y_4-y_3)(x_2-x_1)}\\
$$
素直な$${A=\begin{bmatrix}(y_2-y_1) & -(x_2-x_1) \\(y_4-y_3) & -(x_4-x_3)\\\end{bmatrix}}$$の場合。
$$
A_1=
\begin{bmatrix}
b_1 & -(x_2-x_1) \\
b_2 & -(x_4-x_3)\\
\end{bmatrix}, \quad
A_2=
\begin{bmatrix}
(y_2-y_1) & b_1 \\
(y_4-y_3) & b_2\\
\end{bmatrix}
$$
$$
x=\frac{b_2(x_2-x_1)-b_1(x_4-x_3)}{(y_4-y_3)(x_2-x_1)-(y_2-y1)(x_4-x_3)}\\
y=\frac{b_2(y_2-y_1)-b_1(y_4-y_3)}{(y_4-y_3)(x_2-x_1)-(y_2-y_1)(x_4-x_3)}\\
$$
分子分母にマイナス１を掛ければ結果は同じ式である。
直線の交差判定を実装する場合
import java.util.List;
PVector prev;
PVector current;
PVector dv = new PVector(0,0);
List<PVector> vertices = new ArrayList<PVector>();
int current_vertex_index = -1;
float r = 10;
PVector v1;
PVector v2;
PVector v3;
PVector v4;
void mousePressed()
{
prev = new PVector(mouseX,mouseY);
current = new PVector(mouseX,mouseY);
for(int i = 0; i<this.vertices.size(); i++)
{
var v = vertices.get(i);
if((mouseX-v.x)*(mouseX-v.x)+(mouseY-v.y)*(mouseY-v.y)<r*r)
{
current_vertex_index = i;
return;
}
}
}
void mouseDragged()
{
prev = current.copy();
current.x = mouseX;
current.y = mouseY;
dv = PVector.sub(current,prev);
if(0<=current_vertex_index&¤t_vertex_index<this.vertices.size())
{
PVector v = this.vertices.get(current_vertex_index);
v.add(dv);
}
}
void mouseReleased()
{
prev = null;
current = null;
current_vertex_index=-1;
}
void setup()
{
size(500,500);
this.v1 = new PVector(100,100);
this.v2 = new PVector(200,200);
this.v3 = new PVector(100,200);
this.v4 = new PVector(100,300);
this.vertices.add(v1);
this.vertices.add(v2);
this.vertices.add(v3);
this.vertices.add(v4);
}
void draw()
{
background(255);
fill(255);
line(vertices.get(0).x,vertices.get(0).y,vertices.get(1).x, vertices.get(1).y);
line(vertices.get(2).x,vertices.get(2).y,vertices.get(3).x, vertices.get(3).y);
for(var v : vertices)
{
circle(v.x,v.y,10);
}
PVector intersection = GetIntersection2(
vertices.get(0),vertices.get(1),
vertices.get(2),vertices.get(3));
if(intersection!=null)
{
fill(255,0,0);
circle(intersection.x,intersection.y,10);
fill(0);
}
}
//教科書の方,浅野p26
PVector GetIntersection1(PVector v1, PVector v2, PVector v3, PVector v4)
{
float detA = (v2.y-v1.y)*(v4.x-v3.x)-(v4.y-v3.y)*(v2.x-v1.x);
float b1 = v1.x*v2.y-v2.x*v1.y;
float b2 = v3.x*v4.y-v4.x*v3.y;
float x = (b1*(v4.x-v3.x)-b2*(v2.x-v1.x))/detA;
float y = (b1*(v4.y-v3.y)-b2*(v2.y-v1.y))/detA;
return new PVector(x,y);
}
//素直に計算した方
PVector GetIntersection2(PVector v1, PVector v2, PVector v3, PVector v4)
{
float detA = (v4.y-v3.y)*(v2.x-v1.x)-(v2.y-v1.y)*(v4.x-v3.x);
float b1 = v1.x*v2.y-v2.x*v1.y;
float b2 = v3.x*v4.y-v4.x*v3.y;
float x = (b2*(v2.x-v1.x)-b1*(v4.x-v3.x))/detA;
float y = (b2*(v2.y-v1.y)-b1*(v4.y-v3.y))/detA;
return new PVector(x,y);
}
線分交差判定および交点座標取得
: ChatGPT君の答えの場合
PVector GetIntersectionGPT(PVector v1, PVector v2, PVector v3, PVector v4)
{
var l1 = new Line(v1,v2);
var l2 = new Line(v3,v4);
return l1.GetIntersection(l2);
}
//chatGPT
public class Line {
// 直線を表す2つの座標
private PVector p1;
private PVector p2;
// コンストラクタ
public Line(PVector p1, PVector p2) {
this.p1 = p1;
this.p2 = p2;
}
// 2つの直線が交わっているかどうかを判定する関数
public boolean isIntersect(Line line) {
// 2つの直線を表す2つの座標を取得する
PVector a1 = p1;
PVector a2 = p2;
PVector b1 = line.p1;
PVector b2 = line.p2;
// 直線の方程式を求める
double a = a2.y - a1.y;
double b = a1.x - a2.x;
double c = a * a1.x + b * a1.y;
double d = b2.y - b1.y;
double e = b1.x - b2.x;
double f = d * b1.x + e * b1.y;
// 直線が平行かどうかを判定する
if (a * e == b * d) {
return false;
}
// 交点の座標を求める
double x = (e * c - b * f) / (a * e - b * d);
double y = (a * f - d * c) / (a * e - b * d);
// 交点が2つの線分上に存在するかどうかを判定する
if (Math.min(a1.x, a2.x) <= x && x <= Math.max(a1.x, a2.x) &&
Math.min(a1.y, a2.y) <= y && y <= Math.max(a1.y, a2.y) &&
Math.min(b1.x, b2.x) <= x && x <= Math.max(b1.x, b2.x) &&
Math.min(b1.y, b2.y) <= y && y <= Math.max(b1.y, b2.y)) {
return true;
}
return false;
}
PVector GetIntersection(Line line) {
// 2つの直線を表す2つの座標を取得する
PVector a1 = p1;
PVector a2 = p2;
PVector b1 = line.p1;
PVector b2 = line.p2;
// 直線の方程式を求める
double a = a2.y - a1.y;
double b = a1.x - a2.x;
double c = a * a1.x + b * a1.y;
double d = b2.y - b1.y;
double e = b1.x - b2.x;
double f = d * b1.x + e * b1.y;
// 直線が平行かどうかを判定する
if (a * e == b * d) {
return null;
}
// 交点の座標を求める
double x = (e * c - b * f) / (a * e - b * d);
double y = (a * f - d * c) / (a * e - b * d);
// 交点が2つの線分上に存在するかどうかを判定する
if (Math.min(a1.x, a2.x) <= x && x <= Math.max(a1.x, a2.x) &&
Math.min(a1.y, a2.y) <= y && y <= Math.max(a1.y, a2.y) &&
Math.min(b1.x, b2.x) <= x && x <= Math.max(b1.x, b2.x) &&
Math.min(b1.y, b2.y) <= y && y <= Math.max(b1.y, b2.y)) {
return new PVector((float)x,(float)y);
}
return null;
}
}ベクトル使う場合
２点$${\bm r_1(x_1,y_1,z_1)}$$と$${\bm r_2(x_2,y_2,z_2)}$$を通る直線を考える時、その直線上の任意の点を$${\bm r(x,y,z)}$$とすると、パラメータ$${t}$$を用いて
$$
\bm r-\bm r_1=t(\bm r_2-\bm r_1)\\
\bm r=\bm r_1+t(\bm r_2-\bm r_1)
$$
線分として見るなら$${\bm r_1}$$は始点で$${\bm r_2}$$は終点である。
線分感をだしたいならインデックスを$${\bm r_0}$$, $${\bm r_1}$$などとして良い。
成分で書くと
$$
x=x_1+t(x_2-x_1)\\
y=y_1+t(y_2-y_1)\\
z=z_1+t(z_2-z_1)\\
$$
$${t}$$は
$$
t=(x-x_1)/(x_2-x_1)\\
t=(y-y_1)/(y_2-y_1)\\
t=(y-y_1)/(y_2-y_1)\\
$$
全部$${t}$$で繋がるから
$$
\frac{(x-x_1)}{(x_2-x_1)}=\frac{(y-y_1)}{(y_2-y_1)}=\frac{(z-z_1)}{(z_2-z_1)}
$$
これは直線の方程式である。
法線定義（ヘッセ標準形）
あるベクトル$${\bm r_1(x_1,y_1)}$$に対して、これと直交する（内積=0）ベクトルないしそれによって得られる点全部集めたものとして直線を定義する。
$$
\bm r_1\cdot (\bm r-\bm r_1)=0
$$
ここで$${\bm r_1(x_1,y_1)}$$は原点から直線に引いた垂線と見ることもでき、$${\bm r}$$は直線上の任意の点である。
内積を成分で書くと
$$
x_1(x-x_1)+y_1(y-y_1)=0\\
x_1x-x_1^2+y_1y-y_1^2=0\\
x_1x+y_1y-(x_1^2+y_2^2)=0
$$
ここで$${|\bm r_1|=\sqrt{x_1^2+y_1^2}}$$であるから
$${|\bm r_1|^2=x_1^2+y_1^2}$$であって
$${x_1x+y_1y-|\bm r_1|^2=0}$$
一方、方向余弦（あるベクトルが座標系の各軸に対して成す$${\cos}$$。成す角でなく、角によって得られる斜辺（あるベクトルの長さ$${|\mathbf v|}$$）と、あるベクトルが各座標軸に落とす影の大きさ（例えばx軸なら$${x}$$）の比、つまり成す$${\cos}$$）の定義により
$$
l=\frac{x_1}{|\bm r_1|}\\
m=\frac{y_1}{|\bm r_1|}\\
$$
であるから
$$
l|\bm r_1|x+m|\bm r_1|y-|\bm r_1|^2=0\\
lx+my-|\bm r_1|=0\\
$$
同様に法線によって平面を定義すると
$$
\bm r_1\cdot(\bm r-\bm r_1)=0
$$
$$
l=\frac{x_1}{|\bm r_1|}\\
m=\frac{y_1}{|\bm r_1|}\\
n=\frac{z_1}{|\bm r_1|}
$$
$$
lx+my+nz-|\bm r_1|=0
$$
この記事が気に入ったらサポートをしてみませんか？