Блог

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

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

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

Есть предложения о том, как это сделать?

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

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

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

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

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

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

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

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

Цвета, приведенные выше, соответствуют этому изображению.

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

Создайте все линии перед их визуализацией.

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

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

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

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

Вот мой код на 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 /