|
You are probably going to have to live with an imperfect solution. This looks a lot like subset-sum, which iirc is an NP hard problem 
|
|
|
|
|
Hello,
Best Fit problem as applies to computer science involves variable size storage blocks as well as variable size data to be put into the storage blocks notably without combining data chunks before storage (see Knuth, Vol. I).
What you have described is the timeworn knapsack problem, aka circus train problem. Simply stated: What is the packaging arrangement of a fixed set of variably sized objects into uniform size containers that fills the fewest containers?
Problem size will be a considerable obstacle here. Consider unfavorable size distributions in your set of variables that yield many size combinations to be generated, tested, and compared with the previous-best combination. And how many possible combinations of these combinations are possible?
Anyway, I think you should postulate some modest inputs and do some pencil scratch before hunting down code or algorithm.
Tadeusz Westawic
An ounce of Clever is worth a pound of Experience.
|
|
|
|
|
I want to implement an algorithm in which I need to put some nodes(points)in an environment and segments which connect theses nodes in some way to each other. The environment is occupied with some obstacles(simple shapes or polygons)! How can I determine when collision exists between nodes or segments and the environment's obstacles! Thanks so much in advance.
|
|
|
|
|
It depends on the accuracy that you want. For relatively inaccurate detection you can use the bounding box of your shapes.
There are some nice bounding box based algorithms in OpenGL that you can use: here[^].
There's also a nice CP article here[^].
EDIT: It helps to explain why you gave me a '1-vote'...
modified on Tuesday, June 10, 2008 3:30 AM
|
|
|
|
|
The solution requires the use of a spatial container. You place all your environment objects into the container, then as you process your dynamic objects you query them against the spatial container. The result should provide back the intersecting objects. Depending on the dimensionality of the objects you could either use a quad-tree or an oc-tree.
|
|
|
|
|
General process is that you perform a "broad phase" sweep to determine potential collision pairs based on something easy - bounding circles or boxes, and then move onto a "narrow phase" to check for exact collisions.
You might want to read up on minkowski sums - using these in an embedded system at the moment for mining machine anti-collision.
|
|
|
|
|
Non-Numerics R Us, use bitmaps and the GDI Bitblt() function.
Two congruent bitmaps A and B each contain some 'on' bits and some 'off' bits and we wish to determine if any 'on' bits occupy the same coord location in both maps.
1. A AND B yields a bitmap with 'on' bits only where the 'on' bits of A and B collided.
2. Row-wise OR the first half of C with its second half, then the first one fourth with the second one forth, etc. until all rows are ORed to a single row.
3. Repeat step 2, except column-wise for the first row only until ORed to a single bit.
If the upper-left bit is 'on', then a collision occurred.
This method always answers yes or no, but never how many or where. You might ask what use is that?
I have used blitter and bitmaps in (unsuccessful) attempt to simulate fluid flow through a maze by pumping bits into the entrance and sumping them out the exit. My bits just wouldn't flow and I need a better notion of 'boolean soup'.
I have also used this method to successfully determine if constrained random walks in integer 3-space cross one another.
This method boasts a strictly linear increase in execution time as number of objects to test increases. This feature makes it useful for very large numbers of objects like the hundreds of thousands of bits bouncing around in my mazes, keeping track of which are moving N, E, S, W and colliding with each other or with maze walls.
Tadeusz Westawic
An ounce of Clever is worth a pound of Experience.
|
|
|
|
|
Sorry, thats supposed to read....
That is, linear increase in execution time IF you are adding one bitmap per graphic object.
There is ZERO increase in execution time if you work things out to fixed number of bitmaps. Ten bits set or 500,000 bits set in a 1000x1000 bm wil execute in the same amount of time.
Tadeusz Westawic
An ounce of Clever is worth a pound of Experience.
|
|
|
|
|
This is one of those times when I'm not sure I understand the problem well enough to articulate an intelligeable question, so bear with me as I muddle my way through this.
In my application, I have a set of conditions. I need to test these conditions, and if a combination of them results in a true value, then I take one action; otherwise, I take another.
These conditions are really just integer values; the test in my code looks something like this:
flag1 = flag2 = flag3 = false;
for(int i = 0; i < OscillatorCount; i++)
{
for(int j = 0; j < TargetCount; j++)
{
if(oscillatorSource[i][j] == Envelope1)
{
flag1 = true;
}
else if(oscillatorSource[i][j] == Envelope2)
{
flag2 = true;
}
else if(oscillatorSource[i][j] == Envelope3)
{
flag3 = true;
}
}
}
In other words, I have a two-dimensional table. If any of the values in the table matches a certain value, I set a flag to true. So in the future when I need to take an action based on the values in the table, I can simply do this:
if(flag1)
{
}
if(flag2)
{
}
if(flag3)
{
}
What it seems like I'm doing is answering questions about a two-dimensional table and putting the answers into one-dimensional values, i.e. the boolean flags.
Are there algorithms for this sort of thing?
|
|
|
|
|
Seems OK, but I suggest using an enum with the Flags attribute rather than three boolean values.
|
|
|
|
|
Hi everybody,
is there any formula and algorithm to calculate the distance between two points
on the earth using mercator coordinates (x,y) instead of WGS coordinates (Lat, lon)?
Many thanks.
Michela
|
|
|
|
|
Because of uniform grid size, for coordinate pairs between C and U verticals you can use euclidean distance taking into account the correct vertical and horizontal offsets. Outside of those ranges you have to maintain a list of width/height to accurately calculate intersected distance over those grids. There is a paper about UTM by a guy called Redfern, has some interesting notes.
|
|
|
|
|
michela wrote: is there any formula and algorithm to calculate the distance between two points
on the earth using mercator coordinates (x,y) instead of WGS coordinates (Lat, lon)?
Why on earth (heh) would you want distances to be calculated in Mercator coordinates? 
Since it's a conformal cylindrical projection, the metric (i.e. distance between two points) will be awfully messy to calculate. It's much simpler to convert the coords and do the calculation that way.
|
|
|
|
|
|
I know that converting it on lat lon would result in a much simpler
way to do this!!! Unfortunately I have my Mercator coordinates and
I cannot convert tham back to WGS (also due to computational speed
issues) so I was looking for a formula who allows calculating distance
using only Mercator coordinates...
|
|
|
|
|
michela wrote: I have my Mercator coordinates and
I cannot convert tham back to WGS
Besides speed issues (although I can't imagine why the conversion would cause a speed issue ) why can't you convert them? It's a trivial calculation that can't possibly be CPU intense. I'm sure the calculation time is on the order of milliseconds or less. See here[^].
Doing the calculation in Mercator coords will require a look-up table of ratios and certainly require more calculation time than converting the coords. Furthermore, the distance calculation in Mercator units will not be a simple computation...
EDIT: if you're going to vote me a '1', at least give some reason as to why my answer was no good.
modified on Sunday, June 8, 2008 2:48 PM
|
|
|
|
|
Also having a table of ratio would be better than converting to WGS
and then using Vincenty formula to calculate distance between two points.
Do you know if there is any way to calculate these ratio factors?
Thanks.
|
|
|
|
|
michela wrote: Also having a table of ratio would be better than converting to WGS
Not only would the calculation be slower, it would also be difficult to implement and would produce inaccurate results.
michela wrote: Do you know if there is any way to calculate these ratio factors?
I am sure there is, but it is more difficult and less accurate than just converting to x,y...
|
|
|
|
|
How would I measure the 'entropic value'1 of a salt token added to a password before hashing with SHA-256? Should I be more concerned with the length of the salt, or its composition?
1 I just made up that term. Please feel free to enlighten me regarding the correct term.
Semicolons: The number one seller of ostomy bags world wide. - dan neely
|
|
|
|
|
Information entropy in a very general and oversimplified definition relates to compressibility of a sequence when the source is unknown.
When generating salt one assumes the source is random, hence the salt should have an entropy of 1. The length is not taken into account. If the salt is the result of a pattern or other known means then it will have a low entropy, something limiting to 0.
The end result is the entropy of the salt is of very little relevance when using a "decent" MD such as the one you have suggested, when hashing passwords.
|
|
|
|
|
Fascinating, thanks. I'd actually like to know more about this, so could you please suggest some online resources for a noob like me?
So am I correct in guessing that if the entropy is 1, a sequence cannot be decompressed at all, and at 0, it can always be decompressed?
Semicolons: The number one seller of ostomy bags world wide. - dan neely
|
|
|
|
|
Does anyone know the algorithm behind Windows Update, and other auto-update mechanisms?
Does the client browse a list of available updates on the server, or does the server receive an inventory from the client, and then the server decides what updates are to be applied?
“Cannot find REALITY.SYS...Universe Halted.”
~ God on phone with Microsoft Customer Support
|
|
|
|
|
I don't know about the windows update, but an online game server that I know checks a file in game folder, where some paramters are written by the update. If the parameters don't pass the test, the launcher ask you to make an update, and gives a shortcut to the updater. But it is not "auto", it requieres user confirmation. But if it is not updated, it may avoid the server connection (depending on what the new update changes)
Greetings.
--------
M.D.V. 
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
“The First Rule of Program Optimization: Don't do it. The Second Rule of Program Optimization (for experts only!): Don't do it yet.” - Michael A. Jackson
Rating helpfull answers is nice, but saying thanks can be even nicer.
|
|
|
|
|
I'm looking for some code that determines from a series of
2D points, whether the points draw a:
- ellipse
- line
- rect
- polygon
if none of the above then just a assume a free form polyline. If the
function determines a ellipse, line or rect, then return a rect for
the bounds. Doesn't have to be super accurate, as it's for a demo program.
¡El diablo está en mis pantalones! ¡Mire, mire!
Real Mentats use only 100% pure, unfooled around with Sapho Juice(tm)!
SELECT * FROM User WHERE Clue > 0
0 rows returned
Save an Orange - Use the VCF!
VCF Blog
|
|
|
|
|
Assuming the ellipse, rectangle and line will be made from points ordered uniformly around their 'perimeter'...
If they represent...
1) An ellipse: the distances from the geometric centre to each point will be linearly distributed... ie: the average distance from the centre should be within an epsilon amount to half way between the maximum and minimum distances.
2) A line: take any two points and calculate the 'linear line equation' y=mx+c... then see if all other points fit the equation.
3) A rectangle: the points would fit into four 'linear line equations', one for each side; find a pair of points that at least one other points fits into, repeat with the remaining points until four sides have been found and there are no points left. (This is the hardest of the three... there may be a better way).
4) A polygon... if none of the other conditions apply.
Calculating the bounding rectangle is simple... look for maximum/minimum points in both the vertical/horizontal directions.
I believe I've done something like this before... I'll see if I can find some code.
Hope this helps.
Matthew Butler
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
!! That hit the funny bone 
