1

I have an array of CGPoints (well, actually NSStrings as CGPoints).

I have a separate point called CGPoint nextPoint.

How would I find out which CGPoint, in my array, is the closest to nextPoint?

Will
  • 147
  • 1
  • 10

2 Answers2

3

Have you considered simply iterating through your array and finding the distance between all the points?

You could store the distance in a new NSMutableArray and then grab the smallest value from it.

Community
  • 1
  • 1
brandonscript
  • 68,675
  • 32
  • 163
  • 220
1

Just iterate and calculate like Pythagoras and compare the results.

sqrt( ( exp( x1 - x2, 2) + exp( y1 - y2, 2 ) ) );

You might want to check if CGFloat is a float or a double and use the float versions of these functions if appropriate. There is a macro that defines this.

if (CGFLOAT_IS_DOUBLE == YES) {

If YES, then use the above, if NO, then use the function versions that end with f

If your set of points to compare is large enough you need to do it faster you could try various means of finding the shortest distance in subsets of your points in parallel then comparing the result of those operations.

uchuugaka
  • 12,679
  • 6
  • 37
  • 55
  • 1
    ... or just don't waste time doing the sqrt(). And I would avoid using exp() instead use direct multiplication. You don't need the actual distance, just something that compares relatively. – Jeff Laing May 19 '14 at 04:12
  • Oh, yeah. I see what you mean. Just leverage the value of the (x1 - x2)^2 + (y1 - y2)^2 ? What's the argument against using exp() ? Is there some small difference on instructions performed? These can be great tips, but I'd say it's worth a comment in the code. Actually writing out pythagorean formulas has a chance of being recognized. – uchuugaka May 19 '14 at 04:31
  • Hardware multiplication is orders of magnitude faster than exponentiation. Even if they have special cased for "power=2", you are still going to take a load more computation on-board. If you are concerned about typos, use #define SQUARED(x) ((x)*(x)) and then you'll be able to write SQUARED(x1-x2)+SQUARED(y1-y2) The compiler will still optimise all the repetition away – Jeff Laing May 20 '14 at 21:14
  • How fast does it need to be? is what you propose really better than what math.h provides? Who's to say what the compiler might do anyway? If you can measure a performance impact that poses enough concern then it's worth optimizing. Otherwise it's better to do more interesting things. – uchuugaka May 20 '14 at 23:42
  • Well, yes, what I propose is better than what math.h provides. And if you read any book on graphic engines, you will find the same suggestion. Every CPU cycle you do not spend doing computations you do not need is increased battery life. If you are doing one search, then who cares - but if you are searching repeatedly through hundreds or thousands of objects, it may make a difference. Then again, as you say, if its not interesting, don't worry about it. – Jeff Laing May 23 '14 at 09:43
  • Any book suggestions there? – uchuugaka May 23 '14 at 11:34
  • It depends on what you want to do. Last time I looked, "3D Game Engine Design" by Dave Eberly was pretty good on algorithms, but its probably not suited to GIS Analysis. – Jeff Laing May 27 '14 at 02:46
  • Since the actual distance isn't needed and just used for comparisons, the ^2 could probably be skipped as well. Probably increases readability more than any computations that might be saved. So abs(x1-x2) + abs(y1-y2). I tested this in a game I'm building and it works fine. – Derek Hewitt Jul 29 '14 at 07:04