How to draw a specific CGPath with unordered CGPoints
Consider this ASCII drawing:
A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ D
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
| |
|_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _|
B C
Points A, B, C, and D are known CGPoints within an NSMutableArray and have been used to create a filled CGPath . Now consider this drawing:
A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ D
| |
| |
| |
| |
| H _ _ _ I |
| | | |
| | | |
| F _ _ _| | |
| | G | |
| | |_ _ _ K |
| | J | |
| | | |
|_ _ _ _| _ _ _ _ _ _ _ _ |_ _ _|
B E L C
CGPoints E, F, G, H, I, J, K, and L are known and have been appended to the end of the NSMutableArray .
The Question
How can I rearrange all the points within the array to create a CGPath that looks like the drawing below?
A _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ D
| |
| |
| |
| |
| H _ _ _ I |
| | | |
| | | |
| F _ _ _| | |
| | G | |
| | |_ _ _ K |
| | J | |
| | | |
|_ _ _ _| |_ _ _|
B E L C
Currently I have no trouble creating a CGPath - if I know the order of the CGpoints - by looping through them:
CGPoint firstPoint = [[points objectAtIndex:0] CGPointValue];
CGMutablePathRef path = CGPathCreateMutable();
CGPathMoveToPoint(path, NULL, firstPoint.x, firstPoint.y);
for (int i = 0; i < [points count]; i++)
{
CGPathAddLineToPoint(path, NULL, [[points objectAtIndex:i] CGPointValue].x, [[points objectAtIndex:i] CGPointValue].y);
}
CGPathCloseSubpath(path);
... but this assumes that a line should be drawn from each point in the array i to the following point i + 1 . In the drawing above, lines would have to be drawn from A → B , B → E , E → F ... K → L , L → C , C → D . If E is not after B and C is not after L in the array (which they won't be), then this obviously won't draw correctly.
More Information
CGPoints should share an x or y coordinate with the CGPoint before and after them. Other Possible Layouts
A _ _ _ _ _ _ _ K P _ _ _ D
| | | |
| | | |
| | N _ _ _| |
| | | O |
| |_ _ _| |
| L M |
| |
| F _ _ _ G |
| | | |
| | |_ _ _ I |
| | H | |
| | | |
|_ _ _ _ _ _ _| |_ _ _|
B E J C
A _ _ _ _ _ _ _ _ _ _ M
| |
| |
| |_ _ _ _ _ _ O
| N |
| H _ _ _ I |
| | | |
| | | |
| F _ _ _| | |
| | G | |
| | |_ _ _ K |
| | J | |
| | | |
|_ _ _ _| |_ _ _|
B E L C
I think this might do it. I tested it with a couple of sets of numbers and it seemed to work. Basically, I start with the point at index 0 (any starting point should work), add that to the arrangedPoints array and then look for the nearest point with the same y value -- that point is added to arrangedPoints and deleted from the original randomPoints array. I then do the same thing in the x direction and repeat until there's only one point left in the randomPoints array, and add that to the end of arrangedPoints.
-(void)arrangePoints:(NSMutableArray *) randomPoints {
NSMutableArray *arrangedPoints = [NSMutableArray array];
[arrangedPoints addObject:[randomPoints objectAtIndex:0]];
[randomPoints removeObjectAtIndex:0];
while (randomPoints.count > 1) {
//Look for the closest point that has the same y value
int yValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].y;
int xValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].x;
NSIndexSet *indSet = [randomPoints indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop){
return yValueOfknownPoint == [obj CGPointValue].y;
}];
NSLog(@"%d",indSet.count);
if (indSet.count == 1) {
[arrangedPoints addObject:[randomPoints objectAtIndex:indSet.firstIndex]];
[randomPoints removeObjectAtIndex:indSet.firstIndex];
}else{
__block int min = 10000000;
__block int foundIndex;
[indSet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) {
int posibleMin = fabs(xValueOfknownPoint - [[randomPoints objectAtIndex:idx]CGPointValue].x);
if (posibleMin < min) {
min = posibleMin;
foundIndex = idx;
}
}];
[arrangedPoints addObject:[randomPoints objectAtIndex:foundIndex]];
[randomPoints removeObjectAtIndex:foundIndex];
}
//Look for the closest point that has the same x value
xValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].x;
yValueOfknownPoint = [[arrangedPoints lastObject] CGPointValue].y;
indSet = [randomPoints indexesOfObjectsPassingTest:^BOOL(id obj, NSUInteger idx, BOOL *stop){
return xValueOfknownPoint == [obj CGPointValue].x;
}];
if (indSet.count == 1) {
[arrangedPoints addObject:[randomPoints objectAtIndex:indSet.firstIndex]];
[randomPoints removeObjectAtIndex:indSet.firstIndex];
}else{
__block int min = 10000000;
__block int foundIndex;
[indSet enumerateIndexesUsingBlock:^(NSUInteger idx, BOOL *stop) {
int posibleMin = fabs(yValueOfknownPoint - [[randomPoints objectAtIndex:idx]CGPointValue].y);
if (posibleMin < min) {
min = posibleMin;
foundIndex = idx;
}
}];
[arrangedPoints addObject:[randomPoints objectAtIndex:foundIndex]];
[randomPoints removeObjectAtIndex:foundIndex];
}
}
[arrangedPoints addObject:randomPoints.lastObject];
NSLog(@"%@",arrangedPoints);
}
Some added points to address known problems:
To deal with equidistant points like G and M from N, I think I would keep the sets of points separate -- rather than putting every thing into one array, I would keep the original rectangle, and each new set of points that come in separate. Then when I was constructing the paths, I wold only look for point within my own set of points or the original rectangle, but not in any other set of points.
To deal with the problem inwit brought up, of doubling back on itself, I think you would have to determine whether a set of points intersects a side or a corner -- I think only the corner ones would present that problem. You could check for a corner one by seeing that 2 of the points fall on 2 different lines of the original rectangle (rather than on the same line). You would then have to calculate the missing point (a putative point p in your last example above) and see which point of the original rectangle it's identical too, and then delete that point from the path. I think that my algorithm would then work correctly.
Here is one approach (in pseudocode) if all you are interested in is fills and not strokes:
Create an empty mutable path using CGPathCreateMutable() .
Add the original rectangular figure to the mutable path as a closed loop.
One by one, add each of the additional irregular figures to the mutable path, separately, as a closed loop.
Use the function CGContextEOFillPath() to fill the eroded figure using the even-odd fill rule .
The even-odd fill rule is described in the section Filling a Path in the Quartz 2D Programming Guide .
You may also be interested in this
Alright, this may seem a very complicated algorithm (and it is far from optimal), but I'd approach it like this.
1. Find the point(s) with lowest X-value
2. Of those points find point P (using a loop) such that:
- P has a nabour N with the same X-value
- There exists no other point that vertically lies between P and its nabour N with the same Y value
(if no P exists with a nabour, the algorithm has ended, after joining P with its horizontally aligned point)
3. If there exists a point with the same X value as P (horizontally aligned), join that point and P with a line.
4. Now join point P with its nabour N
5. Find all points with the same X-value as N (horizontally aligned)
6. Goto 2
I hope it works (haven't tested it).
链接地址: http://www.djcxy.com/p/61824.html