List of surrounding points
-
I have a list of
System.Drawing.Point, e.g. selected pixels in a bitmap. Now I'd like to get a list of points which are nearby, say less than 10 pixels (simply the sum of distances in x and y direction) away from the former points. When the number of points is small, that's easy. But when more than 1000 pixels are selected, the performance becomes important. Can you suggest some algorithms for this task? Currently, I use a simple method:public static IReadOnlyList GetSurroundingCloud(this IEnumerable _points, int _maximumDistance)
{
ISet result = new HashSet();
foreach (Point p in _points)
{
for (int x = 0; x <= _maximumDistance; x++)
{
for (int y = 0; y + x <= _maximumDistance; y++)
{
result.Add(new Point(p.X - x, p.Y - y));
result.Add(new Point(p.X - x, p.Y + y));
result.Add(new Point(p.X + x, p.Y - y));
result.Add(new Point(p.X + x, p.Y + y));
}
}
}
return result.ToList();
}As you can see, there are some features which won't scale well: - the iteration over the input list (though O(n) could be acceptable) - the loops with maximumDistance parameter - O(n^2) with that parameter - HashSet.Add - the larger the list gets, the more points it has to look up for preventing duplicates, so something like O(n^2) or worse.
Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
Trigonometry to the rescue! You can use Pythagorean theorem to calculate the hypotenuse which is basically the length from one point to another. Hypotenuse - Wikipedia[^] The trick to make it efficient is to avoid using the Square Root function. Basically...
10 > sqrt(x^2 + y^2)
is a lot slower to calculate than
10^2 > x^2 + y^2
As some bonus trivia I found the Fast inverse square root - Wikipedia[^] really fascinating:
-
I have a list of
System.Drawing.Point, e.g. selected pixels in a bitmap. Now I'd like to get a list of points which are nearby, say less than 10 pixels (simply the sum of distances in x and y direction) away from the former points. When the number of points is small, that's easy. But when more than 1000 pixels are selected, the performance becomes important. Can you suggest some algorithms for this task? Currently, I use a simple method:public static IReadOnlyList GetSurroundingCloud(this IEnumerable _points, int _maximumDistance)
{
ISet result = new HashSet();
foreach (Point p in _points)
{
for (int x = 0; x <= _maximumDistance; x++)
{
for (int y = 0; y + x <= _maximumDistance; y++)
{
result.Add(new Point(p.X - x, p.Y - y));
result.Add(new Point(p.X - x, p.Y + y));
result.Add(new Point(p.X + x, p.Y - y));
result.Add(new Point(p.X + x, p.Y + y));
}
}
}
return result.ToList();
}As you can see, there are some features which won't scale well: - the iteration over the input list (though O(n) could be acceptable) - the loops with maximumDistance parameter - O(n^2) with that parameter - HashSet.Add - the larger the list gets, the more points it has to look up for preventing duplicates, so something like O(n^2) or worse.
Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
[C# System.Drawing.Point - Coding Horrors - GameDev.net](https://www.gamedev.net/forums/topic/667763-c-systemdrawingpoint/) Use your own structs or lists of "primitives"; e.g. ints or longs that translate to coordinates.
"(I) am amazed to see myself here rather than there ... now rather than then". ― Blaise Pascal
-
Trigonometry to the rescue! You can use Pythagorean theorem to calculate the hypotenuse which is basically the length from one point to another. Hypotenuse - Wikipedia[^] The trick to make it efficient is to avoid using the Square Root function. Basically...
10 > sqrt(x^2 + y^2)
is a lot slower to calculate than
10^2 > x^2 + y^2
As some bonus trivia I found the Fast inverse square root - Wikipedia[^] really fascinating:
Thanks, Dar, but that's not the thing I am looking for. For the purpose of getting that list of points surrounding a given list of points, the sum of x and y will just do for the distance. It is the generation of the list which I think of.
Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
-
I have a list of
System.Drawing.Point, e.g. selected pixels in a bitmap. Now I'd like to get a list of points which are nearby, say less than 10 pixels (simply the sum of distances in x and y direction) away from the former points. When the number of points is small, that's easy. But when more than 1000 pixels are selected, the performance becomes important. Can you suggest some algorithms for this task? Currently, I use a simple method:public static IReadOnlyList GetSurroundingCloud(this IEnumerable _points, int _maximumDistance)
{
ISet result = new HashSet();
foreach (Point p in _points)
{
for (int x = 0; x <= _maximumDistance; x++)
{
for (int y = 0; y + x <= _maximumDistance; y++)
{
result.Add(new Point(p.X - x, p.Y - y));
result.Add(new Point(p.X - x, p.Y + y));
result.Add(new Point(p.X + x, p.Y - y));
result.Add(new Point(p.X + x, p.Y + y));
}
}
}
return result.ToList();
}As you can see, there are some features which won't scale well: - the iteration over the input list (though O(n) could be acceptable) - the loops with maximumDistance parameter - O(n^2) with that parameter - HashSet.Add - the larger the list gets, the more points it has to look up for preventing duplicates, so something like O(n^2) or worse.
Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
Analytical Geometry to the rescue! Given point (X0, Y0), return all points (X, Y) such that |X - X0| + |Y - Y0| <= R. For the row Y == Y0, this is trivially all the points (X, Y0), X0 - R <= X <= X0 + R. For the rows Y == Y0+/-1, this is trivially all the points (X, Y0+/-1), X0 - R + 1 <= X <= X0 + R - 1. For the rows Y == Y0+/-n, this is trivially all the points (X, Y0+/-n), X0 - R + n <= X <= X0 + R - n. And for Y == Y0+/-R, this is trivially the points (X0, Y0+/-R). No coordinates are explicitly calculated, and no point is visited more than once. Note that this approach would work for the more conventional distance, as well. Use [Bresenham's circle-drawing algorithm](https://www.geeksforgeeks.org/bresenhams-circle-drawing-algorithm/) to calculate the end-points of each row.
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows. -- 6079 Smith W.
-
I have a list of
System.Drawing.Point, e.g. selected pixels in a bitmap. Now I'd like to get a list of points which are nearby, say less than 10 pixels (simply the sum of distances in x and y direction) away from the former points. When the number of points is small, that's easy. But when more than 1000 pixels are selected, the performance becomes important. Can you suggest some algorithms for this task? Currently, I use a simple method:public static IReadOnlyList GetSurroundingCloud(this IEnumerable _points, int _maximumDistance)
{
ISet result = new HashSet();
foreach (Point p in _points)
{
for (int x = 0; x <= _maximumDistance; x++)
{
for (int y = 0; y + x <= _maximumDistance; y++)
{
result.Add(new Point(p.X - x, p.Y - y));
result.Add(new Point(p.X - x, p.Y + y));
result.Add(new Point(p.X + x, p.Y - y));
result.Add(new Point(p.X + x, p.Y + y));
}
}
}
return result.ToList();
}As you can see, there are some features which won't scale well: - the iteration over the input list (though O(n) could be acceptable) - the loops with maximumDistance parameter - O(n^2) with that parameter - HashSet.Add - the larger the list gets, the more points it has to look up for preventing duplicates, so something like O(n^2) or worse.
Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
@bhiller Without some 'unsafe voodoo, I don't see any way but "brute force;" in this example, I chose to generate a set of rectangles:
public static IEnumerable GetNearbyPoints(int maxDist, List points, int nRows, int nColumns)
{
int x, y, w, h;
int half = maxDist / 2;List rects = new List(); for (int i = 0; i < points.Count(); i++) { Point pt = points\[i\]; x = pt.X; y = pt.Y; if (x < 0) x = 0; w = maxDist; if (x + half > nColumns) { w = nColumns - x; } if (y < 0) y = 0; h = maxDist; if (y + half > nRows) { h = nRows - y; } yield return (new Rectangle(x,y,w,h)); }}
«Where is the Life we have lost in living? Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information?» T. S. Elliot
-
[C# System.Drawing.Point - Coding Horrors - GameDev.net](https://www.gamedev.net/forums/topic/667763-c-systemdrawingpoint/) Use your own structs or lists of "primitives"; e.g. ints or longs that translate to coordinates.
"(I) am amazed to see myself here rather than there ... now rather than then". ― Blaise Pascal
The problem with using 'structs in this case would be their mutability will require you to update your list with the new copy of the struct created by modifying it.
«Where is the Life we have lost in living? Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information?» T. S. Elliot
-
@bhiller Without some 'unsafe voodoo, I don't see any way but "brute force;" in this example, I chose to generate a set of rectangles:
public static IEnumerable GetNearbyPoints(int maxDist, List points, int nRows, int nColumns)
{
int x, y, w, h;
int half = maxDist / 2;List rects = new List(); for (int i = 0; i < points.Count(); i++) { Point pt = points\[i\]; x = pt.X; y = pt.Y; if (x < 0) x = 0; w = maxDist; if (x + half > nColumns) { w = nColumns - x; } if (y < 0) y = 0; h = maxDist; if (y + half > nRows) { h = nRows - y; } yield return (new Rectangle(x,y,w,h)); }}
«Where is the Life we have lost in living? Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information?» T. S. Elliot
Thanks, Bill. That could pave the way to a solution. I really need some kind of "List" of those points - IEnumerable is necessary, Count would be nice, mutability is not required at all. That "list" will be used as a parameter in further calculations. So, a solution could be: - create a rectangle enclosing all original points (that's O(n) for number of points) - create a 2-dimensional array of bool, and map those points (i.e. x and y of the point become indices of the array, and there the value is set to true) - create a 2-dimensional array of bool for the result. It's bigger, and the size can easily be determined. - either - - iterate over all result array and find out if a point of the original array can be reached - - iterate over the original array and mark all points which can be reached in the result array. In contrast to the HashSet implementation, there is no need to check for duplicates: it does not matter if an item already true is set to true again. - re-map the array to a List of Point That should be O(n) for the number of original points (which is my main concern), but stil O(n^2) for the distance (which is a configurable value, and should not vary to much).
Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
-
Thanks, Bill. That could pave the way to a solution. I really need some kind of "List" of those points - IEnumerable is necessary, Count would be nice, mutability is not required at all. That "list" will be used as a parameter in further calculations. So, a solution could be: - create a rectangle enclosing all original points (that's O(n) for number of points) - create a 2-dimensional array of bool, and map those points (i.e. x and y of the point become indices of the array, and there the value is set to true) - create a 2-dimensional array of bool for the result. It's bigger, and the size can easily be determined. - either - - iterate over all result array and find out if a point of the original array can be reached - - iterate over the original array and mark all points which can be reached in the result array. In contrast to the HashSet implementation, there is no need to check for duplicates: it does not matter if an item already true is set to true again. - re-map the array to a List of Point That should be O(n) for the number of original points (which is my main concern), but stil O(n^2) for the distance (which is a configurable value, and should not vary to much).
Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
off the top of my head: from the IEnumerable<Rectangle>
public static IEnumerable RectanglesToPoints(IEnumerable rects)
{
return rects.Select(r => RectToPoints(r)).SelectMany(pt => pt);
}public static IEnumerable RectToPoints(Rectangle rect)
{
for (int i = rect.X; i < rect.Width + rect.X; i++)
{
for (int j = rect.Y; j < rect.Height + rect.Y; j++)
{
yield return new Point(i,j);
}
}
}I suspect there's a better way; is there something about when you need to go from IEnumerable to List, or other, that is critical here ?
«Where is the Life we have lost in living? Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information?» T. S. Elliot
-
off the top of my head: from the IEnumerable<Rectangle>
public static IEnumerable RectanglesToPoints(IEnumerable rects)
{
return rects.Select(r => RectToPoints(r)).SelectMany(pt => pt);
}public static IEnumerable RectToPoints(Rectangle rect)
{
for (int i = rect.X; i < rect.Width + rect.X; i++)
{
for (int j = rect.Y; j < rect.Height + rect.Y; j++)
{
yield return new Point(i,j);
}
}
}I suspect there's a better way; is there something about when you need to go from IEnumerable to List, or other, that is critical here ?
«Where is the Life we have lost in living? Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information?» T. S. Elliot
Thanks for your input. I think I could have enough information now to improve the original solution (don't need to do it now, but I am sure I'll have to do it some when later). Regarding your latest code, there a two points to consider: the resulting list will be used in a few places. So I'd have to do a
ToListorToArraycall to prevent the Linq statement from being executed multiple times. That's an easy fix. Also, when I need the amount of points in the resulting list, it should be free of duplicates. A call toDistinctinRectanglesToPointsshould do the trick easily again.Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
-
Thanks for your input. I think I could have enough information now to improve the original solution (don't need to do it now, but I am sure I'll have to do it some when later). Regarding your latest code, there a two points to consider: the resulting list will be used in a few places. So I'd have to do a
ToListorToArraycall to prevent the Linq statement from being executed multiple times. That's an easy fix. Also, when I need the amount of points in the resulting list, it should be free of duplicates. A call toDistinctinRectanglesToPointsshould do the trick easily again.Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
Hi Bernhard, It was fun to think about this. I was puzzling over the issue of duplication, since two rectangles could overlap, without being identical. My only thought was to generate the full list of points, and call 'Distinct on that: I tried to ignore the thought of graphic paths that could represent rectangles with chunks taken out of them :) cheers, Bill
«Where is the Life we have lost in living? Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information?» T. S. Elliot
-
Hi Bernhard, It was fun to think about this. I was puzzling over the issue of duplication, since two rectangles could overlap, without being identical. My only thought was to generate the full list of points, and call 'Distinct on that: I tried to ignore the thought of graphic paths that could represent rectangles with chunks taken out of them :) cheers, Bill
«Where is the Life we have lost in living? Where is the wisdom we have lost in knowledge? Where is the knowledge we have lost in information?» T. S. Elliot
BillWoodruff wrote:
It was fun to think about this.
That's also my motivation for reading questions / articles / discussions on CodeProject. Nice to hear that I could provide an interesting topic. :)
Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!