|
I've sometimes wondered this very thing myself, and done some experiments, but unfortunately the shape I suspect you're after isn't really well defined.
One approach I used to generate a bitmap of the "skeleton" was to draw text repeatedly using increasing stroke widths, adding to the skeleton any island of pixels which disappeared from one iteration to the next. This was slow, but it somewhat worked; the results were used to generate an HPGL file for an engraving machine (the goal was to engrave the entire interiors of letters, but I wanted the engraver to follow the contours of the letters so the tooling marks would look good).
One slight caveat is that for decent results it's necessary to draw the fonts using miter joins, but some fonts have acute angles which look very bad (the joins either stick out way too far, or else they're converted to bevel joins which are way too short). This can be fixed somewhat by adding a very short extra stroke to acute joins, perpendicular to the bisector of the two lines being joined. This will generate a bevel whose distance from the intersection will be half the stroke width.
|
|
|
|
|
Hey all,
I have written a designer (similar to class designer) in WPF and am looking to build a diagram layout algorithm such as orthogonal routing algorithm. However I was wondering if there is an open implementation available that one can use. In any ways are there any obvious algorithms that you guys can think of (I can imagine a variation of dijkstra's shortest path algorithm).
Thanks in advance,
Ashish
Ashish Kaila
|
|
|
|
|
|
I don't understand why Dijkstra's alogorith is restricted only to positive costs . It does seem to do a good job no matter what .. Can anyone tell me why do we have that restriction or give me an example that fails with negative costs ?
Thank you !
|
|
|
|
|
Well… I visit your website first time and found this site very useful and interesting! Well… you guys doing nice work and I just want to say that keep rocking and keep it up!!!!
Mark Alter
interview questions
|
|
|
|
|
..pay for it, you must. I voted for a "remove"
I are troll
|
|
|
|
|
Well, this might sound as a weird algorithm discussion, it's a theoretical one, although I wouldn't mind seeing the abstract implementation. Here it is.
In a 2D game, you have a player and enemies in 2D space. A player has ranged attack as PlayerRange and enemies have their own range(s), but let's say they all have the same range of EnemyRange. What I'm interested in is how to separate a cloud of enemies into groups and circle them to death. here is my solution:
First, acquire range between enemies that will be considered as min-max range to be between each other in a group, and separate cloud of enemies into sub-clouds. Once this is done, create convex hull for each of sub-groups and determine closest sub-group player is to. If player is inside any of those, find closest line of the convex hull and follow in direction of normal to it until player is outside the sub-group.
While outside, construct expanded convex hull using PlayerRange and follow it from point to point until convex hull is no more (i.e. has only 2 enemies left). Once it is so, use simple sphere as path to follow around them until they are destroyed.
Now, all this assumes that sub-group and convex hull calculations are done on a per-frame basis, because enemies do move on their own and may merge from one sub-group to another. This raises a question as to which next point to go to. I think a good solution for this would be to choose next counter- or clockwise point around convex hull and go towards it.
What do you think, is this a good way of doing "circling to death" or are there others?
"Do not try. Do"
|
|
|
|
|
Your question isn't very clear, but it appears you want some way to group enemies into clouds to surround them.
One approach is Cluster Analysis. Start with a list of all enemies and a table of the distances among them. Group the two closest enemies into a cluster. The cluster becomes a new "enemy" with a centroid (average X and Y coordinates). Continue grouping enemies until the closest are above some threshold. The clusters of enemies remaining are your compact clouds.
If you have many enemies to group, a KD-tree (http://en.wikipedia.org/wiki/Kd-tree[^]) is efficient for finding nearest neighbors.
|
|
|
|
|
|
IN: vector<POINT>--the complex area Point
OUT:vector<vector<POINT>>--the boundarey of the area,including the out boundary and inside boundary.
bool ConvertInnerToBorder(vector<vector<POINT>>;vector<POINT>)
{
}
|
|
|
|
|
how to scan or know a file was copied to HDD after scaning files over that path file in HDD? i saw this Algorithms in some viruse protection program. how do they do? what Algorithms do they use ?
modified on Friday, May 29, 2009 7:00 AM
|
|
|
|
|
They're not using .NET - seems that Avast! has hooked the FindFiles function. I found the process reading files whenever I opened a virtual DOKAN drive.
What you need is someone who is very familiar with the WinAPI
I are troll
|
|
|
|
|
can u give some link page for about what u said ?
|
|
|
|
|
|
|
|
|
And people supplying the news through Twitter and mobile phones is going to help make it better how? That's too bad. I would like to know what they're talking about though.
|
|
|
|
|
Don't use and have never used Twitter, and at this moment in time, I fail to see the point of Twitter and am not attracted to it. However, I have no idea what the original story exactly was, but, I'll say no more than "Rumours and conjecture manage to twist stories out of all proportion".
modified 1-Aug-19 21:02pm.
|
|
|
|
|
It would be interesting to know if the guy really came to the solution indipendently, though it's not likely.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
Hi,
I have two long (>50000) lists of names that must be periodically checked for possible matches between them. I've coded up several fast algorithms for computing edit distances (Eg- Levenshtein) but the size of the lists still makes it very time costly.
Is there any fast function F(S) that people compute offline on single strings that you could cluster them by, so that two strings far apart in F are also far apart in string distance, and one could reduce the size of the set that must be checked exactly? For example, if my criterion for matching is Leven(s1, s2) < N, then I know that |Length(s1) - Length(s2)| < N, and if I find a length difference >= N I won't even bother running Levenshtein.
I Googled once and came up with suggestions to use Hilbert curves or Z-ordering, and it made my head hurt. But there's gotta be something better than just length...
Thanks a million!
|
|
|
|
|
There's a much simpler solution: Use a hash table.
Insert all strings from the larger list into a hash table with at least twice as many slots as strings. Then check to see if each string from the smaller list is in the hash table.
Hash tables trade space for speed and are very fast. If you want more speed, just increase the number of slots in the table.
|
|
|
|
|
I'm not sure there's a good method if one is seeking to find all strings in one set which are within some Leven distance of any string in another set, unless the only distances of interest are small (preferably one, maybe two).
If the strings in question are names, you could hash each one into an 26-bit integer identifying what letters it contains. If desired, some letters could be ignored, or other letters folded together, so as to yield e.g. a 16-bit integer. If two names are within an edit distance of e.g. 2, then there must be at most two bits different between the names. One could produce a list of all distance-two collisions among the 65,536 different integer hash values. There would be many such collisions, but one might still save some time versus a brute-force comparison of everything.
|
|
|
|
|
As others said, I really think a hash table is the fastest solution to your problem. Not sure if there is some more specific approach for this case.
2+2=5 for very large amounts of 2
(always loved that one hehe!)
|
|
|
|
|
It's unclear. Do you have two lists of names (List<string>)? Or two strings that contain multiple names?
If the former, I'd make one into a HashSet and then see if the members of the other appear in it.
If the latter, I'd Split them and proceed as above.
|
|
|
|