Re: Line Segments - C# Discussion Boards

26-Nov-07 5:13

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

Skippums26-Nov-07 7:03

Skippums

26-Nov-07 7:03

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

Jim Warburton26-Nov-07 8:10

26-Nov-07 8:10

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

Skippums26-Nov-07 9:56

Skippums

26-Nov-07 9:56

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

Jim Warburton29-Nov-07 4:23

29-Nov-07 4:23

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

Luc Pattyn26-Nov-07 7:10

Luc Pattyn

26-Nov-07 7:10

jimwawar wrote:
lose the square root

where is the sqrt coming from?

Smile | :)

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

Jim Warburton26-Nov-07 7:57

this thing looks like it was written by an epileptic ferret
Dave Kreskowiak

26-Nov-07 7:57

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 .

Luc Pattyn26-Nov-07 8:32

Luc Pattyn

26-Nov-07 8:32

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]

Jim Warburton26-Nov-07 8:59

How to know which tree view node on master page is clicked on the form level

26-Nov-07 8:59

Luc Pattyn wrote:
Hope this helps.

It does, thanks

this thing looks like it was written by an epileptic ferret
Dave Kreskowiak

ss.mmm26-Nov-07 5:09

ss.mmm

26-Nov-07 5:09

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

Re: How to know which tree view node on master page is clicked on the form level

SABhatti26-Nov-07 8:53

SABhatti

26-Nov-07 8:53

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.

-----

Updating controls from non-gui thread.

Rob Philpott26-Nov-07 5:09

Rob Philpott

26-Nov-07 5:09

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.

m@u26-Nov-07 5:21

m@u

26-Nov-07 5:21

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

Rob Philpott26-Nov-07 5:25

Rob Philpott

26-Nov-07 5:25

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.

m@u26-Nov-07 5:38

m@u

26-Nov-07 5:38

Ok then i'm lucky Smile | :)

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?