Перпендикулярная линия от кривой Безье до точки - PullRequest
Новая
       95

Перпендикулярная линия от кривой Безье до точки

1 голос
/ 09 января 2020

Вопрос

Мне нужно получить точку Q кубической кривой c (2d) B (t) где линия из точки Q в другую заданную точку P пересекается перпендикулярно с кривой Безье.

  • Я знаю: P , B (т)
  • Я ищу: Q (в основном я хочу иметь наклон г но я могу легко вычислить это, когда знаю Q , но достаточно наклон g )

То, что я делал до сих пор (вы можете пропустить это)

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

Я пытался решить это с моими (основами c) знанием математики, но я не могу закончить sh это. Это то, что у меня есть сейчас (пожалуйста, не слишком строго с обозначениями, я не очень хорош в этом):

Следующие формулы будут выражаться как y (x) чтобы получить один результат, это должно быть рассчитано для y (x) и x (y) . Точка P является контрольной точкой, Q - это точка, где линия г (х) от Q до P перпендикулярно кривой Безье B (t) = (x, y) T . Выражение для строки г (х) может быть получено с помощью

, где B (x) - кривая Безье в декартовых координатах, B '(x) - производная (в декартовых координатах) и k - пересечение с осью y. Чтобы получить наклон г (х) , нужно решить

Для расчета B (x) нужно решить B (t) для t и затем подключить его обратно к B (t) . Таким образом, в каждой точке кривой Безье есть отношение

, которое также применяется к производной B ' (т) .

Производное B (т) равно (согласно Википедии )

Решение этого для t ( с вольфрам альфа ) приводит к

где a 0 = ( P 1 - P 0 ) x , a 1 = ( P 2 - P 1 ) x и a 2 = ( P 3 - P 2 ) х . Если подключить * t i * s обратно к B (t) , то получится ( wolfram alpha для t 1 , вольфрам альфа для т 2 , вольфрам альфа для т 3 )

Теперь следующая вещь будет использовать y = B '(x) и второе уравнение и исключить x , но я понятия не имею, как, и я даже не знаю, возможно ли это.

Ответы [ 2 ]

3 голосов
/ 09 января 2020

Вы уже знаете производную кривой Безье - она ​​описывает касательную к кривой. Эта касательная должна быть перпендикулярна вектору QP. Таким образом, вам нужно написать обе компоненты вектора PQ и касательного вектора T в этой точке 

PQx = (1-t)^3 * P0.x + 3*t*(1-t)^2*P1.x  ... - P.x
PQy = (1-t)^3 * P0.y + ... - P.y
Tx = 3*(1-t)^2 * (P1.x - P0.x).... and so on
Ty = ....

и составить уравнение для точечного произведения векторов T и QP (точечное произведение равно нулю для перпендикулярных векторов) : 

 PQx * Tx + PQy * Ty = 0

Теперь откройте скобки и получите уравнение 5-й градус для неизвестного t.

Не существует решения в замкнутой форме для такого полиномиального уравнения так что вам нужен какой-то числовой root алгоритм поиска (используйте те, которые предназначены для полиномиальных корней)

0 голосов
/ 13 января 2020

Я нашел реализацию аппроксимации для моей задачи, сделанную mbostock на Github , которая реализовала идею этой онлайн-книги, которая была специально создана @ Mike'Pomax'Kamermans о кривые Безье. Если вам приходится иметь дело с кривыми Безье, проверьте это. Это объясняет большинство проблем, которые у меня были с кривыми Безье.

Идея алгоритма заключается в следующем:

  1. Сделайте грубое приближение:
    1. Рассчитать Q прибл. i путем подключения различных t i s в B ( t ) (mbostock использует t 1 = 0, t 2 = 1/8, t 3 = 2/8, ...).
    2. Рассчитать квадратичные значения c (сохранить один квадрат root расчет) расстояние между Q приблизительно, i и P .
    3. Сохранить Q ок, i и t i , который является ближайшим (с наименьшим расстоянием).
  2. Сделайте более точное приближение:
    1. Выберите точность q .
    2. Рассчитать t до * 10 87 * = t i - q .
    3. Проверьте, находится ли расстояние между Q приблизительно, до = B ( t до ) и P меньше, чем расстояние между Q приблизительно, i и P , если да, установить Q приблизительно, i = Q приблизительно, до и начинайте с 2 (точное приближение), если нет продолжения.
    4. Рассчитайте t после = t i + q .
    5. Проверьте, находится ли расстояние между Q приблизительно, после = B ( t после ) и P меньше расстояния между Q прибл., i и P , если да, установить Q * 11 87 * приблизительно, i = Q после и начинаются с 2 (точное приближение), если нет продолжения .
    6. Q приблизительно, i является ближайшим. Если точность достаточно хорошая, остановитесь здесь. Если нет, то уменьшите точность q (mbostock делится на два) и начните снова с 2 (точное приближение).

Как уже упоминалось есть реализация mbostock на Github . Я вставляю код здесь в случае, если ссылка не работает. ЭТО НЕ МОЙ СОБСТВЕННЫЙ КОД. 

var points = [[474,276],[586,393],[378,388],[338,323],[341,138],[547,252],[589,148],[346,227],[365,108],[562,62]];
var width = 960,
    height = 500;
var line = d3.svg.line()
    .interpolate("cardinal");
var svg = d3.select("body").append("svg")
    .attr("width", width)
    .attr("height", height);
var path = svg.append("path")
    .datum(points)
    .attr("d", line);
var line = svg.append("line");
var circle = svg.append("circle")
    .attr("cx", -10)
    .attr("cy", -10)
    .attr("r", 3.5);
svg.append("rect")
    .attr("width", width)
    .attr("height", height)
    .on("mousemove", mousemoved);
// adding coordinates display
var coords = svg.append("text");
function mousemoved() {
  var m = d3.mouse(this),
      p = closestPoint(path.node(), m);
  line.attr("x1", p[0]).attr("y1", p[1]).attr("x2", m[0]).attr("y2", m[1]);
  circle.attr("cx", p[0]).attr("cy", p[1]);
  coords.attr("x", (p[0] + m[0]) / 2).attr("y", (p[1] + m[1]) / 2).html("Q(" + Math.round(p[0]) + ", " + Math.round(p[1]) + ")");
}
function closestPoint(pathNode, point) {
  var pathLength = pathNode.getTotalLength(),
      precision = 8,
      best,
      bestLength,
      bestDistance = Infinity;
  // linear scan for coarse approximation
  for (var scan, scanLength = 0, scanDistance; scanLength <= pathLength; scanLength += precision) {
    if ((scanDistance = distance2(scan = pathNode.getPointAtLength(scanLength))) < bestDistance) {
      best = scan, bestLength = scanLength, bestDistance = scanDistance;
    }
  }
  // binary search for precise estimate
  precision /= 2;
  while (precision > 0.5) {
    var before,
        after,
        beforeLength,
        afterLength,
        beforeDistance,
        afterDistance;
    if ((beforeLength = bestLength - precision) >= 0 && (beforeDistance = distance2(before = pathNode.getPointAtLength(beforeLength))) < bestDistance) {
      best = before, bestLength = beforeLength, bestDistance = beforeDistance;
    } else if ((afterLength = bestLength + precision) <= pathLength && (afterDistance = distance2(after = pathNode.getPointAtLength(afterLength))) < bestDistance) {
      best = after, bestLength = afterLength, bestDistance = afterDistance;
    } else {
      precision /= 2;
    }
  }
  best = [best.x, best.y];
  best.distance = Math.sqrt(bestDistance);
  return best;
  function distance2(p) {
    var dx = p.x - point[0],
        dy = p.y - point[1];
    return dx * dx + dy * dy;
  }
}
.disclaimer{
  padding: 10px;
  border-left: 3px solid #ffcc00;
  background: #fffddd;
}
path {
  fill: none;
  stroke: #000;
  stroke-width: 1.5px;
}
line {
  fill: none;
  stroke: red;
  stroke-width: 1.5px;
}
circle {
  fill: red;
}
rect {
  fill: none;
  cursor: crosshair;
  pointer-events: all;
}
<script src="https://cdnjs.cloudflare.com/ajax/libs/d3/3.5.17/d3.min.js"></script>
<div class="disclaimer">
  This is not my own code. This is made by <a href="https://gist.github.com/mbostock/8027637">mbostock on Github</a> based on Mike Kamermans <a href="https://pomax.github.io/bezierinfo/#projections">Primer on Bézier Curves online book</a>.
</div>
...