평면상의 4개의 점이 직사각형을 형성하는지 알아보시겠습니까?

평면상의 4개의 점이 직사각형을 형성하는지 알아보시겠습니까?

4개의 점(함수에 대한 원호)이 직사각형을 이루면 true를 반환하고 그렇지 않으면 false를 반환하는 함수를 C스타일의 의사 코드로 작성하는 방법을 가르쳐 주시겠습니까?

저는 먼저 동일한 x-값을 가진 두 개의 서로 다른 점 쌍을 찾고 나서 y축에 대해 이 작업을 수행하는 해결책을 생각해냈습니다.하지만 암호는 좀 길어요.다른 사람들이 무슨 생각을 하는지 궁금해서요.

• 구석점의 질량 중심을 구합니다: cx=(x1+x2+x3+x4)/4, cy=(y1+y2+y3+y4)/4
• 질량 중심에서 네 모서리까지의 거리의 제곱이 동일한지 시험한다.

bool isRectangle(double x1, double y1,
                 double x2, double y2,
                 double x3, double y3,
                 double x4, double y4)
{
  double cx,cy;
  double dd1,dd2,dd3,dd4;

  cx=(x1+x2+x3+x4)/4;
  cy=(y1+y2+y3+y4)/4;

  dd1=sqr(cx-x1)+sqr(cy-y1);
  dd2=sqr(cx-x2)+sqr(cy-y2);
  dd3=sqr(cx-x3)+sqr(cy-y3);
  dd4=sqr(cx-x4)+sqr(cy-y4);
  return dd1==dd2 && dd1==dd3 && dd1==dd4;
}

(물론 실제로는 두 부동소수점 번호 a와 b의 동일성에 대한 테스트는 유한한 정확도로 수행해야 한다: 예: abs(a-b) < 1E-6)

struct point
{
    int x, y;
}

// tests if angle abc is a right angle
int IsOrthogonal(point a, point b, point c)
{
    return (b.x - a.x) * (b.x - c.x) + (b.y - a.y) * (b.y - c.y) == 0;
}

int IsRectangle(point a, point b, point c, point d)
{
    return
        IsOrthogonal(a, b, c) &&
        IsOrthogonal(b, c, d) &&
        IsOrthogonal(c, d, a);
}

주문을 미리 알 수 없는 경우에는 조금 더 복잡한 확인이 필요합니다.

int IsRectangleAnyOrder(point a, point b, point c, point d)
{
    return IsRectangle(a, b, c, d) ||
           IsRectangle(b, c, a, d) ||
           IsRectangle(c, a, b, d);
}

1. Find all possible distances between given 4 points. (we will have 6 distances)
2. XOR all distances found in step #1
3. If the result after XORing is 0 then given 4 points are definitely vertices of a square or a rectangle otherwise, return false (given 4 points do not form a rectangle).
4. Now, to differentiate between square and rectangle 
   a. Find the largest distance out of 4 distances found in step #1. 
   b. Check if the largest distance / Math.sqrt (2) is equal to any other distance.
   c. If answer is No, then given four points form a rectangle otherwise they form a square.

여기서는 직사각형/사각형과 비트 매직의 기하학적 특성을 사용합니다.

직사각형 속성 재생 중

1. 직사각형의 반대쪽과 대각선은 길이가 같다.
2. 직사각형의 대각선 길이가 sqrt(2) 곱하기 길이의 경우 직사각형이 정사각형입니다.

비트 매직

1. XORing 등가치는 0을 반환합니다.

직사각형의 4개 모서리 사이의 거리는 대각선 및 길이가 다른 각 변에 대해 각각 2개씩 항상 3개의 쌍을 형성하므로 XOR을 지정하면 직사각형의 경우 모든 값이 0으로 반환됩니다.

한 지점에서 다른 세 지점까지의 거리는 직각 삼각형을 형성해야 합니다.

|   /      /||  /      / || /      /  ||/___   /___|

d1 = sqrt( (x2-x1)^2 + (y2-y1)^2 ) 
d2 = sqrt( (x3-x1)^2 + (y3-y1)^2 ) 
d3 = sqrt( (x4-x1)^2 + (y4-y1)^2 ) 
if d1^2 == d2^2 + d3^2 then it's a rectangle

심플화:

d1 = (x2-x1)^2 + (y2-y1)^2
d2 = (x3-x1)^2 + (y3-y1)^2
d3 = (x4-x1)^2 + (y4-y1)^2
if d1 == d2+d3 or d2 == d1+d3 or d3 == d1+d2 then return true

저도 최근에 비슷한 도전에 직면했지만, Python에서는 이것이 Python에서 생각해 낸 것입니다.아마 이 방법은 가치가 있을지도 모릅니다.즉, 6개의 선이 있으며, 한 세트로 작성될 경우 길이, 폭, 대각선 등 3개의 고유한 선 거리가 남아 있어야 합니다.

def con_rec(a,b,c,d): 
        d1 = a.distanceFromPoint(b)
        d2 = b.distanceFromPoint(c)
        d3 = c.distanceFromPoint(d)
        d4 = d.distanceFromPoint(a)
        d5 = d.distanceFromPoint(b)
        d6 = a.distanceFromPoint(c)
        lst = [d1,d2,d3,d4,d5,d6] # list of all combinations 
        of point to point distances
        if min(lst) * math.sqrt(2) == max(lst): # this confirms a square, not a rectangle
            return False
        z = set(lst) # set of unique values in ck
        if len(lst) == 3: # there should be three values, length, width, diagonal, if a 
        4th, it's not a rectangle
            return True
        else: # not a rectangle
            return False

• 그 정점 중 하나가 원점에 놓이도록 사변형을 번역하다
• 나머지 3개의 점은 원점에서 3개의 벡터를 형성한다
• 둘 중 하나는 대각선을 나타내야 한다
• 나머지 두 개는 측면을 나타내야 한다
• 평행사변형 규칙에 따라 변이 대각선을 형성하면 우리는 평행사변형을 갖는다
• 변이 직각을 이루면 직각을 가진 평행사변형이다
• 평행사변형의 대각은 같다
• 평행사변형의 연속각은 보충각이다
• 그러므로 모든 각도는 직각이다
• 그것은 직사각형이다.

• 코드에서는 훨씬 간결하지만 :-)

  static bool IsRectangle(
     int x1, int y1, int x2, int y2, 
     int x3, int y3, int x4, int y4)
  {
      x2 -= x1; x3 -= x1; x4 -= x1; y2 -= y1; y3 -= y1; y4 -= y1;
      return
          (x2 + x3 == x4 && y2 + y3 == y4 && x2 * x3 == -y2 * y3) ||
          (x2 + x4 == x3 && y2 + y4 == y3 && x2 * x4 == -y2 * y4) ||
          (x3 + x4 == x2 && y3 + y4 == y2 && x3 * x4 == -y3 * y4);
  }
  

• (부동소수점 값으로 동작시키려면 헤더의 int 선언만 무작정 치환하지 마십시오.그것은 나쁜 습관이다.그들은 이유가 있다.부동소수점 결과를 비교할 때는 항상 오차의 상한을 사용하여 작업해야 합니다.)

포인트가 A, B, C, D이고 순서를 알고 있으면 벡터가 계산됩니다.

x=B-A, y=C-B, z=D-C 및 w=A-D

그런 다음 도트 곱(x dot y), (y dot z), (z dot w) 및 (w dot x)를 선택합니다.모두 0이면 직사각형이 됩니다.

기울기의 곱이 -1이면 두 개의 별빛 선이 수직인 것을 알 수 있습니다. 평면이 주어지기 때문에 연속된 세 개의 선의 기울기를 구한 다음 곱하여 정말로 수직인지 여부를 확인할 수 있습니다.선 L1, L2, L3이 있다고 가정합니다.L1이 L2에 수직이고 L2가 L3에 수직이면 m(L1)*m(L2)=-1과 m(L2)*m(L3)=-1의 직사각형 및 기울기가 됩니다. 즉, 직사각형임을 의미합니다.코드는 다음과 같습니다.

bool isRectangle(double x1,double y1,
        double x2,double y2,
        double x3,double y3,
        double x4,double y4){
    double m1,m2,m3;
    m1 = (y2-y1)/(x2-x1);
    m2 = (y2-y3)/(x2-x3);
    m3 = (y4-y3)/(x4-x3);

    if((m1*m2)==-1 && (m2*m3)==-1)
        return true;
    else
        return false;
}

점곱 제안을 한 단계 더 나아가 점의 3개 중 어느 한 점에 의해 만들어진 벡터 두 개가 수직인지 확인한 다음 x와 y가 네 번째 점과 일치하는지 확인합니다.

[Ax,Ay] [Bx,By] [Cx,Cy] [Dx,Dy] 포인트가 있으면

벡터 v = B-A 벡터 u = C-A

v(dot)u/|v||u| == cos(theta)

그래서 만약 (v.u == 0) 이면 여기에 몇 개의 수직선이 있습니다.

사실 C 프로그래밍은 잘 모르지만, 여기 당신을 위한 "메타" 프로그래밍이 있습니다.p

if (v==[0,0] || u==[0,0] || u==v || D==A) {not a rectangle, not even a quadrilateral}

var dot = (v1*u1 + v2*u2); //computes the "top half" of (v.u/|v||u|)
if (dot == 0) { //potentially a rectangle if true

    if (Dy==By && Dx==Cx){
     is a rectangle
    }

    else if (Dx==Bx && Dy==Cy){
     is a rectangle
    }
}
else {not a rectangle}

제곱근도 없고 0으로 나눌 가능성도 없어요이전 게시글에서 사람들이 이 문제를 언급하는 것을 보고 대안을 제시하려고 했습니다.

따라서 계산상으로는 v와 u를 구하려면 4개의 빼기, 2개의 곱셈, 1개의 덧셈이 필요하며 1과 7 사이의 등식을 확인해야 합니다.

내가 지어낸 얘기일지도 모르지만, 어딘가에서 읽었던 뺄셈과 곱셈이 "더 빠른" 계산이라는 걸 어렴풋이 기억한다.변수/어레이를 선언하고 값을 설정하는 것도 꽤 빠르다고 생각합니다.

죄송합니다, 저는 이런 일은 처음이라 방금 쓴 글에 대한 피드백을 받고 싶습니다.

편집: 아래 코멘트를 기반으로 시도합니다.

A = [a1,a2];
B = [b1,b2];
C = [c1,c2];
D = [d1,d2];

u = (b1-a1,b2-a2);
v = (c1-a1,c2-a2);

if ( u==0 || v==0 || A==D || u==v)
    {!rectangle} // get the obvious out of the way

var dot = u1*v1 + u2*v2;
var pgram = [a1+u1+v1,a2+u2+v2]
if (dot == 0 && pgram == D) {rectangle} // will be true 50% of the time if rectangle
else if (pgram == D) {
    w = [d1-a1,d2-a2];

    if (w1*u1 + w2*u2 == 0) {rectangle} //25% chance
    else if (w1*v1 + w2*v2 == 0) {rectangle} //25% chance

    else {!rectangle}
}
else {!rectangle}

이 4개의 점을 검증하는 것은 우선 평행사변형을 형성하고, 그 후 직각이 하나 존재하는지 알아내는 것이다.
1. 평행사변형을 확인합니다.

input 4 points A, B, C, D;

if(A, B, C, D are the same points), exit;// not a rectangle;

else form 3 vectors, AB, AC, AD, verify(AB=AC+AD || AC=AB+AD || AD=AB+AC), \\if one of them satisfied, this is a parallelogram;

2. 직각으로 기울이다

through the last step, we could find which two points are the adjacent points of A;

We need to find out if angle A is a right angle, if it is, then rectangle.

벌레가 있는지 몰랐어요.있는지 알아봐 주세요.

이것은 Python에서의 축 정렬 직사각형 테스트에 대한 알고리즘 제안입니다.

첫 번째 점을 피벗으로 잡고 다른 모든 점이 동일한 폭과 높이를 준수해야 하며, (1, 2, 2) (10, 30), (10, 30)과 같은 경우를 고려하기 위해 세트를 통해 모든 점이 구별되는지 확인합니다.

from collections import namedtuple

Point = namedtuple('Point', ('x', 'y'))

def is_rectangle(p1, p2, p3, p4) -> bool:
    width = None
    height = None

    # All must be distinct
    if (len(set((p1, p2, p3, p4))) < 4):
        return False

    pivot = p1

    for point in (p2, p3, p4):
        candidate_width = point.x - pivot.x
        candidate_height = point.y - pivot.y

        if (candidate_width != 0):
            if (width is None):
                width = candidate_width
            elif (width != candidate_width):
                return False

        if (candidate_height != 0):
            if (height is None):
                height = candidate_height
            elif (height != candidate_height):
                return False

    return width is not None and height is not None

# Some Examples
print(is_rectangle(Point(10, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(100, 50), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 10), Point(20, 50), Point(10, 40), Point(20, 40)))
print(is_rectangle(Point(10, 30), Point(20, 30), Point(10, 30), Point(20, 30)))
print(is_rectangle(Point(10, 30), Point(10, 30), Point(10, 30), Point(10, 30)))
print(is_rectangle(Point(1, 2), Point(10, 30), Point(1, 2), Point(10, 30)))
print(is_rectangle(Point(10, 50), Point(80, 50), Point(10, 40), Point(80, 40)))

언급URL : https://stackoverflow.com/questions/2303278/find-if-4-points-on-a-plane-form-a-rectangle