|
I am trying to find an algorithm, or actual code if available, to find the intersection point of a Great Circle line and a straight line. Even though this is on a sphere, the earth, I want to consider the straight line as basically tunneling through the earth and not following the curvature of the earth. Basically I want to find the point where a Great Circle line passes some "line in the sand". I have searched for an algorithm for this but have not been able to find anything. Please help me Obi Wan Kenobe, you're my only hope.
Kalvin
|
|
|
|
|
Hi,
there is no algorithm involved, just a little algebra, with a system of two equations (line and
sphere) to solve. What do you know about the line? What is your coordinate system?
If you can't solve it in three dimensions, try the similar question in two dimensions first.
Luc Pattyn [Forum Guidelines] [My Articles]
This month's tips:
- before you ask a question here, search CodeProject, then Google;
- the quality and detail of your question reflects on the effectiveness of the help you are likely to get;
- use PRE tags to preserve formatting when showing multi-line code snippets.
|
|
|
|
|
Thank you for the reply.
When it comes to math I am at a disadvantage. My lines are defined by lat/lon values for the end points of both lines. I know the equation for a straight line is y=mx+b. I can plug in lat/lon for y and x since lat/lon are in decimal degrees. I have not been able to find an equation for the Great Circle line, not one I understand anyway.
|
|
|
|
|
Why don't you follow Luc suggestion and try first in two dimensions?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
[my articles]
|
|
|
|
|
That's a great idea. Since the great circle is on a sphere, could I use an arc in 2D for this? Any idea what the equation of a Great Circle line is?
I really appreciate the help. I have been looking at this for days and am getting nowhere. All the equations I find have to do with finding the distance or heading for a Great Circle line. I don't need either one of those.
Kalvin
|
|
|
|
|
Well, I think that we have too few details of your problem. For instance do you mean a 3D generic line? Moreover, what Great Circle? Have you considered that a sphere has infinite (with power two, if I'm not wrong) Great Circles?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
[my articles]
|
|
|
|
|
I couldn't pass this by without a comment. Two points on a sphere (except the endpoints of a diameter) can have one and only one great circle pass through them. The two points and the center of the sphere define a plane, and this plane intersects the sphere in one great circle.
What you are referring to, I think, is that two points in space can have an infinite number of circles pass through them, bounded, of course. The smallest circle is the one whose diameter is the line defined by the two points. The infinity starts there, a different circle for every increase in size, and these circles are just tangent to the two points. The additional infinities are the rotation of any of the circles around the line thus forming a torus. The interesting point is that these two sets of infinities are a distinct set of circles than those created by changing the end points of the same line, (a lower bound for the smallest circle and all such circles are distinct from the initial set, even if the same diameter, because the center is at a different place). Same thing for a different line (two different points not on the same line).
As to the initial question, I do have the equations to solve this, but this bring up analytical geometry and vector methods. I could elaborate if anyone is interested.
Dave Augustine
|
|
|
|
|
Member 4194593 wrote: I couldn't pass this by without a comment. Two points on a sphere (except the endpoints of a diameter) can have one and only one great circle pass through them. The two points and the center of the sphere define a plane, and this plane intersects the sphere in one great circle.
Sphere has infinite power two Great Circles, if you fix two points, it is strighforward that you end up with no degrees of freedom, i.e. one Great Circle.
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
If you read the authors second post, it was stated that both lines were defined by lat/lon values, thus only one great circle.
Dave Augustine.
|
|
|
|
|
Member 4194593 wrote: both lines
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
This is going on my arrogant assumptions. You may have a superb reason why I'm completely wrong.
-- Iain Clarke
|
|
|
|
|
Hi every body.
Can any body help me plz
I have a task that requires to read the text on a image
My requirement is
I take a image of a vehicle number plate through a web cam or a usb camera.
Now when i get the image when i click a button i should get the numberplate number into a text box I need this functionality using c#,vb.net plz help me i am doing my B.tech final year project, I would be very much thank full if any one will help me
thanks in advance
with regards
harivinod
|
|
|
|
|
|
You posted your question in 4 different forums huh? How rude. Read the forum rules. All this time you spent cross-posting, and waiting for someone to reply, you could have done research to get the answeres yourself.
I'm going to become rich when I create a device that allows me to punch people in the face over the internet.
"If an Indian asked a programming question in the forest, would it still be urgent?" - John Simmons / outlaw programmer
|
|
|
|
|
Awww, geeze. OP posted here, too
"I guess it's what separates the professionals from the drag and drop, girly wirly, namby pamby, wishy washy, can't code for crap types." - Pete O'Hanlon
|
|
|
|
|
I am attempting to come up with an algorythm for ranking players in a multiplayer game. The ELO system (used in Chess et-al) does not seem to fit as that is geared towards head-to-head games and im dealing with a variable player-number multiplayer game.
I basically have 4 (possibly 5) "statistics" that I can capture about a players history. I may want to weight some of those statistics more than others.
Can anyone start me off on how to proceed?
|
|
|
|
|
What about MS TrueSkill?
If the Lord God Almighty had consulted me before embarking upon the Creation, I would have recommended something simpler.
-- Alfonso the Wise, 13th Century King of Castile.
[my articles]
|
|
|
|
|
I think more information about the game is needed to come up with an appropriate algorithm, in particular how the variable number of players influences the outcome.
|
|
|
|
|
It's a tricky problem.
It's tempting to add the statistics together but then you'll find players exploiting the system by finding a technique for gaining huge levels in 1 stat.
The next thought is to multiply the scores together as that would require a broader based approach where players do a bit of everything. This unfortunately stops specialist players from gaining many points.
Often in multiplayer games you find that the guy who is running round helping his team mates or coordinating the efforts of his team is providing the most valuable service of anyone but will never get points for his actions. It's a very hard thing to determine a score and normally the people who care most about their individual score are the people you least want playing.
Even giving people points based on their team's performance is a risky ploy as you'll have people switching sides to improve their rankings.
Is there a way you could give people a score based on their teams improvement since they joined? That would then rank them according to the value they add through their presence.
Russell
|
|
|
|
|
It is indeed tricky.
I should point out that this is not a team-based game. Essentially everyone plays versus everyone else.
|
|
|
|
|
In which case I would record your scores in each of the 5 or six categories. At the end of a game rate your playing as you see fit from 1 to 5. If you have friends whos opinions you trust with a different style of play but who are none the less worthy opponents in your eyes then get them to do the same.
You may find that one of the metrics correlates very well against the subjective scores given by the players. In this case that's what you should mainly base your scores on. Otherwise you need to get some kind of statistical analysis of the results to work out what the correct balance of each of the points is. Or use some kind of very basic weighted network and try to get a best fit between the inputs and the ratings you have given yourselves.
Russell
|
|
|
|
|
Okay -- you have a PvP game in which you can gather several statistics.
First you may want to incorporate some additional stats under the covers that cannot be seen. For example -- time between deaths, kills between deaths, etc.
Now part of you weighting will be number of players participating at given times within the game.
Finally you would have your standard stats which everyone can see (total kills, hit accuracy, etc.)
You will have a bell curve for you weighting system. Too few or too many players and the stats are badly stacked. But in the sweet spot you would gain the highest scoring.
At the end of a match (assuming this is timed matches) you would first compute the weighting factor based on number of players against the bell curve * (time between death / factor ) * ( kills between death / factor ) -- or some such formulae as that.
Now take your weighting factor and apply it to the sum of your key stats * each stat weight factor.
This way when you hit the sweet spot a player who lives a long time, kills many people during that time, and has a high chance of being killed (the number of players playing without a ripe field of fodder) will get a higher ranking than a player that finds someplace to hide and only nails a few players.
Just my opinion.
|
|
|
|
|
I need to find what the closest point is for each of a series of points with 2 dimensional coordinates. To give a real world example say you took a picture of the stars at night and you wanted to find what star appears to be closest to each star when you look at them (this is not the real application just an example).
Obviously the easy way to do this would be to find the distance from every point to every other point and then sort the differences but this could be very slow if there is alot of points since the number of comparisons would increase exponentially. I have a few ideas on quicker ways to do this but I wanted to make sure I'm not overlooking some existing algorithm that would be good for this problem. Actually I'm not even sure what the name of this problem is (if it has one). If anyone knows the name or knows of some existing algorithms it would be a big help.
Thanks,
Mike
|
|
|
|
|
Someone may know about established algorithms, but one way to go would be to organise the 'star' co-ordinates in boxes on a grid. This way you would only have to search a small number of boxes dependent on the co-ordinates of each variable point and the nearest point found in each box. If you have variable densities of 'stars' then you could nest your boxes in some areas.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Unfortunately, Peter, this is not sufficient. Even comparing the smallest distance between any of the stars in all of the grid boxes may miss the case where a star in one grid box is immediately adjacent to another star in another grid box. You also need to make a quick comparison at the end inside a narrow band that spans the grid lines, the width of the band being the smallest distance between two stars found thus far.
Many, many optimizations also need to be done in the algorithm to avoid expensive calculations. With 9100 6.5 magnitude stars, about 4500 should be visible from any point on earth. O(n) of 4500 is about 10,125,000, and that is a lot of calculations.
What I was concerned with, is not that these were stars (~4500), but (as stated) this is an analogy for... Maybe the real problem was one in physics where the points were atoms in some condensate and numbered in the billions and the distance was to determine attractions.
Dave Augustine.
|
|
|
|
|
Member 4194593 wrote: Even comparing the smallest distance between any of the stars in all of the grid boxes may miss the case where a star in one grid box is immediately adjacent to another star in another grid box
That's why I said in my post that you would only have to search a small number of grid boxes - not just one.
I haven't thought about it much, but one way to start would be to search it's own box first, and if a star is found that is closer than any boundary then you are finished, otherwise you have to search any box that intersects the sphere to the nearest star you have found.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|