|
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<Point> GetSurroundingCloud(this IEnumerable<Point> _points, int _maximumDistance)
{
ISet<Point> result = new HashSet<Point>();
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!
modified 5-Nov-18 3:50am.
|
|
|
|
|
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!
|
|
|
|
|
|
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
|
|
|
|
|
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 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.
|
|
|
|
|
@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<Rectangle> GetNearbyPoints(int maxDist, List<Point> points, int nRows, int nColumns)
{
int x, y, w, h;
int half = maxDist / 2;
List<Rectangle> rects = new List<Rectangle>();
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!
|
|
|
|
|
off the top of my head: from the IEnumerable<Rectangle>
public static IEnumerable<Point> RectanglesToPoints(IEnumerable<Rectangle> rects)
{
return rects.Select(r => RectToPoints(r)).SelectMany(pt => pt);
}
public static IEnumerable<Point> 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 ToList or ToArray call 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 to Distinct in RectanglesToPoints should 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
|
|
|
|
|
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!
|
|
|
|
|
I need help with a program for a match stick game between the computer and a user. program should ensure that the computer always wins.
Rules for the game are as follows :
•There are 21 match –stick
•The computer asks the player to pick 1,2,3 sticks.
•The computer starts first.
•After the person pick, the computer does is picking.
•Whoever is forced to pick up the last stick win the game.
|
|
|
|
|
We do not do your homework: it is set for a reason. It is there so that you think about what you have been told, and try to understand it. It is also there so that your tutor can identify areas where you are weak, and focus more attention on remedial action.
Try it yourself, you may find it is not as difficult as you think!
If you meet a specific problem, then please ask about that and we will do our best to help. But we aren't going to do it all for you!
Sent from my Amstrad PC 1640
Never throw anything away, Griff
Bad command or file name. Bad, bad command! Sit! Stay! Staaaay...
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Computers take instructions very literal.
Computer picks 1 stick. 20 left.
User picks 1 stick. 19 left.
Computer picks 2 sticks. 17 left.
User picks 2 sticks. 15 left.
Computer picks 3 sticks. 12 left.
User picks 3 sticks. 9 left.
Everyone wins.
Bastard Programmer from Hell 
If you can't read my code, try converting it here[^]
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
class Program
{
static void Main(string[] args)
{
Console.WriteLine("I win!");
Console.ReadLine();
}
}
|
|
|
|
|
I have Pdf template with some background design and logo, so we need to pass the data dynamically in to that pdf template using "itextsharp" library. So when we pass the data to the template, it’s overriding the template backgroud design and showing the plain text that we have passed to the
Template instead of merging with the Template.
Any ideas or suggestions to achieve the functionality would be appreciated.
|
|
|
|
|
With so little information it is impossible to guess what your code is doing. Please edit your question and add some proper detail.
|
|
|
|
|
I have written a program the has numerous methods in form1.cs file and it has become somewhat difficult to manage because of its length. Is there a way to move some of these methods to a separate file? If so, what are the mechanics of linking the together? Or is there another approach to manage long programs?
JBD
|
|
|
|
|
To me a good sign of "good practice" would be that someone else reading your code would have some clear ideas about its structure, and what it does, just by looking at the use of namespaces, classes, method names. variable names.
This is a very broad question, and it may well relate to bigger-picture issues in object-oriented design (OOD). Do you know about SOLID, a coherent set of ideas for OOD [^] ?
In WinForms, you can declare a Class as 'partial to get around the restriction on having a single Class definition across multiple files [^].
Other ways commonly used to group Methods, where the Method has no dependencies, include writing Extension Methods in a static Class [^].
Of course, you can also group Methods into a library, compile that to a .dll, load that into your project, and reference the assembly in your Class' code ... as long as those methods have no innate dependency on your app's run-time objects, declarations, etc.
«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
|
|
|
|
|
just a quick correction: It's not WinForms that defines partial classes, but the languages of C# and VB do. You don't need a WinForms project to make use of the feature.
|
|
|
|
|
Thanks, Josh !
«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
|
|
|
|
|
When someone starts programming, the first concepts he's learning are "procedural" concepts, i.e. how to control the program flow (if...else, for, do...while etc).
Another concept is "object orientation". Now you have to think of "encapsulation of data" (how to access them, and more important how to change them safely), and eventually of components and their interactions.
Bill mentioned SOLID: those are 5 ways for creating components and having them interact. "S" stands for "single responsibility" and is a good point to start with: a class takes care of one thing only, a function in that class of one action only.
This change in paradigm from mere procedural code to object oriented code is a big step.
Oh sanctissimi Wilhelmus, Theodorus, et Fredericus!
|
|
|
|
|
I have successfully used the InPlaceBitmapMetadataWriter to write Keywords to many photos taken by many cameras, including when I need to extend the metdata padding. However for photos taken by recent cameras the TrySave method always returns false for Keywords. Does anyone know why this might be and how I might solve this?
private bool UpdateMetadataInPlace()
{
bool traySaveSuccessful = false;
string tempPath = PutTogetherTemporaryFilePath();
if (File.Exists(tempPath))
{
File.Delete(tempPath);
}
File.Copy(imageFilePath, tempPath);
using (Stream jpgFileStream = File.Open(tempPath, FileMode.Open, FileAccess.ReadWrite))
{
BitmapDecoder jpgDecoder = BitmapDecoder.Create(jpgFileStream, BitmapCreateOptions.None, BitmapCacheOption.None);
if (jpgDecoder.Frames[0] != null && jpgDecoder.Frames[0].Metadata != null)
{
InPlaceBitmapMetadataWriter metadataJpgWriter = jpgDecoder.Frames[0].CreateInPlaceBitmapMetadataWriter();
metadataJpgWriter.SetQuery("System.Keywords", Keywords.ToArray());
if (metadataJpgWriter.TrySave())
{
traySaveSuccessful = true;
}
}
}
if (traySaveSuccessful == true)
{
File.Delete(imageFilePath);
File.Move(tempPath, imageFilePath);
}
else
{
File.Delete(tempPath);
}
return traySaveSuccessful;
}
modified 29-Oct-18 14:12pm.
|
|
|
|
|
Whenever my application loses focus, the scrolling of a panel is reset to the top position once focus is regained. This is really annoying. I have tried everything I can think of and researched to fix this such as overriding the scroll mechanism and saving coordinates; also doing the same during a mouse wheel scroll and trying to restore with the following method:
private void OnFormActivated(object sender, EventArgs e)
{
panel1.AutoScrollPosition = panelRect.Location;
}
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
