Как найти правильную половинную ссылку для разделения при вставке новой пары половинных ребер?

Question

Я работаю над процедурным проектом строительства города, в котором для представления дорог используется структура данных со списком половин / двусвязных краев. На изображении ниже, ранее существовавшие соединения имеют размер solid линий. Существуют две полукруглые связи: от А до В и от Х до Y. Мне нужно вставить новое соединение (пунктирная линия), состоящее из двух новых полукруглых элементов: 1 и 2. Стрелки обозначают направление половины. рассматриваемый ребро, с ближайшим узлом (solid окружностей), где начинается эта половина ребра.

Мне нужно программно определить, следует ли разделять связь половин ребра AB или XY. В этой ситуации ссылка AB должна быть разделена, создавая две новые полуголовые ссылки: A1 и 2B. Как бы вы go определили это?

Answer 1

Я думаю, у меня есть решение. Причины, по которым ссылки X1 / 2Y недействительны, заключаются в том, что они пересекаются друг с другом, когда вы рисуете ссылки от начала до конца sh. Это заставило меня задуматься о том, что тестирование на пересечение должно сработать.

Первый шаг к этому - найти «вектор создания» нового соединения (пунктирная линия). В этом случае node2 - это startPosition, а endPosition - это центральный узел. Это делается следующим образом:

creationVector = normalize(endPosition - startPosition);

Далее необходимо рассчитать две точки, связанные с узлом 2 на диаграмме: входящую и исходящую. Чтобы сохранить направление по часовой стрелке, входящая точка должна быть слева от вектора создания, а исходящая точка должна быть справа. На диаграммах ниже входящая точка имеет красный цвет, а исходящая точка - синий. Это делается следующим образом:

incomingPoint = nodeAPosition + new float2(-creationVector.y, creationVector.x);
outgoingPoint = nodeAPosition + new float2(creationVector.y, -creationVector.x);

Последний бит рисует две линии и проверяет, есть ли пересечение между ними. Начнем с недействительных ссылок, X1 / 2Y. В данном случае две линии, которые мы рисуем, это: nodeX для входящей точки и outgoingPoint для узла A. Решение, которое я нашел для тестирования пересечения, взято из этого сообщения в блоге . Ниже я приведу свою версию для полноты:

private float2 IntersectionPointGet(
        float2 a1,
        float2 a2,
        float2 b1,
        float2 b2,
        out bool isIntersection)
{
    float tmp = (b2.x - b1.x) * (a2.y - a1.y) - (b2.y - b1.y) * (a2.x - a1.x);

    if (tmp == 0)
    {
        isIntersection = false;
        return float2.zero;
    }

    float mu = ((a1.x - b1.x) * (a2.y - a1.y) - (a1.y - b1.y) * (a2.x - a1.x)) / tmp;

    isIntersection = true;
    return new float2(
        b1.x + (b2.x - b1.x) * mu,
        b1.y + (b2.y - b1.y) * mu
    );
}

Как видите, ссылки X1 / 2Y пересекаются и, следовательно, являются недействительными:

Сейчас сравните это с A1 / 2B, которые не пересекаются и, следовательно, действительны:

Хорошая особенность этого решения заключается в том, что вам нужно протестировать только одну пару ссылок. Если X1 / 2Y неверен, мы можем предположить, что A1 / 2B действителен. Это означает, что ссылка AB должна быть разделена, а ссылка XY должна быть оставлена ​​в покое.