gpt4 book ai didi

algorithm - 判断 4 个点是否构成四边形

转载 作者:塔克拉玛干 更新时间:2023-11-03 02:58:48 29 4
gpt4 key购买 nike

谁能告诉我一个算法来编写一个函数,如果 4 个点形成四边形则返回 true,否则返回 false?积分不附带任何订单。

我尝试检查 4 个点的所有排列,看看是否有 3 个点形成一条直线。如果有 3 个点形成一条直线,那么它就不是四边形。但后来我意识到没有办法告诉订单。然后我挣扎了几个小时的思考和谷歌搜索没有结果:(

我读过这些问题:

  1. find if 4 points on a plane form a rectangle?
  2. Determining ordering of vertices to form a quadrilateral

但是还是没有找到解决办法。在 1 的情况下,它无法检测到另一种四边形,而在 2 的情况下,它假设这些点已经是四边形了。有没有其他方法可以判断4个点是否构成四边形?

先谢谢了。

编辑澄清:

我把四边形定义为简单的四边形,基本上就是这张图所示的所有形状: Quadirateral

带有“四边形”和“复杂”标题的形状除外。

至于“检查共线三元组”方法的问题,我尝试使用如下方法检查垂直线、水平线和对角线:

def is_linear_line(pt1, pt2, pt3):
return (pt1[x] == pt2[x] == pt3[x] ||
pt1[y] == pt2[y] == pt3[y] ||
slope(pt1, pt2) == slope(pt2, pt3))

并意识到矩形和正方形将算作直线,因为点的斜率都相同。希望这能解决问题。

最佳答案

这是为了检查四边形是否是凸的。如果它是一个简单的四边形,则不会。

我在 objective-c 中确实喜欢这个 https://github.com/hfossli/AGGeometryKit/

extern BOOL AGQuadIsConvex(AGQuad q)
{
BOOL isConvex = AGLineIntersection(AGLineMake(q.bl, q.tr), AGLineMake(q.br, q.tl), NULL);
return isConvex;
}

BOOL AGLineIntersection(AGLine l1, AGLine l2, AGPoint *out_pointOfIntersection)
{
// http://stackoverflow.com/a/565282/202451

AGPoint p = l1.start;
AGPoint q = l2.start;
AGPoint r = AGPointSubtract(l1.end, l1.start);
AGPoint s = AGPointSubtract(l2.end, l2.start);

double s_r_crossProduct = AGPointCrossProduct(r, s);
double t = AGPointCrossProduct(AGPointSubtract(q, p), s) / s_r_crossProduct;
double u = AGPointCrossProduct(AGPointSubtract(q, p), r) / s_r_crossProduct;

if(t < 0 || t > 1.0 || u < 0 || u > 1.0)
{
if(out_pointOfIntersection != NULL)
{
*out_pointOfIntersection = AGPointZero;
}
return NO;
}
else
{
if(out_pointOfIntersection != NULL)
{
AGPoint i = AGPointAdd(p, AGPointMultiply(r, t));
*out_pointOfIntersection = i;
}
return YES;
}
}

关于algorithm - 判断 4 个点是否构成四边形,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/9513107/

29 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com