指向旋转的2D矩形内部(不使用平移，触发函数或点积) [英] Point inside rotated 2D rectangle (not using translation, trig functions, or dot product)

问题描述

我想知道以下用于检查点是否在矩形内的算法是否有效. 我已经根据自己的直觉(没有足够的经验基础)来开发它，所以我很乐意听取对此事有更多经验的人的意见.

上下文:

• 该矩形定义有4个点.它可以旋转.
• 坐标始终是正数.
• 根据定义，如果该点与矩形相交，则视为该点.

假设:

• 使用点和矩形顶点之间的距离(下面的第一张图).
• 最大可能的总距离是该点位于一个顶点(第二张图)中.
• 如果点正好位于矩形的外部，则距离会更大(第三张图).

图表链接: http://i45.tinypic.com/id6o35.png

算法(Java):

static boolean pointInsideRectangle(Point[] rect, Point point) {
    double maxDistance = distance(rect[0], rect[1]);
    maxDistance += distance(rect[0], rect[2]);
    maxDistance += distance(rect[0], rect[3]);

    double distance = 0;
    for (Point rectPoint : rect) {          
        distance += distance(rectPoint, point);
        if (distance > maxDistance) return false;
    }
    return true;
}

问题:这正确吗?

解决方案

简短的回答:不:P(不要对此感到不满)

长答案:与您提到的四个圆(相对的顶点之间的最大距离)的区域相交不会产生矩形. 由于我在几何学上有些生疏，所以我无法给出完整的数学解释(对我来说是时间限制)，但是给您一些过程的伪代码，其中包含您要求的限制(无特殊公式)，对于Wikipeida的任何矩形均有效或一本几何书可以填补这些空白.

• 找到N，E，S，W顶点(最上，最右，最低和最左边的顶点)，这对于任何矩形来说都很容易，但是对齐的轴可以产生奇怪的顶点赋值(请参见带有示例的图像)
• 找到NE，SE，SW和NW边界，这是线方程维基百科中的示例或其他，因为它们会产生另一种类型的刺激/限制.

• 检查您的点是否在边界的右侧" 将不等式视为数学术语，只有矩形内的一个点满足四个限制，如您在所附图片中看到的那样.

• 我很抱歉，如果我忽略了可以完成此任务的java.geom命令

我希望这对您的努力有帮助

I was wondering if the following algorithm to check if a point is inside a rectangle is valid. I've developed it using my own intuition (no strong trig/math basis to support it), so I'd love to hear from someone with more experience in the matter.

Context:

• The rectangle is defined with 4 points. It could be rotated.
• Coordinates are always positive.
• By definition, the point is considered inside the rectangle if intersects it.

Hypothesis:

• Use the distance between the point and the rectangle vertices (first diagram below).
• The maximum possible total distance is when the point is in one vertex (second diagram).
• If the point is just outside the rectangle, the distance will be greater (third diagram).

Diagram link: http://i45.tinypic.com/id6o35.png

Algorithm (Java):

static boolean pointInsideRectangle(Point[] rect, Point point) {
    double maxDistance = distance(rect[0], rect[1]);
    maxDistance += distance(rect[0], rect[2]);
    maxDistance += distance(rect[0], rect[3]);

    double distance = 0;
    for (Point rectPoint : rect) {          
        distance += distance(rectPoint, point);
        if (distance > maxDistance) return false;
    }
    return true;
}

Questions: is this correct?

解决方案

Short answer: NO :P (don´t fell bad about it)

Long Answer: Intersecction the areas from the four circles that you mention (max distance between opposite vertex) does not produce a rectangle. Since I´m a bit rusty in geometry I can´t give full mathematical explanation (time constrain for my part), but give you some pseudocode of the procedure with the constrains that you ask (no fancy formulae), valid for any rectangle the wikipeida or a geometry book can fill the gaps.

• Find the N,E,S,W vertex (the uppermost, rightmost, lowest and leftmost vertex) this is trivially easy for any rectangle but the axis aligned who can produce oddly assignation of the vertex (see images with examples)
• Find the NE, SE, SW and NW border, this is the line equation in wikipedia or another link, again should be easy, but the axis aligned border should be analized carefully because those generate another type of ecuation/restriction.

• Check if your point is on the "right side" of the border see inequality as mathematical term, only a point inside your rectangle satisfy the four restrictions as you can see in the image attached.

• my apologies if I have overlook some command of java.geom that can accomplish this task

I hope this help with your endevour

这篇关于指向旋转的2D矩形内部(不使用平移，触发函数或点积)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！