判断点d在过点a,b,c的圆内

hbghlyj

asymptote的文档中

1. real incircle(pair a, pair b, pair c, pair d);
2. returns a positive (negative) value if d lies inside (outside) the circle passing through the counterclockwise-oriented points a,b,c or zero if d lies on the this circle. The value returned is the determinant
4. |a.x a.y a.x^2+a.y^2 1|
5. |b.x b.y b.x^2+b.y^2 1|
6. |c.x c.y c.x^2+c.y^2 1|
7. |d.x d.y d.x^2+d.y^2 1|

Copy the Code

确定点 \(d\) 是否位于由平面上三点 \(a\)、\(b\) 和 \(c\) 定义的圆的内部或外部。

假设 \(a\)、\(b\)、\(c\) 按逆时针顺序标记在圆周上，计算行列式：
\begin{vmatrix}
a_x & a_y & a_x^2 + a_y^2 & 1 \\
b_x & b_y & b_x^2 + b_y^2 & 1 \\
c_x & c_y & c_x^2 + c_y^2 & 1 \\
d_x & d_y & d_x^2 + d_y^2 & 1 \\
\end{vmatrix}如果行列式为正，则 \(d\) 在圆内；如果为负，则 \(d\) 在圆外；如果为零，则四点共圆。如果行列式为正，则 \(d\) 在圆内；如果为负，则 \(d\) 在圆外；如果为零，则四点共圆。

推广到 3 维：判断点在由 4 个点定的球内：
\begin{vmatrix}
a_x & a_y & a_z & a_x^2 + a_y^2 + a_z^2 & 1 \\
b_x & b_y & b_z & b_x^2 + b_y^2 + b_z^2 & 1 \\
c_x & c_y & c_z & c_x^2 + c_y^2 + c_z^2 & 1 \\
d_x & d_y & d_z & d_x^2 + d_y^2 + d_z^2 & 1 \\
e_x & e_y & e_z & e_x^2 + e_y^2 + e_z^2 & 1 \\
\end{vmatrix}如果行列式为正，则 \(e\) 在球内；如果为负，则 \(e\) 在球外；如果为零，则五点共球。

isee

回复 1# hbghlyj


如果你只是想问这个行列式是什么的话，我就说：这个行列式是过三点圆的方程

你多半是知道的，所以，应该是答非所问

hbghlyj

应用：Delaunay 三角剖分算法中

当左右点集均存在可能点时，判断左边点所对应圆是否包含右边点，若包含则不符合；对于右边点也是同样的判断。一般只有一个可能点符合标准（除非四点共圆）。