什么是最简单的算法来确定一个点是否在一个二维三角形内部？
如何确定一个点是否在一个二维三角形内？
338
- ET 0.618
7
30我写了一篇完整的文章介绍三角形中点的测试方法，包括重心法、参数法和点积法。然后讨论了当点恰好在一个边上时出现的准确性问题（并给出了示例）。最后，提出了一种基于点到边距离的全新方法。请享受链接中的阅读内容！ - Logic
4类似的3D问题是关于BSP生成的，如何将一个由平面定义的三角形与平面相交或定位。 - luser droog
2我投票关闭此问题，因为它涉及数学而非编程，并且是基于个人观点的（对你来说什么是“容易”的？）。 - TylerH
16这个问题被关闭的事实表明 SO 存在缺陷。在多边形（三角形）中测试点是否存在是一个常见的编程问题。 - Mitch Wheat
5虽然这个问题涉及数学，但在math-stackexchange网站上提问通常会得到晦涩难懂的数学符号式回答，这对于没有数学背景的人来说可能很难理解。只懂编程的人更愿意在SO网站上提问这个问题。 - Thariq Nugrohotomo
显示剩余2条评论
25个回答
350
通常情况下，最简单（且相当优化）的算法是检查点在由边创建的半平面的哪一侧。
这里有一个关于GameDev主题的高质量信息，包括性能问题：链接。
以下是一些代码，可供参考：
float sign (fPoint p1, fPoint p2, fPoint p3)
{
return (p1.x - p3.x) * (p2.y - p3.y) - (p2.x - p3.x) * (p1.y - p3.y);
}
bool PointInTriangle (fPoint pt, fPoint v1, fPoint v2, fPoint v3)
{
float d1, d2, d3;
bool has_neg, has_pos;
d1 = sign(pt, v1, v2);
d2 = sign(pt, v2, v3);
d3 = sign(pt, v3, v1);
has_neg = (d1 < 0) || (d2 < 0) || (d3 < 0);
has_pos = (d1 > 0) || (d2 > 0) || (d3 > 0);
return !(has_neg && has_pos);
}
- Kornel Kisielewicz
13
14它通常在2D中使用。重心坐标往往会使人困惑。而且，鉴于三角形的坐标和点的坐标已知，我不确定使用重心坐标的效率如何。 - Kornel Kisielewicz
10@Kornel，重心坐标版本在二维中更有效。您的解决方案也存在问题，即对于恰好位于三角形边缘上的点，将根据三角形是顺时针还是逆时针指定而报告不同的结果。 - Andreas Brinck
10对于我的目的（我发现这个网站的原因），Kornel Kisielewicz提供的原始答案更加高效。我正在使用一个带有BYTE大小坐标和非常典型的微处理器的LCD显示屏，其中整数乘法是一条非常快速的指令，而除法则慢得多得多。由于没有除法，数字问题也要小得多！所有计算都是精确的。谢谢，Rick。 - user252020
4sign()函数告诉你p1位于由p2和p3形成的半平面的哪一侧。 - David Doria
1请注意，如果
v1、v2和v3相等，此函数将始终返回true。 - Morris Franken显示剩余8条评论
201
解决以下方程组：
p = p0 + (p1 - p0) * s + (p2 - p0) * t
如果0 <= s <= 1且0 <= t <= 1且s + t <= 1，则点p在三角形内。
s、t和1 - s - t被称为点p的重心坐标。
- Andreas Brinck
14
2这比半平面检查更快，但如果您对重心坐标系不熟悉，可能会有点难以理解。 - Daniel Rikowski
10使用Kornel方法中的微不足道的退出（未实现），他的方法实际上比你的更有效率。如果你真正尝试计算s和t，你就会知道我在说什么。 - Matthieu N.
100我想测试一下，所以我做了一个 jsfiddle，依赖于 @andreasdr 的解决方案和 coproc 的评论：http://jsfiddle.net/PerroAZUL/zdaY8/1/ - urraka
7优化：如果
s + t <= 1，那么当 s >= 0 和 t >= 0 时，就意味着 s <= 1 和 t <= 1。 - Thomas Eding9这篇文章http://totologic.blogspot.fr/2014/01/accurate-point-in-triangle-test.html，由@Logic发布，帮助我更好地理解了这个解决方案。 - flaviussn
显示剩余9条评论
127
我同意Andreas Brinck的看法，重心坐标对于这个任务非常方便。需要注意的是，每次并不需要解决一个方程组：只需评估分析解即可。使用Andreas的符号表示，解决方案如下：
s = 1/(2*Area)*(p0y*p2x - p0x*p2y + (p2y - p0y)*px + (p0x - p2x)*py);
t = 1/(2*Area)*(p0x*p1y - p0y*p1x + (p0y - p1y)*px + (p1x - p0x)*py);
其中Area是三角形的（有符号）面积：
Area = 0.5 *(-p1y*p2x + p0y*(-p1x + p2x) + p0x*(p1y - p2y) + p1x*p2y);
只需评估
s、t 和 1-s-t。当且仅当它们都为正数时，点 p 在三角形内部。编辑：注意，上述面积表达式假定三角形节点编号逆时针。如果编号顺时针，则此表达式将返回负面积（但具有正确的大小）。然而，测试本身（
s>0 && t>0 && 1-s-t>0）不依赖于编号方向，因为上面乘以 1/(2*Area) 的表达式也会随着三角形节点方向的变化而改变符号。编辑2：为了获得更好的计算效率，请参见下面 coproc 的评论（提到如果事先知道三角形节点的方向（顺时针或逆时针），则可以避免在
s 和 t 的表达式中除以 2*Area）。还请查看 Perro Azul 在 Andreas Brinck 的答案下的评论中的 jsfiddle 代码。- andreasdr
12
9那就是解决方程组的意思 :) - Andreas Brinck
2是的，我的观点是，基于解决方程组的计算成本对您的方法进行任何批评都是没有根据的，因为这不必作为算法的一部分来完成。 - andreasdr
16不需要通过“2*面积”进行除法运算，可以提高效率，即通过计算
s´=2*|面积|*s和t´=2*|面积|*t来实现（如果点的方向-顺时针或逆时针-未知，则必须检查“面积”的符号，但通常情况下可能不需要进行计算），因为对于检查“s> 0”，只需要检查“s´> 0”。而且，不需要检查“1-s-t>0”，只需要检查s´+t´<2*|面积|。 - coproc2我可以补充一下，如果在笛卡尔坐标系中
p0->p1->p2是逆时针（通常在屏幕坐标系中为顺时针），那么使用这种方法计算的面积将为正。 - rhgb1当您沿着三角形的边界以p0 -> p1 -> p2 -> p0的方向旅行时，您将始终将三角形的内部保持在您的右侧或左侧。在前一种情况下，编号是顺时针的，在后一种情况下，它是逆时针的。 - andreasdr
显示剩余7条评论
60
在尝试使用Google之前，我写了这段代码并找到了这个页面，所以我想分享一下。它基本上是Kisielewicz答案的优化版本。我也研究了重心法，但根据维基百科文章，我很难看出它为什么更有效（我猜测存在某种更深层次的等价性）。无论如何，这个算法的优点是不使用除法；一个潜在问题是边缘检测的行为取决于方向。
bool intpoint_inside_trigon(intPoint s, intPoint a, intPoint b, intPoint c)
{
int as_x = s.x - a.x;
int as_y = s.y - a.y;
bool s_ab = (b.x - a.x) * as_y - (b.y - a.y) * as_x > 0;
if ((c.x - a.x) * as_y - (c.y - a.y) * as_x > 0 == s_ab)
return false;
if ((c.x - b.x) * (s.y - b.y) - (c.y - b.y)*(s.x - b.x) > 0 != s_ab)
return false;
return true;
}
简而言之，想法是这样的：点s在AB和AC两条线的左侧还是右侧？如果是真的，则不能在内部。如果是假的，则至少在满足条件的“锥体”内部。由于我们知道三角形内部的点必须在AB与BC（以及CA）的同一侧，因此我们检查它们是否不同。如果它们不同，则s显然不能在内部，否则s必须在内部。
计算中的一些关键词是半平面和行列式（2x2叉积）。也许更易理解的方法可能是认为，当点到AB、BC和CA的每条线的同一侧时，该点在内部。但以上方法对于某些优化似乎更合适。
- John Bananas
4
2这个测试比提供的第一个测试快了大约140-180%（顺便感谢你们两位：）。我在这里运行了代码：https://paste.ubuntu.com/p/k5w7ywH4p8，使用禁用优化的nodejs v8引擎，并得到以下结果：:w！node -p --minimal
test1: 114.852毫秒
test2: 64.330毫秒
test1: 115.650毫秒
test2: 63.491毫秒
test1: 117.671毫秒
test2: 65.353毫秒
test1: 119.146毫秒
test2: 63.871毫秒
test1: 118.271毫秒
test1: 118.670毫秒
test2: 63.352毫秒 - surgemcgee
@surgemcgee 你为什么不开启优化就运行它？难道这样不是更偏离现实吗？ - xuiqzy
@xuiqzy 嗯，我的程序包含了两种不同的解决方案。我还没有实施最快的方法。也许应该删除那个评论，并用我完成的作品来代替它。 - surgemcgee
2谢谢。我写了一个非常详细注释的版本，以便更好地理解它：https://math.stackexchange.com/a/4624564/1142693 - carlynorama
45
这是由andreasdr和Perro Azul发布的重心法的C#版本。我添加了一个检查来放弃计算面积，当s和t有相反的符号（并且都不为零）时，因为可能避免三分之一的乘法成本是合理的。
public static bool PointInTriangle(Point p, Point p0, Point p1, Point p2)
{
var s = (p0.X - p2.X) * (p.Y - p2.Y) - (p0.Y - p2.Y) * (p.X - p2.X);
var t = (p1.X - p0.X) * (p.Y - p0.Y) - (p1.Y - p0.Y) * (p.X - p0.X);
if ((s < 0) != (t < 0) && s != 0 && t != 0)
return false;
var d = (p2.X - p1.X) * (p.Y - p1.Y) - (p2.Y - p1.Y) * (p.X - p1.X);
return d == 0 || (d < 0) == (s + t <= 0);
}
更新2021：
此版本正确处理以任何顺序指定的三角形（顺时针或逆时针）。请注意，对于位于三角形边缘上的点，本页中的其他答案根据列出三角形的三个点的顺序给出了不一致的结果。这些点被认为是“在”三角形中，并且此代码无论旋转方向如何都会正确返回true。
- Glenn Slayden
8
@GlennSlayden 哪些点是构成三角形的，我们需要寻找哪个点？ - USer22999299
@用户22999299 第一个参数
p 是你要查找的点。剩下的三个 Point 参数 p0、p1 和 p2 建立了一个三角形，你希望在其中进行搜索。 - Glenn Slayden1感谢您在这里发布。只有一件事。您的额外检查破坏了此算法对于绕序的冷漠性。一个三角形（1,1;1,2;2,2）和一个点（1,1.5）被认为不匹配，尽管它正好在边缘上。删除您的两行代码可以解决此问题。但再次感谢您的发布，它帮了大忙。 - Robert K.
@RobertK. 感谢您的有益评论。我已经更新了答案。 - Glenn Slayden
我很困惑。这不是重心法，而是同侧法，对吗？ - dialer
显示剩余3条评论
17
重心法的Java版本：
class Triangle {
Triangle(double x1, double y1, double x2, double y2, double x3,
double y3) {
this.x3 = x3;
this.y3 = y3;
y23 = y2 - y3;
x32 = x3 - x2;
y31 = y3 - y1;
x13 = x1 - x3;
det = y23 * x13 - x32 * y31;
minD = Math.min(det, 0);
maxD = Math.max(det, 0);
}
boolean contains(double x, double y) {
double dx = x - x3;
double dy = y - y3;
double a = y23 * dx + x32 * dy;
if (a < minD || a > maxD)
return false;
double b = y31 * dx + x13 * dy;
if (b < minD || b > maxD)
return false;
double c = det - a - b;
if (c < minD || c > maxD)
return false;
return true;
}
private final double x3, y3;
private final double y23, x32, y31, x13;
private final double det, minD, maxD;
}
假设没有溢出，以上代码适用于整数，并且适用于顺时针和逆时针三角形。它不能用于共线的三角形（但您可以通过测试det == 0来检查）。
如果您要测试与同一三角形的不同点，则重心版本最快。
由于浮点舍入误差，重心版本在3个三角形点中不对称，因此可能比Kornel Kisielewicz的边半平面版本不一致。
来源：我从Wikipedia的重心坐标文章制作了上述代码。
- Adam Gawne-Cain
2
不错！甚至可以改进为使用javax.vecmath的Point3f / Point2f元组，以更好地处理数据输入。 - Alex Byrth
只是好奇：为什么这个包缺少Point2i类？ - djangofan
16
通过使用重心坐标的解析解（由Andreas Brinck指出），并且：
- 不要在括号项上分配乘法
- 通过存储它们来避免多次计算相同的术语
- 减少比较（如coproc和Thomas Eding所指出的那样）
可以最小化“昂贵”的操作次数：
function ptInTriangle(p, p0, p1, p2) {
var dX = p.x-p2.x;
var dY = p.y-p2.y;
var dX21 = p2.x-p1.x;
var dY12 = p1.y-p2.y;
var D = dY12*(p0.x-p2.x) + dX21*(p0.y-p2.y);
var s = dY12*dX + dX21*dY;
var t = (p2.y-p0.y)*dX + (p0.x-p2.x)*dY;
if (D<0) return s<=0 && t<=0 && s+t>=D;
return s>=0 && t>=0 && s+t<=D;
}
代码可以粘贴到Perro Azul jsfiddle 中，或者点击下面的“运行代码片段”进行尝试。
var ctx = $("canvas")[0].getContext("2d");
var W = 500;
var H = 500;
var point = { x: W / 2, y: H / 2 };
var triangle = randomTriangle();
$("canvas").click(function(evt) {
point.x = evt.pageX - $(this).offset().left;
point.y = evt.pageY - $(this).offset().top;
test();
});
$("canvas").dblclick(function(evt) {
triangle = randomTriangle();
test();
});
test();
function test() {
var result = ptInTriangle(point, triangle.a, triangle.b, triangle.c);
var info = "point = (" + point.x + "," + point.y + ")\n";
info += "triangle.a = (" + triangle.a.x + "," + triangle.a.y + ")\n";
info += "triangle.b = (" + triangle.b.x + "," + triangle.b.y + ")\n";
info += "triangle.c = (" + triangle.c.x + "," + triangle.c.y + ")\n";
info += "result = " + (result ? "true" : "false");
$("#result").text(info);
render();
}
function ptInTriangle(p, p0, p1, p2) {
var A = 1/2 * (-p1.y * p2.x + p0.y * (-p1.x + p2.x) + p0.x * (p1.y - p2.y) + p1.x * p2.y);
var sign = A < 0 ? -1 : 1;
var s = (p0.y * p2.x - p0.x * p2.y + (p2.y - p0.y) * p.x + (p0.x - p2.x) * p.y) * sign;
var t = (p0.x * p1.y - p0.y * p1.x + (p0.y - p1.y) * p.x + (p1.x - p0.x) * p.y) * sign;
return s > 0 && t > 0 && (s + t) < 2 * A * sign;
}
function render() {
ctx.fillStyle = "#CCC";
ctx.fillRect(0, 0, 500, 500);
drawTriangle(triangle.a, triangle.b, triangle.c);
drawPoint(point);
}
function drawTriangle(p0, p1, p2) {
ctx.fillStyle = "#999";
ctx.beginPath();
ctx.moveTo(p0.x, p0.y);
ctx.lineTo(p1.x, p1.y);
ctx.lineTo(p2.x, p2.y);
ctx.closePath();
ctx.fill();
ctx.fillStyle = "#000";
ctx.font = "12px monospace";
ctx.fillText("1", p0.x, p0.y);
ctx.fillText("2", p1.x, p1.y);
ctx.fillText("3", p2.x, p2.y);
}
function drawPoint(p) {
ctx.fillStyle = "#F00";
ctx.beginPath();
ctx.arc(p.x, p.y, 5, 0, 2 * Math.PI);
ctx.fill();
}
function rand(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
function randomTriangle() {
return {
a: { x: rand(0, W), y: rand(0, H) },
b: { x: rand(0, W), y: rand(0, H) },
c: { x: rand(0, W), y: rand(0, H) }
};
}<script src="https://cdnjs.cloudflare.com/ajax/libs/jquery/1.9.1/jquery.min.js"></script>
<pre>Click: place the point.
Double click: random triangle.</pre>
<pre id="result"></pre>
<canvas width="500" height="500"></canvas>引导至：
- 变量“recalls”：30
- 变量存储：7
- 加法：4
- 减法：8
- 乘法：6
- 除法：无
- 比较：4
这与Kornel Kisielewicz的解决方案相当，后者为（25次回调，1个存储，15次减法，6次乘法，5次比较），如果需要顺时针/逆时针检测，则可能更好（它本身需要6次回调，1次加法，2次减法，2次乘法和1次比较，使用分析解行列式，如rhgb所指出的）。
- Cédric Dufour
6
不错的解决方案。我认为这与我在MSE上的上一个方法相当等价：http://math.stackexchange.com/questions/51326/determining-if-an-arbitrary-point-lies-inside-a-triangle-defined-by-three-points/1884485#1884485 - Jack D'Aurizio
我刚刚按原样测试了代码，但对我来说不起作用（例如p-4.69317198，-6.99191951 p0-7.05846786 0.596718192 p1-6.8703599 -2.36565161 p2-4.69317198，-6.99191951）。 - Giovanni Funchal
@GiovanniFunchal 奇怪，你的例子在我的本地 Python 实现和 jsfiddle（替换初始“point”和“triangle”定义）中都可以工作。数值精度问题（尝试去掉一些小数）？ - Cédric Dufour
1你的方法在我的测试中似乎是最快的：https://jsfiddle.net/eyal/gxw3632c/27/。然而，所有方法之间的差异都非常小。 - Eyal
尝试三角形(-1，-1)，(1，-1)，(0，1)和点(0，-1)。当s（2）+ t（2）> d（2）时返回false，但应该返回true。似乎三角形边缘的数学有问题，因为点p恰好在p0和p1之间的边界上，这不是将<转换为<=之类的简单问题。 - devnullicus
1实际上，在进一步研究后，似乎可以很容易地修复它。将ptInTriangle的最后一行更改为“return s >= 0.0 && t >= 0.0 && (s + t) <= 2.0 * A * sgn”似乎可以解决问题。 - devnullicus
15
- Simon P Stevens
4
3嗯，那种方法并不十分高效，而且容易出现数值误差... - Kornel Kisielewicz
这恰恰相反，非常低效 :-) 不过这只是一种简单的方法，易于实现。你能举一个可能导致数值误差的例子吗？ - Simon P Stevens
虽然在我看来，这似乎是该主题下所有答案中最好的一个，但我猜三角形边缘上的点被计算为包含在三角形内，而你对此没有完全控制。 - Redu
检查是否恰好为2π在数值上是不可能的，因为π是无理数。然而，您只需要检查角度是否相加大于π即可。 - lonewarrior556
11
这里有一个用Python编写的解决方案，高效且文档完备，并包含三个单元测试。它具有专业级质量，可以直接作为模块插入到您的项目中使用。
import unittest
###############################################################################
def point_in_triangle(point, triangle):
"""Returns True if the point is inside the triangle
and returns False if it falls outside.
- The argument *point* is a tuple with two elements
containing the X,Y coordinates respectively.
- The argument *triangle* is a tuple with three elements each
element consisting of a tuple of X,Y coordinates.
It works like this:
Walk clockwise or counterclockwise around the triangle
and project the point onto the segment we are crossing
by using the dot product.
Finally, check that the vector created is on the same side
for each of the triangle's segments.
"""
# Unpack arguments
x, y = point
ax, ay = triangle[0]
bx, by = triangle[1]
cx, cy = triangle[2]
# Segment A to B
side_1 = (x - bx) * (ay - by) - (ax - bx) * (y - by)
# Segment B to C
side_2 = (x - cx) * (by - cy) - (bx - cx) * (y - cy)
# Segment C to A
side_3 = (x - ax) * (cy - ay) - (cx - ax) * (y - ay)
# All the signs must be positive or all negative
return (side_1 < 0.0) == (side_2 < 0.0) == (side_3 < 0.0)
###############################################################################
class TestPointInTriangle(unittest.TestCase):
triangle = ((22 , 8),
(12 , 55),
(7 , 19))
def test_inside(self):
point = (15, 20)
self.assertTrue(point_in_triangle(point, self.triangle))
def test_outside(self):
point = (1, 7)
self.assertFalse(point_in_triangle(point, self.triangle))
def test_border_case(self):
"""If the point is exactly on one of the triangle's edges,
we consider it is inside."""
point = (7, 19)
self.assertTrue(point_in_triangle(point, self.triangle))
###############################################################################
if __name__ == "__main__":
suite = unittest.defaultTestLoader.loadTestsFromTestCase(TestPointInTriangle)
unittest.TextTestRunner().run(suite)
以上算法还有一个可选的图形测试，以确认其有效性：
import random
from matplotlib import pyplot
from triangle_test import point_in_triangle
###############################################################################
# The area #
size_x = 64
size_y = 64
# The triangle #
triangle = ((22 , 8),
(12 , 55),
(7 , 19))
# Number of random points #
count_points = 10000
# Prepare the figure #
figure = pyplot.figure()
axes = figure.add_subplot(111, aspect='equal')
axes.set_title("Test the 'point_in_triangle' function")
axes.set_xlim(0, size_x)
axes.set_ylim(0, size_y)
# Plot the triangle #
from matplotlib.patches import Polygon
axes.add_patch(Polygon(triangle, linewidth=1, edgecolor='k', facecolor='none'))
# Plot the points #
for i in range(count_points):
x = random.uniform(0, size_x)
y = random.uniform(0, size_y)
if point_in_triangle((x,y), triangle): pyplot.plot(x, y, '.g')
else: pyplot.plot(x, y, '.b')
# Save it #
figure.savefig("point_in_triangle.pdf")
生成以下图形：
- xApple
1
point_in_triangle的实现取决于当side_*变量中的任何一个为零时的绕线。当点恰好位于边缘上时，这可能被视为在三角形内部或外部，取决于绕线将导致令人困惑的边缘情况。 - undefined8
由于没有JS答案，
顺时针和逆时针解决方案：
function triangleContains(ax, ay, bx, by, cx, cy, x, y) {
let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
return det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) >= 0 &&
det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) >= 0 &&
det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) >= 0
}
编辑：修正了两个拼写错误（关于符号和比较）。
https://jsfiddle.net/jniac/rctb3gfL/
function triangleContains(ax, ay, bx, by, cx, cy, x, y) {
let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)
return det * ((bx - ax) * (y - ay) - (by - ay) * (x - ax)) > 0 &&
det * ((cx - bx) * (y - by) - (cy - by) * (x - bx)) > 0 &&
det * ((ax - cx) * (y - cy) - (ay - cy) * (x - cx)) > 0
}
let width = 500, height = 500
// clockwise
let triangle1 = {
A : { x: 10, y: -10 },
C : { x: 20, y: 100 },
B : { x: -90, y: 10 },
color: '#f00',
}
// counter clockwise
let triangle2 = {
A : { x: 20, y: -60 },
B : { x: 90, y: 20 },
C : { x: 20, y: 60 },
color: '#00f',
}
let scale = 2
let mouse = { x: 0, y: 0 }
// DRAW >
let wrapper = document.querySelector('div.wrapper')
wrapper.onmousemove = ({ layerX:x, layerY:y }) => {
x -= width / 2
y -= height / 2
x /= scale
y /= scale
mouse.x = x
mouse.y = y
drawInteractive()
}
function drawArrow(ctx, A, B) {
let v = normalize(sub(B, A), 3)
let I = center(A, B)
let p
p = add(I, rotate(v, 90), v)
ctx.moveTo(p.x, p.y)
ctx.lineTo(I.x, I .y)
p = add(I, rotate(v, -90), v)
ctx.lineTo(p.x, p.y)
}
function drawTriangle(ctx, { A, B, C, color }) {
ctx.beginPath()
ctx.moveTo(A.x, A.y)
ctx.lineTo(B.x, B.y)
ctx.lineTo(C.x, C.y)
ctx.closePath()
ctx.fillStyle = color + '6'
ctx.strokeStyle = color
ctx.fill()
drawArrow(ctx, A, B)
drawArrow(ctx, B, C)
drawArrow(ctx, C, A)
ctx.stroke()
}
function contains({ A, B, C }, P) {
return triangleContains(A.x, A.y, B.x, B.y, C.x, C.y, P.x, P.y)
}
function resetCanvas(canvas) {
canvas.width = width
canvas.height = height
let ctx = canvas.getContext('2d')
ctx.resetTransform()
ctx.clearRect(0, 0, width, height)
ctx.setTransform(scale, 0, 0, scale, width/2, height/2)
}
function drawDots() {
let canvas = document.querySelector('canvas#dots')
let ctx = canvas.getContext('2d')
resetCanvas(canvas)
let count = 1000
for (let i = 0; i < count; i++) {
let x = width * (Math.random() - .5)
let y = width * (Math.random() - .5)
ctx.beginPath()
ctx.ellipse(x, y, 1, 1, 0, 0, 2 * Math.PI)
if (contains(triangle1, { x, y })) {
ctx.fillStyle = '#f00'
} else if (contains(triangle2, { x, y })) {
ctx.fillStyle = '#00f'
} else {
ctx.fillStyle = '#0003'
}
ctx.fill()
}
}
function drawInteractive() {
let canvas = document.querySelector('canvas#interactive')
let ctx = canvas.getContext('2d')
resetCanvas(canvas)
ctx.beginPath()
ctx.moveTo(0, -height/2)
ctx.lineTo(0, height/2)
ctx.moveTo(-width/2, 0)
ctx.lineTo(width/2, 0)
ctx.strokeStyle = '#0003'
ctx.stroke()
drawTriangle(ctx, triangle1)
drawTriangle(ctx, triangle2)
ctx.beginPath()
ctx.ellipse(mouse.x, mouse.y, 4, 4, 0, 0, 2 * Math.PI)
if (contains(triangle1, mouse)) {
ctx.fillStyle = triangle1.color + 'a'
ctx.fill()
} else if (contains(triangle2, mouse)) {
ctx.fillStyle = triangle2.color + 'a'
ctx.fill()
} else {
ctx.strokeStyle = 'black'
ctx.stroke()
}
}
drawDots()
drawInteractive()
// trigo
function add(...points) {
let x = 0, y = 0
for (let point of points) {
x += point.x
y += point.y
}
return { x, y }
}
function center(...points) {
let x = 0, y = 0
for (let point of points) {
x += point.x
y += point.y
}
x /= points.length
y /= points.length
return { x, y }
}
function sub(A, B) {
let x = A.x - B.x
let y = A.y - B.y
return { x, y }
}
function normalize({ x, y }, length = 10) {
let r = length / Math.sqrt(x * x + y * y)
x *= r
y *= r
return { x, y }
}
function rotate({ x, y }, angle = 90) {
let length = Math.sqrt(x * x + y * y)
angle *= Math.PI / 180
angle += Math.atan2(y, x)
x = length * Math.cos(angle)
y = length * Math.sin(angle)
return { x, y }
}* {
margin: 0;
}
html {
font-family: monospace;
}
body {
padding: 32px;
}
span.red {
color: #f00;
}
span.blue {
color: #00f;
}
canvas {
position: absolute;
border: solid 1px #ddd;
}<p><span class="red">red triangle</span> is clockwise</p>
<p><span class="blue">blue triangle</span> is couter clockwise</p>
<br>
<div class="wrapper">
<canvas id="dots"></canvas>
<canvas id="interactive"></canvas>
</div>
- Joseph Merdrignac
7
我尝试了这段代码，但它不起作用。它总是返回False。 - xApple
1哎呀，我犯了一个错误，我写成了：
let det = (bx - ax) * (cy - ay) - (by - ay) * (cy - ay)，而不是let det = (bx - ax) * (cy - ay) - (by - ay) * (cx - ax)。现在已经修正了，感谢您的反馈。 - Joseph Merdrignac你的
triangleContains 函数是错误的；对于 (1, 1.5)，它错误地返回了 false —— 对于两个备选绕组 (1, 1) (1, 2) (2, 2) 和 (1, 1) (2, 2) (1, 2) 都是如此——尽管该点明显在三角形的边缘上。我认为你编写的函数中的所有三个不等式都应该是 … >= 0 而不是 … > 0。 - Glenn Slayden@GlennSlayden 你是对的，我编辑了我的答案，现在边缘上的点返回true。谢谢 - Joseph Merdrignac
另外，如果一个点在三角形的角落，则返回false。我在triangleContains函数的开头修复了它，如下所示：如果（ax == x and ay == y）return true; 如果（bx == x and by == y）return true; 如果（cx == x and cy == y）return true; - Digerkam
显示剩余2条评论
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接