查找关闭多边形iOS的总数

Question

我想找到近似形状的总数.

在图像中,有6个没有近似多边形.我试过以下方法

    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 寻路算法的递归部分，不同之处在于，潜在路径是累积的，而不是较短的路径在完成评估之前消除较长的路径。