Точка внутри правильного шестиугольника

Question

Я ищу совет о том, как лучше поступить. Я пытаюсь найти, находится ли заданная точка A: (a, b) внутри правильного шестиугольника, определенного с центром O: (x, y) и диаметром описанной окружности.

Для такого простого случая кажется излишним использовать приведение лучей или число обмоток, чтобы определить это, и в настоящее время я рассматриваю возможность нахождения угла (от горизонтали) линии OA, и «нормализуя» (возможно, не правильное слово) его в один из 6 равносторонних треугольников и выясняя, находится ли эта новая точка в этом треугольнике.

У меня такое ощущение, что я упускаю что-то простое, и есть простой способ (или, если мне действительно повезет, Java API) сделать это просто и эффективно.

Спасибо за вашу помощь.

Редактировать : шестиугольник ориентирован так, что одна из сторон плоская с горизонтальной.

Answer 1

Если вы уменьшите проблему до проверки {x = 0, y = 0, d = 1} в одном квадранте, вы можете сделать очень просто.

public boolean IsInsideHexagon(float x0, float y0, float d, float x, float y) {
    float dx = Math.abs(x - x0)/d;
    float dy = Math.abs(y - y0)/d;
    float a = 0.25 * Math.sqrt(3.0);
    return (dy <= a) && (a*dx + 0.25*dy <= 0.5*a);
}

• dy <= a проверяет, что точка находится ниже горизонтального края.
• a*dx + 0.25*dy <= 0.5*a проверяет, что точка находится слева от наклонного правого края.

Для {x0 = 0, y0 = 0, d = 1} угловые точки будут (±0.25, ±0.43) и (±0.5, 0.0).

Answer 2

Это то, что я использовал:

public bool InsideHexagon(float x, float y)
{
    // Check length (squared) against inner and outer radius
    float l2 = x * x + y * y;
    if (l2 > 1.0f) return false;
    if (l2 < 0.75f) return true; // (sqrt(3)/2)^2 = 3/4

    // Check against borders
    float px = x * 1.15470053838f; // 2/sqrt(3)
    if (px > 1.0f || px < -1.0f) return false;

    float py = 0.5f * px + y;
    if (py > 1.0f || py < -1.0f) return false;

    if (px - py > 1.0f || px - py < -1.0f) return false;

    return true;
}

px и py - это координаты x и y, спроецированные на систему координат, где намного проще проверить границы.

Answer 3

Вы можете использовать уравнения для каждой из сторон шестиугольника;с их помощью вы можете узнать, находится ли данная точка в той же полуплоскости, что и центр шестиугольника.

Например, верхняя правая сторона имеет уравнение:

-sqrt(3)x - y + sqrt(3)/2 = 0

Вы добавляете сюда координаты точки, а затем координаты центра.Если результаты имеют одинаковый знак, то точка находится в нижней левой полуплоскости (поэтому она может быть внутри шестиугольника).

Затем повторите процедуру, используя уравнения других сторон.
Обратите внимание, что этот алгоритм будет работать для любого выпуклого многоугольника .

Answer 4

Похоже, вы знаете общее решение: «Это похоже на излишнее использование ...».Итак, вот моя идея:

Рассчитать расстояние от точки до центра и назовем его l.

Затем вы можете сравнить его с инрадиусом (r) и околозвездом (R).).если l < r, то точка находится внутри шестиугольника, если l > R, то снаружи.Если r < l < R, то вы должны проверять каждую сторону соответственно, но поскольку R - r очень мала (13% длины стороны гекса), поэтому вероятность того, что вам придется выполнять сложные вычисления, ничтожна.

Формулы можно найти здесь: http://mathworld.wolfram.com/Hexagon.html

Answer 5

Сначала я бы проверил, находится ли точка внутри вписанной окружности (вы можете легко вычислить радиус вписанной окружности) или за пределами описанной окружности (которая у вас уже есть).

Первый означает, что точка находится, вторая означает, что она отсутствует.

Статистически, большинство точек ввода должны позволять вам решать на основе вышеупомянутых простых тестов.

Для сценария наихудшего случая (точка находится между вписанными и описанными кругами), я думаю, что вы можете найти две вершины, которые находятся ближе всего к точке, а затем посмотреть, на какой стороне сегмента V1V2 эта точка (внутренняя или внешний, относительно O-центра). Особый случай: точка равна одной из вершин => она в.

Если у меня появится более умная идея (или если я когда-нибудь начну действительно изучать тригонометрию), я отредактирую ответ, чтобы вы знали:)

Answer 6

Вам нужен код, чтобы узнать, находится ли точка внутри выпуклого многоугольника, частным случаем является шестиугольник.

Вот хороший ответ: https://stackoverflow.com/a/34689268/516188

Я изменил эту функцию для своего использования, я считаю свою версию более понятной.Это машинопись (ты просто щуришься и это JavaScript):

function vectorX(v: Vector): number {
    return v[1].x - v[0].x;
}

function vectorY(v: Vector): number {
    return v[1].y - v[0].y;
}

function crossProduct(v1: Vector, v2: Vector): number {
    return vectorX(v1)*vectorY(v2) - vectorY(v1)*vectorX(v2);
}

function isInConvexPolygon(testPoint: Point, polygon: Polygon): boolean {
    // https://stackoverflow.com/a/34689268/516188
    if (polygon.length < 3) {
        throw "Only supporting polygons of length at least 3";
    }
    // going through all the edges around the polygon. compute the
    // vector cross-product http://allenchou.net/2013/07/cross-product-of-2d-vectors/
    // to find out for each edge on which side of the edge is the point.
    // if the point is on the same side for all the edges, it's inside
    let initCrossIsPositive = undefined;
    for (var i=0;i<polygon.length;i++) {
        if (polygon[i].x === testPoint.x &&
            polygon[i].y === testPoint.y) {
            // testPoint is an edge of the polygon
            return true;
        }
        const curPointOnEdge = polygon[i];
        const nextPointOnEdge = polygon[(i+1)%polygon.length];
        const vector1 = <[Point,Point]>[curPointOnEdge, nextPointOnEdge];
        const vector2 = <[Point,Point]>[curPointOnEdge, testPoint];
        const cross = crossProduct(vector1, vector2);
        if (initCrossIsPositive === undefined) {
            initCrossIsPositive = cross > 0;
        } else {
            if (initCrossIsPositive !== (cross > 0)) {
                return false;
            }
        }
    }
    // all the cross-products have the same sign: we're inside
    return true;
}

Answer 7

Вычтите положение центра шестиугольника из вашей точки P, чтобы получить вектор V. Затем возьмите скалярное произведение V со следующими векторами, которые соответствуют трем парам противоположных ребер шестиугольника:

[0,1] ; the edges that are flat with the horizontal
[cos(30),sin(30)] ; the upper-right and lower-left edges
[cos(-30),sin(-30)] ; the lower-right and upper-left edges

Если любое из точечных произведений больше по величине, чем расстояние от центра шестиугольника до одного из его ребер, то точка не находится внутри шестиугольника.

Для справки, точкапроизведение векторов [a, b] и [c, d] представляет собой * c + b * d.

Угол "30" выше в градусах;)