Какао: «случайная» линия между двумя точками?

Question

В моем хобби-проекте Cocoa (на OSX) у меня есть представление с некоторыми выявленными моментами. Примерно так:

NSPoint pt1 = NSMakePoint(20,100);
NSPoint pt2 = NSMakePoint(100,30);

Я хотел бы создать извилистую линию (которая никогда не пересекается) между этими двумя точками. Очки могут отличаться, конечно. Я знаком с NSBezierPath, но я не вундеркинд графики.

Есть два варианта этого. С учетом NSBezierPath *p ... и настройкой [p moveToPoint:pt1]

1. Используйте [p lineToPoint:ptx], где я создаю извилистую линию с зубчатыми линиями и
2. Используйте [p curveToPoint:ptx controlPoint1:cpt1 controlPoint2:cpt2] с гладкой извилистой линией.

Второй случай кажется более сложным, так как разумные контрольные точки также должны быть рассчитаны.

Наконец, я хотел бы иметь возможность отрегулировать величину, с которой линия извивается. Если я установлю переменную, такую ​​как int numOfIntermediatePoints, равную 1, тогда будет плавная кривая между pt1 и pt2. Если я установлю numberOfIntermediatePoints на 10, в линии будет намного больше движения. Я не хочу, чтобы последние промежуточные точки были очень далеки от конечной точки (оставляя большое изменение в конце линии).

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

Какой лучший подход к этому?

---

Обновление

Следуя совету Томми, я отвел библиотеку Рэймонда Хилла Javascript-Voronoi в Obj-C. Вы можете найти его здесь: https://github.com/ccheaton/objcvoronoi

---

Еще одно обновление

Еще одно обновление - я поиграл с алгоритмом Дейкстры и обнаружил, что он излишний для того, чего я пытался достичь. В итоге я реализовал упрощенный вариант, который позволяет мне указывать направляющие узлы для случайной линии. На этом изображении начало строки находится в середине слева, конец строки - в середине справа, и есть ориентиры в точках (xMax * 0,33, 0) и (xMax * 0,66, yMax).

---

Окончательное обновление

Чтобы сделать его немного менее зазубренным, я добавил необязательный алгоритм релаксации. Производительность сейчас невелика, но это не имеет значения для предполагаемого использования.

Answer 1

Есть несколько подходов, которые приходят на ум.

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

Придумывая все по ходу дела, вы можете попробовать рекурсивный подход - начните с прямой линии от начала до конца, а затем для каждой прямой линии:

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

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

Примерно из той же школы мысли, выбрасывая кучу случайных препятствий между точками и запуская следопыт в стиле A *, возможно, получится что-то интересное.