Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Find total no of Close polygons iOS

I want to find total number of close shape.

enter image description here

In image, there are 6 no of close polygons . I have tried following method

    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];

               }

            }

This is go in infinite loop.

I have all start point and end point object in array. array object like below

[ { "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, }, ... ]

Please help me. Thanks in advance.

like image 780
Monish Avatar asked Jun 28 '16 11:06

Monish


1 Answers

You definitely have a closed polygon if you have an ordered list of edges such that each edge ends on the vertex that the next starts on and no edge is repeated within the list.

I'm unclear about your data structure but I might therefore:

Define an object, Edge that identifies two vertices.

For each vertex, create an array containing every single edge that touches that vertex.

Then, something like, in Swift-ish pseudocode:

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
}

Extemporaneous, etc. A bit like the recursive part of Dijkstra's pathfinding algorithm, except that potential paths are accumulated rather than shorter paths eliminating longer ones prior to complete evaluation.

like image 101
Tommy Avatar answered Oct 18 '22 07:10

Tommy