|
Hi,
I have millions of 3D line segments. Each segment is denoted by a point at a each end. One line segment would be v1, v4 (where v1 and v4 are x,y,z). If multiple lines radiate out from one point there will be multiple lines for that point (theoretical v1 could have an infinite number of lines radiating out). There is no ordering in the assignment of x,y,z to points or in the number of points- both are random. There may be 2 or more line segments which form a continuous straight line (v1, v4, v17, vn). I want to find those longer lines and have a single segment replace the multiple segments (v1, v4, v17, vn results in v1, vn). I have been experimenting with the dot product (a result of 1 or -1 is a straight line) and it works. I also have processor and memory issues (neither unlimited) and a time constraint. My question, is there a more efficient way to search for the line segments which form a straight lines (lose the square root) and is there a way to search for line segments radiating from a point (currently I have O^2, unacceptable). Thanks in advance for any help.
-- modified at 12:29 Monday 26th November, 2007
I have developed an efficient routine for finding if line segments are straight continuations of previous lines. Wondering if anyone knows of a search which can be done in a reasonable time frame?
this thing looks like it was written by an epileptic ferret
Dave Kreskowiak
|
|
|
|
|
If there is a bound on the x, y, and z coordinates, then you could do an O(n) sort on all the endpoints. Otherwise, just use a sortedDictionary structure to keep the hash of the endpoints (combine the values of x, y, and z to produce h such that x, y, and z can be retrieved by only knowing h) and a list of indices where that endpoint is contained. Then searching for all line segments "radiating" from the endpoint is easy. This will NOT work, however, for lines that contain other lines but have different endpoints. For example, I think your goal is to combine the lines <0,0,0> to <2,2,2> with <1,1,1> to <3,3,3> to form the line <0,0,0> to <3,3,3>. This is a non-trivial computation, and you will have to solve a system of equations to find out if these two lines can be combined.
Jeff
|
|
|
|
|
I did give a hash some thought, was worried about the size. I have not looked at sortedDictionary, will do so thanks.
I am leaning towards an endpoint ordering. Concern with that approach is the time to form the line. Aren't modern machines supposed to remove this time/memory problem with lots of each.
The original data contains no 'lines with in lines' each segment is unique. Using your example the lines would be <0,0,0> to <1,1,1> and <1,1,1> to <2,2,2> and <2,2,2> to <3,3,3> resulting in a line of <0,0,0> to <3,3,3>. The overlap from your example is not possible in the data set I am working with, if it does occur there was an error beyond my control.
this thing looks like it was written by an epileptic ferret
Dave Kreskowiak
|
|
|
|
|
Then just do what I suggested before, and use sorted dictionary to automatically sort the endpoints for you. You don't even have to use a hash if the class "Point3D" implements IComparable and IEquatable (you can just use the point directly as the key). It would be something like this...
public class Point3D : IComparable<Point3D>, IEquatable<Point3D> {
// this class must implement VALUE comparison (NOT REFERENCE!)
}
public class LineSegment {
public Point3D EndPoint1 { get; }
public Point3D EndPoint2 { get; }
public Vector Slope { get; }
}
public class SomeOther {
List<LineSegment> m_LineSegments = ...; // populate field
SortedDictionary<Point3D, IList<int>> m_EndPoints;
public void AddEndpoint(Point3D pt, int i) {
if (!m_EndPoints.ContainsKey(pt))
m_EndPoints.Add(pt, new List<int>());
m_EndPoints[pt].Add(i);
}
public void CombineLineSegments() {
m_EndPoints = new SortedDictionary<Point3D, IList<int>>(m_LineSegments.Count);
Point3D pt;
for (int i = m_LineSegments.Count - 1; i >= 0; --i) {
AddEndpoint(m_LineSegments[i].EndPoint1, i);
AddEndpoint(m_LineSegments[i].EndPoint2, i);
}
List<int[]> segsToCombine = new List<int[]>();
// Now iterate through the list of endpoints, checking each segment
// for direction coming out of that point. If direction matches, add
// the indices for those vectors to the segsToCombine list
// Finally, combine the segments found to be combinable.
}
}
Jeff
|
|
|
|
|
Thanks for the help. Sorry for the late reply, I have been out of the office for a couple of days.
Jim
this thing looks like it was written by an epileptic ferret
Dave Kreskowiak
|
|
|
|
|
jimwawar wrote: lose the square root
where is the sqrt coming from?
Luc Pattyn [Forum Guidelines] [My Articles]
this months 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
|
|
|
|
|
sqrt was coming in the dot product calculation. The vector was being calculated from the two end points.
The length of the line segment needs to be brought to unit length before the dot product will result in the angle between the two lines. So to bring vector <a,b,c> to unit form length = sqrt(a*a + b*b + c*c) unit form is .
this thing looks like it was written by an epileptic ferret
Dave Kreskowiak
|
|
|
|
|
Can't you live with just the square of length, skipping the sqrt all together?
Furthermore, you're looking for a zero angle, that should be inexpensive.
In two dimensions, I don't think I need any length:
the line defined by points (x1,y1) and (x2,y2)
may connect to the line defined by points (x3,y3) and (x4,y4) if:
- the two lines have the same orientation and origin
- the end points of the line segments are such that they touch or overlap
orientation and origin can easily be tested based on the line's equation:
(y - y1) * (x2 - x1) = (x - x1) * (y2 - y1)
so this equation must hold for x=x3,y=y3 as well as for x=x4,y=y4
Adding a third dimension adds one more equation (say with z and x)
Hope this helps.
Luc Pattyn [Forum Guidelines] [My Articles]
this months 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
|
|
|
|
|
Luc Pattyn wrote: Hope this helps.
It does, thanks
this thing looks like it was written by an epileptic ferret
Dave Kreskowiak
|
|
|
|
|
I have a master page and there is a tree view control there and this is one of the treenodes.
TreeNode _Del = new TreeNode();
_Del.Text = "Administrator";
_Del.NavigateUrl = "~\\Form1.aspx";
TreeNode _Del1 = new TreeNode();
_Del1.Text = "Manager";
_Del1.NavigateUrl = "~\\Form1.aspx";
There is a Form1 and the form1 has two panels. If treenode corresponding to _Del is clicked, panel1.visible=true, panel2.visible=false
and if _Del1 is clicked, panel1.visible=false, panel2.visible=true
Question: How do I get which treenode am clicking in the Form1?
Is response.redirect querystring the only option?
Please help and if the post is not clear, please mention. I can more clearly tell you.
Thanks
|
|
|
|
|
ss.mmm wrote: TreeNode _Del = new TreeNode();
_Del.Text = "Administrator";
_Del.NavigateUrl = "~\\Form1.aspx";
as you are navigating to the same URL, so quick fix is to add a parameter in the URL like:
<br />
_Del.NavigateUrl = "~\\Form1.aspx?node=1";<br />
<br />
and <br />
<br />
_Del1.NavigateUrl = "~\\Form1.aspx?node=2";
and in the code you can show and hide the panels based on node.
-----
|
|
|
|
|
Bad news I know. Does this extend to altering the Tag property on a control too though? I'm stuck in a .NET 1.1 environment (God, give me strength....) so I don't get any helpful exceptions showing me the way.
Regards,
Rob Philpott.
|
|
|
|
|
Hi
As far as i know the cross thread exceptions came up with .net 2.0 so theory says you should be able to change a property of a control from a non-gui thread in 1.x.
but.
as in .net 2.0, 1.1 has the property invokeRequired too. so you can do the same as in 2.0 with Control.Invoke(....)
greets
m@u
|
|
|
|
|
Hey, thanks for the reply.
I know the exceptions were introduced in 2.0, but the rule certainly appied before that. The problem is most the time you'd get away with it, but on occasion it would go wrong so they decided to enforce it in version 2.
Regards,
Rob Philpott.
|
|
|
|
|
Ok then i'm lucky i think i still have some (very..) old code that does that ugly cross-thread thing without invoke..
anyway.. you said you don't get a meaningful exception. do you get an exception at all or does the app just hang?
|
|
|
|
|
Hi,
a thread that did not create a Control, should not access that Control, except for the
very few members explicitly allowed, including InvokeRequired and Invoke (but not Tag).
Before .NET 2.0 the app may behave badly, the GUI may freeze, anything can go wrong if
you violate the rule.
Since 2.0 you get an InvalidOperationException by default; you can disable that by setting
Control.CheckForIllegalCrossThreadCalls false, but that is a very bad idea, and it brings
you back in the previous situation.
Since most if not all Controls are somehow related (they are on a Form, one Form owns
another Form, etc), the natural consequence is all Controls get created and accessed
exclusively by a single thread, typically your initial or main thread, often also called
the "GUI thread".
There are lots of examples on InvokeRequired/Invoke available everywhere;
a rather advanced article on the subject is here[^].
Luc Pattyn [Forum Guidelines] [My Articles]
this months 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
|
|
|
|
|
I am trying to insert data into excel, i usually have no problems, i only have one specific problem:
If the Column Header is named "Job#" the Insert satement fails because it says it can't find column Job#. i have tried everything i can think of to get the # escaped so it doesn't think its a special character. I am using the OLEDB provider to insert with the excel Jet object. Anyone have any advice?????
Thanls
Marios
|
|
|
|
|
Try using (char)35 - I have sometimes found this can work in the sort of situation you are describing.
Regards
Guy
You always pass failure on the way to success.
|
|
|
|
|
No that doesn't work
Thanks
Marios
|
|
|
|
|
Try enclosing the column names into brackets. e.g. INSERT INTO table ([Job#],....
Regards
Aftab Sindhi
.NET Application Developer
U.A.E
|
|
|
|
|
Hi guys let me start by a code exemple 
public Array Maproriete1
{
get { return Maproriete; }
}
how can I make may Array values in readOnly so that i can't modify them.
thanks!!
|
|
|
|
|
You can't like that. Either provide a method, say, GetMapOriete(int index) to return an element or you might considering cloning the array and returning that. Although not exactly read-only, it wouldn't affect your copy.
Regards,
Rob Philpott.
|
|
|
|
|
If you don't mind returning a List (instead of an Array), you could return a ReadOnly version of the collection.
public IList<string> Names {
get {
return new _names.AsReadonly();
}
}
private List<string> _names = new List<string>();/ravi
|
|
|
|
|
how to read particular data from xml file
|
|
|
|
|
well you can load the xml document in dataset using dataset.ReadXML or you can load the xml document using xmldocument.load and then read the data using xpath or best thing is to google it[^]
-----
|
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
