|
Hmmm, that's an interesting problem.
I'm not even sure how to go about drawing the bounding box, or if such a thing really exists in a spherical coordinate system. A few quick sketches show up all sorts of problems in defining the shape - is it a square (with curved edges), or some distorted shape with non-parallel sides? What happens near the poles, or if a pole is inside your circle? I can even end up with a 3-sided "box" in some cases.
I'm afraid I'll have to think a bit more about this one, and get back to you later...
There are three kinds of people in the world - those who can count and those who can't...
|
|
|
|
|
I've been having a bit more of a think about this, and I'm not sure there is a valid concept of a bounding box for a circle on a sphere - or not a simple one anyway.
Working in Lat/Long coordinates, there are a number of problem areas. If you define the "sides" of the box as the meridians at centre+radius and centre-radius Long, and the top and bottom as the similarly defined parallels of Latitude, you can get a "box" of sorts provided the circle is reasonably small, and not near or at either of the poles.
If the circle contains a pole, then the sides actually cross inside the circle, and the top or bottom may also intersect it. If the circle is centred on the pole, then there is no way to define a box at all.
Also, if the circle is a great circle around a meridian, then the circle itself is the box (with only two sides and no vertices)!
Going for an alternative approach, the bounding box could be defined as the intersections of four great circles. Each is defined as the great circle tangent to a particular point on your circle's circumference, with those points spaced at 90 degrees around it. This should define a box independently of any Lat/Long coordinate system, and will only have one degenerate case of the test circle being a great circle. Although if the first point is chosen to be at the "top" of the circle, it will, I think, be similar to the Lat/Long aligned one.
I'm not sure how to calculate the coordinates of the vertices of this new "box", or why you would want them, but it has made me think a lot about spherical geometry, and I might even write a quicky visualiser to look at this in more detail.
What does the "box" represent? What about other bounding shapes - hexagons, octagons? What can we say about limits, areas, volumes? Lots of questions, which have nothing to do with navigation, but are very interesting...
Cheers, and thanks for exercising my brain 
There are three kinds of people in the world - those who can count and those who can't...
|
|
|
|
|
Isn't this just Haversine formula:
R = earth’s radius (mean radius = 6,371km)
Δlat = lat2− lat1
Δlong = long2− long1
a = sin²(Δlat/2) + cos(lat1).cos(lat2).sin²(Δlong/2)
c = 2.atan2(√a, √(1−a))
d = R.c
So obviously:
θ = atan2( sin(Δlong).cos(lat2), cos(lat1).sin(lat2) − sin(lat1).cos(lat2).cos(Δlong) )
No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced.
This message is made of fully recyclable Zeros and Ones
|
|
|
|
|
Yes that true but i do not have lat2 and long2.I have to calculate these with some very valid assumption of angle.
|
|
|
|
|
Have a look at
"http://williams.best.vwh.net/avform.htm"
|
|
|
|
|
If I understand the problem correctly, you have a point on a sphere and a great circle distance, this defines a circle C. You are interested in the extremes of lat/long on that circle.
At the original point, take the normal N. This normal is also normal to the plane containing C.
If you project C onto the plane through the equator Pe you will in general get an ellipse. The minor axis of the ellipse will be the projection of N onto the plane Pe, and the major axis perpendicular to this. You should be able to do some 2D geometry to find the extremes of longitude in this plane.
Similarly, projecting C onto a plane through the poles gives another ellipse that you can use to find the extremities of latitude.
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."
|
|
|
|
|
On his blog, Roger Alsing describes a very interesting program. I wonder if it can be improved....?
Here you can find a file with Dan Bystrom’s improvements [to the EvoLisa program], plus an additional improvement (using uints instead of doubles when the fitness drops below 3/4 of uint.MaxValue). I added an additional feature which could be implemented. It allows an interlaced subset of the pixels to be tested for fitness. I also included an open-source C program I found on the Internet that generates fast random numbers, but that would not help improve the program much speed-wise due to other bottlenecks in the system, so I did not implement it. Right now the renderer seems to be the major bottleneck in the code. You may want to try using System.Windows.Shapes.Polygon instead of System.Graphics for the polygons, since then each polygon could be rerendered at will individually. Right now, rendering is the major bottleneck in the code after the updates are applied (Around 350 renders occur per second on my computer, whereas 3,500 mutates or 1,750 fitness evaluations can occur in the same time period [I tested that by commenting out code temporarily and counting to ten while the algorithm was running. The margin of error was around 10%, which is negligible in this case]). By the way, I think that using uints instead of doubles was the 60% improvement that Dan was talking about, although the improvement would be more along the lines of 3X if the Renderer was faster.
The question is, how can I implement this? (I am a high-school student who has recently begun programming, and I consider myself to be a novice-intermediate programmer). Could anyone optimize that code with all of this in mind? The key is to use System.Windows.Shapes.Polygon so only one polygon would usually need to be rendered per generation (maybe two or three, but certainly not all of them as is required now). Before you ask, NO, THIS IS NOT A HOMEWORK ASSIGNMENT!!!
|
|
|
|
|
' MAIN()
'
' Entry point. No more PPd. & Add. (^800 = 5)
'
'^:MAIN
MAIN:
'^PR^! Retract form in printer.
PRINT CMD("PR");
'^PL66^! Set line count to 66 for this form.
PRINT CMD("PL66");
'^PN^! Normal print mode on.
PRINT CMD("PN")
'^:GET.TERMS
GET.TERMS:
'^?"BOL ENTER TERMS (1 - 4): 1. PREPAID 2. COLLECT 3. 3RD PARTY 4. COD"1"1""%d"800
'A%=VAL(INPUTBOX$("BOL ENTER TERMS (1 - 4): 1. PREPAID 2. COLLECT 3. 3RD PARTY 4.COD",1,"1"))
A%=3
'^OC(^800 < 1)(^GT GET.TERMS)
'^OC(^800 > 4)(^GT GET.TERMS)
IF (A%<1) OR (A%>4) THEN GOTO GET.TERMS
'^H
'
' Goto line 2
'^G2
PRINT CMD("G4");
'
' DATE, ORIGIN, DESTINATION
'
PRINT CMD("C50");CMD("D");STRING$(4," "); K$ ; STRING$(6," "); STRJUST$(FLD(14,0),3,"L"," ")
'GOTO ENDING
'
' Skip a line
'
PRINT
'PRINT
'
' Shippers acct Number
PRINT STRING$(20," "); L$
'
'
PRINT
PRINT
'
PRINT STRING$(2," "); CMD("YL");CMD("7");CMD("YB")
PRINT STRING$(2," "); CMD("YL");CMD("8");CMD("YB")
PRINT STRING$(2," "); CMD("YL");CMD("9");CMD("YB"); STRING$(32," "); CMD("PB"); "HAWB#: ";STRJUST$(FLD(10,0),18, "L", " ");CMD("Pb")
PRINT STRING$(2," "); " "
'
PRINT STRING$(2," "); " ";STRING$(20," "); M$
PRINT STRING$(2," ");STRIP$(FLD(40,0),"C", " ")
'
'
'Skip 4 lines
'
PRINT
PRINT
PRINT
PRINT
'
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("2"),"C"," ");CMD("YB")
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("3"),"C"," ");CMD("YB")
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("4"),"C"," ");CMD("YB")
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("14"),"C"," ");CMD("YB")
'PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("5"),"C"," ");", ";STRIP$(CMD("6"),"C"," ");" ";STRIP$(CMD("7"),"C"," ");CMD("YB")
PRINT STRING$(2," ");CMD("YL");STRIP$(CMD("5"),"C"," ");CMD("YB")
'PRINT
PRINT STRING$(2," ");CMD("YL");STRJUST$(FLD(10,2),18,"L"," ");CMD("YB"); STRING$(2," "); STRIP$(FLD(8,2),"C"," ")
'PRINT STRING$(2," ");
' PO (13chars) / BOL #
PRINT STRING$(2," ");STRJUST$(FLD(40,0),20,"L"," "); STRING$(1," "); STRJUST$(FLD(9,0), 16, "L"," ");
'PRINT STRING$(2," ");STRJUST$(FLD(9,0),13,"L"," "); STRING$(1," "); STRJUST$(FLD(2,0), 16, "L"," ")
'
|
|
|
|
|
Looks like old fashioned basic to me.
No trees were harmed in the sending of this message; however, a significant number of electrons were slightly inconvenienced.
This message is made of fully recyclable Zeros and Ones
|
|
|
|
|
I have 3 or more persons and they each have 3 or more schedules, how do i get all unique combination against each other.
if you have 3 person and they all have 3 schedules each it should be 27 different combinations but how do i program this.
If possible example code in VB.net or C#.net
Example P = Person, S = Schedule:
P1 S1 P2 S1 P3 S1
P1 S2 P2 S1 P3 S1
P1 S3 P2 S1 P3 S1
P1 S1 P2 S2 P3 S1
P1 S1 P2 S3 P3 S1
P1 S1 P2 S1 P3 S2
P1 S1 P2 S1 P3 S3
P1 S2 P2 S2 P3 S1
P1 S2 P2 S3 P3 S1
ETC ETC
|
|
|
|
|
Hi,
no code, just an approach:
if you were to use a ternary number representation (i.e. digits 0, 1, and 2; and digit weights that are powers of 3), then each combination could be written as a number, and incrementing such number would yield the next combination, so you would get 000, 001, 002, 010, 011, 012, 020, 021, 022, 100, ... 222
|
|
|
|
|
But if they have 15 schedules each then it wont be easy to solve it in that way or ??
Plus sometime the persons have different numbers of schedules.
|
|
|
|
|
the same principles apply:
1. if all persons have N schedules, use base=N notation and increment the number;
2. if all persons have different numbers of schedules, use an inhomogeneous base (each digit now has as weight the product of all numbers of schedules to the right of it, somewhat harder to implement)
|
|
|
|
|
using System;
using System.IO;
namespace Schedule
{
class Program
{
static void Main(string[] args)
{
GetThreeSchedules("schedule3.txt", 7, 6, 10);
GetFiveSchedules("schedule5.txt", 2, 3, 4, 1, 6);
}
public static void GetThreeSchedules(string filename, int one, int two, int three)
{
for (int a = 1; a <= one; a++)
{
for (int b = 1; b <= two; b++)
{
for (int c = 1; c <= three; c++)
{
File.AppendAllText(filename, "P1 S" + a + " P2 S" + b + " P3 S" + c + "\r\n");
}
}
}
}
public static void GetFiveSchedules(string filename, int one, int two, int three, int four, int five)
{
for (int a = 1; a <= one; a++)
{
for (int b = 1; b <= two; b++)
{
for (int c = 1; c <= three; c++)
{
for (int d = 1; d <= four; d++)
{
for (int e = 1; e <= five; e++)
{
File.AppendAllText(filename, "P1 S" + a + " P2 S" + b + " P3 S" + c + " P4 S" + d + " P5 S" + e + "\r\n");
}
}
}
}
}
}
}
}
Here is some code. I do not know how to generalize it further, though.
|
|
|
|
|
take this, if you have N persons and they all have a collection of schedules (0 .... N), how would you solve it dynamically so to speak. I mean your example works fine if it is a fixed nr of persons and schedules but thats not the case here.
Person 1 has 3 schedules
Person 2 has 2 schedules
Person 3 has 4 schedules
Person 4 has 3 schedules
etc etc etc up to Person N
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication2
{
class Program
{
static void Main(string[] args)
{
Person person1 = new Person(3);
Person person2 = new Person(2);
Person person3 = new Person(4);
Person person4 = new Person(3);
// code - write to file all unique combinations
}
}
class Person
{
public static int counter = 0;
public int Id;
public List<int> schedules = new List<int>();
public Person(int nrOfSchedules)
{
Id = counter++;
// create schedules for person
for (int i = 0; i < nrOfSchedules ; i++)
{
// think each object in the collection as an schedule id
schedules.Add(i);
}
}
}
}
|
|
|
|
|
I already gave you most of the solution.
the number of combinations N equals the product of the individual number of schedules.
so you need a loop from 0 to N-1
|
|
|
|
|
I understand the solution but i've worked with it for a couple of days now and i can't implement it to code.
|
|
|
|
|
Hi,
something along these lines:
int persons=3;
int[] max=new int[] {4,2,3};
int prod=1;
for (int p=0; p< persons; p++) prod*=max[p];
for (int comb=0; comb< prod; comb++) {
int val=comb;
string s="";
for (int p=persons-1; p>=0; p--) {
int maxp=max[p];
int mod=val%maxp;
s=mod.ToString()+" "+s;
val=val/maxp;
}
Console.WriteLine(s);
}
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
modified on Monday, May 11, 2009 8:57 AM
|
|
|
|
|
Thanks for the example but i cant run the code.
i think something is wrong on you first for-loop.
|
|
|
|
|
HTML monster in action again.
fixed.
Luc Pattyn [Forum Guidelines] [My Articles]
The quality and detail of your question reflects on the effectiveness of the help you are likely to get.
Show formatted code inside PRE tags, and give clear symptoms when describing a problem.
|
|
|
|
|
Thank you it worked fine
|
|
|
|
|
I needed something similar and came across this[^]. However, at 13 elements or more, it fails due to 13!. I still have not found anything perfect.
|
|
|
|
|
Hi,
Can somebody tell me an algorithm to determine if the set of points form a concave or convex Polygon.I want to code it to use for commercial purpose
Thanks
|
|
|
|
|
Hi,
this should do it:
- take one edge (two consecutive points) of the polygon
- find its equation in the form f(x,y) = a*x + b*y + c = 0
(there is one freedom left, a scale factor in each of the coefficients)
- now feed each of the other points in the f(x,y) function; all the results need to have the same sign for the poly to be convex.
- repeat for each edge.
There may be simpler, I am not aware of it though.
|
|
|
|
|
Luc's suggestions is nearly there, but:
1. You should use the orientation predicate (sign of the 3 point determinant (0,+,-)), instead of the half-plane equation.
2. Instead of testing each edge against each other point (via half-plain which btw shouldn't work), what you do is test the orientation of the next point of polygon against the current edege.
3. if the orientation is the same as the previously calculated orientation, or if the orientation is zero and the point is not in the AABB of the current edge then continue onto next edge, if any of those conditions fail for the current edge assume conconcave polygon and break from loop.
This should have a time complexity of O(n).
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
