Объединение Пересекающихся CGPaths на iOS

У меня проблема в приложении, над которым я работаю. Скажем, у меня есть два довольно сложных CGPath, и я добавляю их обоих в CGMutablePath (таким образом, объединяя их). Хорошо, там, где пересекаются два пути, внутри друг друга будут точки. Я хочу устранить эти внутренние точки и по существу нарисовать внешнюю или контурную схему пути. Мне трудно понять, как я поступил бы по этому поводу.

Edit: Вот пример того, о чем я говорю. Синие и красные прямоугольники представляют точки вдоль CGPaths. Красные прямоугольники - это точки, которые находятся внутри обоих путей. Я хотел бы как-то устранить красные точки и перерисовать только контур пути.

enter image description here

 daveMac01 июн. 2012 г., 01:09
@robmayoff Я отредактировал свой вопрос, чтобы, надеюсь, уточнить, что я пытаюсь сделать.
 Shrawan16 дек. 2016 г., 11:09
@daveMac: Вы можете сослаться на: -stackoverflow.com/questions/23497703/…
 rob mayoff31 мая 2012 г., 20:16
Вы имеете в виду, что вы хотите вычислить объединение путей? Или ты хочешьsymmetric difference путей?

Ответы на вопрос(4)

Недостаточно просто объединить два набора точек. Чтобы определить комбинированные полигоны, вам нужно сделать следующее. Извините, у меня есть только псевдокод, я только начал смотреть на эту проблему.

Мы будем рассматривать два полигона как A и B. Неважно, какой есть какой.

Move around polygon A looking for any point that is NOT inside polygon B. Add this point to the polygon. Continue around the polygon, testing and adding each point in turn. When you discover a point that IS inside polygon B, look at the line between it and the previous point. Find out which line on polygon B intersects with this line. Determine the point of intersection between these two lines and add it to the polygon. Determine which of the two points that define the intersecting line belonging to polygon B is NOT inside polygon A and add that to the new polygon. Determine which direction around polygon B you need to go in order that the next point will NOT be the one on the other end of the line of intersection and add it. Repeat from 3, except using polygon B instead of polygon A Continue until you reach the point you started from, swapping between polygons as necessary.

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

То, что вы описываете, является объединением путей & apos; интерьеры.

Если ваши пути содержат кривые, это сложная проблема.

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

В этом случае вам нужна функция объединения полигонов. Этот вид алгоритма довольно прост в области, известной как & # x201C; вычислительная геометрия & # x201D ;. Я не знаю ни одной специфичной для Objective-C реализации объединения полигонов. Возможно, вам удастся найти чистую библиотеку C, но гораздо легче найти библиотеку C ++. Вы можете использовать C ++, если вы измените расширение файла с.m в.mm, Вот некоторые библиотеки C ++, которые могут вычислить объединение полигонов:

Clipper GEOS - see Polygon::Union CGAL - see 2D Regularized Boolean Set-Operations boost geometry - see union_

Обратите внимание, что во всех случаях вам необходимо использоватьCGPathApply извлекать вершины вашего пути, если у вас их еще нет в другом формате.

Классическая точка в задаче многоугольника. Удалите все точки в каждом многоугольнике, которые возвращают 1, ссылаясь на другой многоугольник:

int pnpoly(int npol, float *xp, float *yp, float x, float y)
{
  int i, j, c = 0;
  for (i = 0, j = npol-1; i < npol; j = i++) {
    if ((((yp[i] <= y) && (y < yp[j])) ||
         ((yp[j] <= y) && (y < yp[i]))) &&
        (x < (xp[j] - xp[i]) * (y - yp[i]) / (yp[j] - yp[i]) + xp[i]))
      c = !c;
  }
  return c;
}

Объедините два пути с удаленными точками.

Псевдокод для всей процедуры:

define starPoly with 10 points
define simplePoly with 7 points

for each point in starPoly
    if ( pnpoly( 7, simplePoly.Xs[], simplePoly.Ys[], point.x, point.y ) == 0 )
        clipedStarPoly += point;

for each point in simplePoly
    if ( pnpoly( 10, starPoly.Xs[], starPoly.Ys[], point.x, point.y ) == 0 )
        clipedSimplePoly += point;

for each point in clipedStarPoly
    solutionPoly += point;

for each point in clipedSimplePoly
    solutionPoly += point;

solutionPoly += solutionPoly.point[0]

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

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

 daveMac07 июн. 2012 г., 18:08
Я занимаюсь программированием уже два года и горжусь тем, что всегда пытаюсь найти решения самостоятельно, если у меня есть такая возможность, однако я понятия не имею, что вы пишете, когда пишете что-то вроде: & quot; (pnpoly (7, simplePoly.Xs [], simplePoly.Ys [], point.x, point.y) == 0) & quot; Что именно я передаю, когда пишу "simplePoly.Xs []"? и где я получаю "point.x" и "point.y" от? Простите мое невежество, но это не является полным или полным ответом на мой вопрос и в его нынешнем состоянии не дает вознаграждение (независимо от того, потерял я его или нет, не имеет значения).
 daveMac06 июн. 2012 г., 19:27
Я думаю, что я очень хорошо понимаю. Я знаю, что это просто псевдокод, но я думаю, что это действительно поможет увидеть рабочий пример с использованием CGPaths.
 daveMac05 июн. 2012 г., 15:55
Как насчет небольшого объяснения относительно того, как именно это использовать, где это использовать и что оно делает.
 daveMac07 июн. 2012 г., 18:04
gjpc это не полное решение моего вопроса. Я так и не подтвердил, что это так, просто сказал, что, как мне кажется, я понимаю, что вы предлагаете. Вы просто удаляете баллы, но, поскольку я довольно долго экспериментировал с решением этой проблемы, он намного сложнее, чем этот. Вы должны не только удалить ненужные точки, но и добавить новые точки на новых перекрестках. Более того, ваше решение очень расплывчато в том смысле, что оно не использует особенности CGPath и поэтому немного сбивает с толку то, как именно оно должно быть написано.
 06 июн. 2012 г., 18:02
Эй, Дейв, этого достаточно объяснения?

использованиеCGPathAddPath, Супер прост в использовании.

Ваш ответ на вопрос