如何检查一个点是否在3点外接圆内? [英] How can I check wether a point is inside the circumcircle of 3 points?

问题描述

有什么简单的解决方法吗?还是有人实现的例子?

Is there any easy solution? Or has anybody an example of an implementation?

谢谢乔纳斯

推荐答案

(如果您对非显而易见/疯狂"的解决方案感兴趣).

(In case you are interested in a non-obvious/"crazy" kind of solution.)

Delaunay三角剖分的一个等效属性如下:如果在三角剖分中构建任何三角形的外接圆，则可以保证不包含该三角剖分的任何其他顶点.

One equivalent property of Delaunay triangulation is as follows: if you build a circumcircle of any triangle in the triangulation, it is guaranteed not to contain any other vertices of the triangulation.

Delaunay三角剖分的另一个等效属性是:它使最小三角形角度最大化(即，在同一组点上的所有三角剖分中最大化).

Another equivalent property of Delaunay triangulation is: it maximizes the minimal triangle angle (i.e. maximizes it among all triangulations on the same set of points).

这为您的测试提出了一种算法:

This suggests an algorithm for your test:

1. 考虑在原始3个点上建立的三角形ABC.
2. 如果测试点P位于三角形内，则肯定位于圆内
3. 如果测试点P属于拐角"之一，则"
4. "不成立.区域(请参见下图中的阴影区域)，它肯定在圆圈之外

1. Consider triangle ABC built on the original 3 points.
2. If the test point P lies inside the triangle it is definitely inside the circle
3. If the test point P belongs to one of the "corner" regions (see the shaded regions in the picture below), it is definitely outside the circle

1. 否则(假设P位于区域1)，考虑两个四边形ABCP的三角剖分:原始一个包含原始三角形(红色对角线)，而 alternate 带有翻转"的对角线(蓝色对角线)

1. Otherwise (let's say P lies in region 1) consider two triangulations of quadrilateral ABCP: the original one contains the original triangle (red diagonal), and the alternate one with "flipped" diagonal (blue diagonal)

1. 通过测试翻转"来确定该三角剖分中的哪一个是Delaunay三角剖分.条件，例如通过比较α = min(∠1,∠4,∠5,∠8)与β = min(∠2,∠3,∠6,∠7).
2. 如果原始三角剖分是Delaunay三角剖分(α > β)，则P位于圆之外.如果替代三角剖分是Delaunay三角剖分(α < β)，则P位于圆内.

1. Determine which one if this triangulations is a Delaunay triangulation by testing the "flip" condition, e.g. by comparing α = min(∠1,∠4,∠5,∠8) vs. β = min(∠2,∠3,∠6,∠7).
2. If the original triangulation is a Delaunay triangulation (α > β), P lies outside the circle. If the alternate triangulation is a Delaunay triangulation (α < β), P lies inside the circle.

完成.

(一段时间后重新查看此答案.)

(Revisiting this answer after a while.)

该解决方案可能不像疯狂"那样.可能一见钟情.请注意，为了比较步骤5和步骤6的角度，无需计算实际角度值.知道它们的余弦就足够了(即，无需涉及三角函数).

This solution might not be as "crazy" as it might appear at the first sight. Note that in order to compare angles at steps 5 and 6 there's no need to calculate the actual angle values. It is sufficient to know their cosines (i.e. there's no need to involve trigonometric functions).

代码的C ++版本

#include <cmath>
#include <array>
#include <algorithm>

struct pnt_t
{
  int x, y;

  pnt_t ccw90() const
    { return { -y, x }; }

  double length() const
    { return std::hypot(x, y); }

  pnt_t &operator -=(const pnt_t &rhs)
  {
    x -= rhs.x;
    y -= rhs.y;
    return *this;
  }

  friend pnt_t operator -(const pnt_t &lhs, const pnt_t &rhs)
    { return pnt_t(lhs) -= rhs; }

  friend int operator *(const pnt_t &lhs, const pnt_t &rhs)
    { return lhs.x * rhs.x + lhs.y * rhs.y; }
};

int side(const pnt_t &a, const pnt_t &b, const pnt_t &p)
{
  int cp = (b - a).ccw90() * (p - a);
  return (cp > 0) - (cp < 0);
}

void make_ccw(std::array<pnt_t, 3> &t)
{
  if (side(t[0], t[1], t[2]) < 0)
    std::swap(t[0], t[1]);
}

double ncos(pnt_t a, const pnt_t &o, pnt_t b)
{
  a -= o;
  b -= o;
  return -(a * b) / (a.length() * b.length());
}

bool inside_circle(std::array<pnt_t, 3> t, const pnt_t &p)
{
  make_ccw(t);

  std::array<int, 3> s = 
    { side(t[0], t[1], p), side(t[1], t[2], p), side(t[2], t[0], p) };

  unsigned outside = std::count(std::begin(s), std::end(s), -1);
  if (outside != 1)
    return outside == 0;

  while (s[0] >= 0)
  {
    std::rotate(std::begin(t), std::begin(t) + 1, std::end(t));
    std::rotate(std::begin(s), std::begin(s) + 1, std::end(s));
  }

  double 
    min_org = std::min({
      ncos(t[0], t[1], t[2]), ncos(t[2], t[0], t[1]), 
      ncos(t[1], t[0], p), ncos(p, t[1], t[0]) }),
    min_alt = std::min({
      ncos(t[1], t[2], p), ncos(p, t[2], t[0]), 
      ncos(t[0], p, t[2]), ncos(t[2], p, t[1]) });

  return min_org <= min_alt;
}

以及一些带有任意选择的三角形和大量随机点的测试

and a couple of tests with arbitrarily chosen triangles and a large number of random points

当然，即使不提及Delaunay三角剖分，也可以轻松地重新编写整个内容.从第4步开始，此解决方案基于循环四边形的相反角度的属性，必须达到180°.

Of course, the whole thing can be easily reformulated without even mentioning Delaunay triangulations. Starting from step 4 this solution is based in the property of the opposite angles of cyclic quadrilateral, which must sum to 180°.

这篇关于如何检查一个点是否在3点外接圆内?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！