Как нарисовать контур вокруг любой линии

Question

Итак, у меня есть произвольная линия (см. Пример, показанный на рис. 1), состоящая из n точек

Я хочу нарисовать контур вокруг этой линии (см. Рис.2) поэтому мне нужно вычислить точки окружающего многоугольника.

Я начал с расширения линии, но это не сработает - см. Рисунок 3

Любые предложения о том, как это сделать?

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

Answer 1

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

Когда линии не совпадают (2-3, 6-7 и 12-13), вы добавляете соединение строк (синим цветом),Соединение линии может быть соединением фаски (2-3), просто соединяя точки, или соединением miter , продолжая линии, пока они не встретятся (6-7) или скругление путем построения кривой.

Когда линии встретятся, просто возьмите точку пересечения (синие точки).

В конце линии необходимо добавить заглушка (также синим цветом).Заглушка может быть прикладом (8-9) путем соединения точек, выступающей заглушкой (1-16) путем небольшого удлинения линий перед их соединением или круглая крышка (не показана).

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

Answer 2

Я нашел способ вычисления точек контура линии. Для каждой точки исходной линии вам нужно будет вычислить 2 точки для контура:

1. для каждого отрезка линии исходной линии (между 2 точками) вы должны вычислить его нормальный вектор (красный)
2. для каждой точки, добавьте нормали предыдущего и следующего отрезка. Это создает новый вектор (зеленый)
3. разделите новый вектор со значением: k l + 1, где k l - скалярное произведение нормальных векторов. Вы получите синий вектор. Затем добавьте этот вектор к текущей точке и ее противоположному вектору, и вы получите 2 точки контура для текущей точки

цвета выше соответствуют этому изображению .

Я запрограммировал эту функцию на C, но я использовал Accelerate Framework, поэтому его не очень легко читать. Вы можете найти исходный код здесь и видео с демонстрацией здесь .

Answer 3

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

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

• наконец, он добавляет каждую точку в нужном порядке, чтобы сделать многоугольник

  - (hOzPolygon2D *) convertToPolygonWithWidth:(double) polyWidth
  {
  
  double shift = polyWidth / 2.;
  
  NSMutableArray *tempEdgesRight = [[[NSMutableArray alloc] init] autorelease];
  NSMutableArray *tempEdgesLeft = [[[NSMutableArray alloc] init] autorelease];
  
  NSMutableArray *tempPolyPoints = [[[NSMutableArray alloc] init] autorelease];
  
  // Move your points on the right by half the desired width
  
  // My edges are already computed in a NSArray* called edges, 
  // but you can use pairs of vectors and adapt all this
  
  for (hOzEdge2D *edge in edges) {
  
  hOzVector2 v = hOzVector2([[edge pointB] x] - [[edge pointA] x], [[edge pointB] y] - [[edge pointA] y]);
  double mag = sqrt (v.x * v.x + v.y * v.y);
  v.x = v.x / mag;
  v.y = v.y / mag;
  
  double temp = v.x;
  v.x = v.y;
  v.y = -temp;
  
  hOzPoint2D *newPointA = [[hOzPoint2D alloc] init];
  [newPointA setX:([[edge pointA] x] + v.x * shift)];
  [newPointA setY:([[edge pointA] y] + v.y * shift)];
  
  hOzPoint2D *newPointB = [[hOzPoint2D alloc] init];
  [newPointB setX:([[edge pointB] x] + v.x * shift)];
  [newPointB setY:([[edge pointB] y] + v.y * shift)];
  
  [tempEdgesRight addObject:[hOzEdge2D edge2DWithPointA:newPointA pointB:newPointB]];
  
  }
  
  // With the same polyline, move on the left
  
  for (int j = [edges count] - 1; j >= 0; j--) {
  
  hOzVector2 v = hOzVector2([[[edges objectAtIndex:j] pointB] x] - [[[edges objectAtIndex:j] pointA] x], [[[edges objectAtIndex:j] pointB] y] - [[[edges objectAtIndex:j] pointA] y]);
  double mag = sqrt (v.x * v.x + v.y * v.y);
  v.x = v.x / mag;
  v.y = v.y / mag;
  
  double temp = v.x;
  v.x = v.y;
  v.y = -temp;
  
  hOzPoint2D *newPointA = [[hOzPoint2D alloc] init];
  [newPointA setX:([[[edges objectAtIndex:j] pointB] x] - v.x * shift)];
  [newPointA setY:([[[edges objectAtIndex:j] pointB] y] - v.y * shift)];
  
  hOzPoint2D *newPointB = [[hOzPoint2D alloc] init];
  [newPointB setX:([[[edges objectAtIndex:j] pointA] x] - v.x * shift)];
  [newPointB setY:([[[edges objectAtIndex:j] pointA] y] - v.y * shift)];
  
  [tempEdgesLeft addObject:[hOzEdge2D edge2DWithPointA:newPointA pointB:newPointB]];
  
  }
  
  
  
  // Add the static points and the intersection points to a points array that will define your polygon
  
  [tempPolyPoints addObject:[[tempEdgesRight objectAtIndex:0] pointA]];  // The first point of the right array
  
  for (int k = 0; k < [tempEdgesRight count] - 1; k++) {
  
  // For this function, see the link below in the answer
  
  hOzPoint2D *inter = [[tempEdgesRight objectAtIndex:k] getIntersectionWithStraight:[tempEdgesRight objectAtIndex:k+1]];   
  
  if (inter == nil) {    // if the edges are parallel, we insert a known point
      [tempPolyPoints addObject:[[tempEdgesRight objectAtIndex:k] pointB]];
  } else {
      [tempPolyPoints addObject:inter];
  }
  }
  
  [tempPolyPoints addObject:[[tempEdgesRight lastObject] pointB]];    // The last point of the right array
  
  [tempPolyPoints addObject:[[tempEdgesLeft objectAtIndex:0] pointA]];
  
  // Then the left array, same thing
  
  for (int k = 0; k < [tempEdgesLeft count] - 1; k++) {
  hOzPoint2D *inter = [[tempEdgesLeft objectAtIndex:k] getIntersectionWithStraight:[tempEdgesLeft objectAtIndex:k+1]];
  
  if (inter == nil) {
      [tempPolyPoints addObject:[[tempEdgesLeft objectAtIndex:k] pointB]];
  } else {
      [tempPolyPoints addObject:inter];
  }
  }
  
  [tempPolyPoints addObject:[[tempEdgesLeft lastObject] pointB]];
  
  // Create your polygon with this new ordered points array.
  hOzPolygon2D *poly = [hOzPolygon2D polygon2DWithArrayOfPoints:tempPolyPoints];
  
  return poly;
  
  }
  

Вот некоторые пояснения для точки пересечения с кодом C: http://alienryderflex.com/intersect/

Answer 4

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

http://www.math.niu.edu/~rusin/known-math/95/line_segs

Answer 5

Создайте все линии перед тем, как их рендерить.

Когда вы это сделаете, они должны перекрываться, например:

Те, которые я нарисовал, очевидно, это теобрезается, что бы раскрыть контур.