ios - 查找关闭多边形 iOS 的总数

Question

我想找到闭合形状的总数。

在图像中，有 6 个 no of close polygons 。 我尝试了以下方法

    for (NSInteger i = 0; i < [arrLinesInfo count]; i++) {

              NSDictionary *dictLineInfo = [arrLinesInfo objectAtIndex:i];

              startPoint = CGPointMake([[dictLineInfo valueForKey:@"line_start_point_x"] doubleValue], [[dictLineInfo valueForKey:@"line_start_point_y"] doubleValue]);
              endPoint = CGPointMake([[dictLineInfo valueForKey:@"line_end_point_x"] doubleValue], [[dictLineInfo valueForKey:@"line_end_point_y"] doubleValue]);

              [self isCircularRoute:startPoint withEndPoint:endPoint];
            }


            -(void) isCircularRoute:(CGPoint) lineStartPoint withEndPoint:(CGPoint) lineEndPoint 
            {
                NSPredicate *pre= [NSPredicate predicateWithFormat:[NSString stringWithFormat:@"
    (self.line_end_point_x == '%f' && self.line_end_point_y == '%f') OR 
        (self.line_start_point_x == '%f' && self.line_start_point_y == '%f') OR 
        (self.line_end_point_x == '%f' && self.line_end_point_y == '%f') OR
         (self.line_start_point_x == '%f' && self.line_start_point_y == '%f')", lineStartPoint.x, 
        lineStartPoint.y,
         lineStartPoint.x,
        lineStartPoint.y,
         lineEndPoint.x,
         lineEndPoint.y,
         lineEndPoint.x,
         lineEndPoint.y]];

 NSMutableArray *arrSamePointRef = [[arrLinesInfo filteredArrayUsingPredicate:pre] mutableCopy];

 arrSamePointRef = [[arrSamePointRef filteredArrayUsingPredicate:[NSPredicate predicateWithFormat:[NSString stringWithFormat:@"
(self.line_start_point_x != '%f' && self.line_start_point_y != '%f') &&
         (self.line_end_point_x != '%f' && self.line_end_point_y != '%f')", lineStartPoint.x
        , lineStartPoint.y
        , lineEndPoint.x
        , lineEndPoint.y]]] mutableCopy];//[arrSamePointRef removeObject:dictLineInfo];

                if(arrSamePointRef.count > 2){
                   totalPolygon = totalPolygon + 1;
                }
                NSLog(@"totalPolygon : ===== %tu", totalPolygon);

                for (NSDictionary *dictSingleLine in arrSamePointRef) {

                    CGPoint newStartPoint = CGPointMake([[dictSingleLine valueForKey:@"line_start_point_x"] doubleValue], [[dictSingleLine valueForKey:@"line_start_point_y"] doubleValue]);
                    CGPoint newEndPoint = CGPointMake([[dictSingleLine valueForKey:@"line_end_point_x"] doubleValue], [[dictSingleLine valueForKey:@"line_end_point_y"] doubleValue]);

                    [self isCircularRoute:newStartPoint withEndPoint:newEndPoint];

               }

            }

这是无限循环。

我在数组中有所有起点和终点对象。 如下所示的数组对象

[ { "point_start_lbl" : "a", "point_end_lbl" : "b", "line_start_point_x" : 200, "line_start_point_y" : 10, "line_end_point_x" : 100, "line_end_point_y" : 10, }, ... ]

请帮帮我。 提前致谢。

Answer 1

如果你有一个有序的边列表，那么你肯定有一个封闭的多边形，这样每条边都在下一条开始的顶点上结束，并且列表中没有重复的边。

我不清楚你的数据结构，但我可能因此:

定义一个对象，Edge，它标识两个顶点。

对于每个顶点，创建一个数组，其中包含接触该顶点的每条边。

然后，类似 Swift 风格的伪代码:

var successfulPaths: [Edge] = []
for edge in edges
{
    let usedEdges = [edge]
    attemptTraversalFrom(edge.vertex1, edge.vertex2, usedEdges, successfulPaths)
    attemptTraversalFrom(edge.vertex2, edge.vertex1, usedEdges, successfulPaths)
}

print("There were \(successfulPaths.count) successful paths")

[...]

func attemptTraversalFrom(startingVertex, endingVertex, usedEdges, successfulPaths) {
    let vertexEdges = endingVertex.edges
    for edge in (edges not in usedEdges) {
        let newEndingVertex = 
            (edge.vertex1 == endingVertex) ? edge.vertex2 : edge.vertex1

        if newEndingVertex == startingVertex {
            successfulPaths.add(usedEdges)
            return
        } else {
            let newUsedEdges = userEdges.addItem(edge)
            attemptTraversalFrom(startingVertex, newEndingVertex, newUsedEdges, successfulPaths)
        }
    }

    // Note: will automatically fall through to here and return
    // without adding anything to `successfulPaths` if there are
    // no further traversable edges
}

临时等。有点像 Dijkstra 寻路算法的递归部分，除了潜在路径是累积的，而不是较短的路径在完成评估之前消除较长的路径。