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

Question

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

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

Answer 1

Классическая точка в задаче многоугольника. Удалить все точки каждого многоугольника, которые возвращают 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] 

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

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

Answer 2

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

Answer 3

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

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

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

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

• Clipper
• GEOS - см Polygon::Union
• CGAL - см 2D Regularized Boolean Set-Operations
• boost геометрия - см union_

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

Answer 4

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

Мы рассмотрим два многоугольника как A и B. Не имеет значения, что именно.

• Перемещение по многоугольник ищет любой точки, которая не находится внутри многоугольника B.
• Добавить эту точку многоугольника.
• Продолжайте движение вокруг полигона, проверяя и добавляя каждую точку в свою очередь.
• Когда вы обнаружите точку, которая находится внутри полигона B, посмотрите на линию между ней и предыдущей точкой.
• Узнайте, какая линия на полигоне B пересекается с этой линией.
• Определите точку пересечения между этими двумя линиями и добавьте ее в многоугольник.
• Определите, какая из двух точек, которые определяют пересекающуюся линию, принадлежащую многоугольнику B, НЕ находится внутри многоугольника A и добавляет это к новому многоугольнику.
• Определите, в каком направлении вокруг многоугольника B вам нужно идти, чтобы следующая точка не была той, которая находится на другом конце линии пересечения, и добавьте ее.
• Повторите с 3, за исключением использования многоугольника B вместо многоугольника A
• Продолжайте, пока не дойдете до точки, в которой вы начали, переместившись между полигонами по мере необходимости.

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