Merge line segments into a single line
Merge line segments into a single line
Merge line segments into a single line
Merge line segments into a single line
Merge line segments into a single line
Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line
Merge line segments into a single line Merge line segments into a single line
Merge line segments into a single line
Go Back  Xtreme Visual Basic Talk > > > Merge line segments into a single line


Reply
 
Thread Tools Display Modes
  #1  
Old 01-02-2014, 04:33 AM
Pointy Pointy is offline
Newcomer
 
Join Date: Dec 2013
Posts: 10
Default Merge line segments into a single line


Hi,

I have a series of line segments (vertex pairs) that need to be converted into a single line. The problem is the segments can be in any order, and have multiple branches. Take the attached picture as an example. (The blue dotted line and circles represent the original segments/vertex). The segments will all share at least one vertex. The segments in the example come in order from A to F, so...

A (vertex 7,4)
B (vertex 1,2)
C (vertex 2,3)
D (vertex 3,4)
E (vertex 6,5)
F (vertex 5,4)

This seems pretty simple, if it were not for branches like segment A.
  1. Find an end segment (Loop through all the segment's and find a vertex that is only used once) , and add both of the segment's vertex to the final line eg. B1,B2
  2. Find the segment which shares the previous segment's 2nd vertex, eg C , and add it's other vertex to the final line eg. C3
  3. Repeat step 2 until all segments processed.

I am not sure how to handle branches, ultimately I need to expand a path outwards from the line as shown by the black line/grey area in the picture. Each segment could have a different expansion amount, although I have drawn them all the same in the example.

Another problem is the fact that a segment can have a curve factor, but I am not worried about this for the time being.

Anyone have a thoughts or suggestions?

Regards,

Les
Attached Images
File Type: png line example.png (22.8 KB, 13 views)
Reply With Quote
  #2  
Old 01-03-2014, 03:33 PM
boops boops's Avatar
boops boops boops boops is offline
Centurion
 
Join Date: Dec 2006
Location: Holland and France
Posts: 146
Default

Hi pointy,
It's not clear what you mean by a "single line" but I suspect that what you need is a GraphicsPath. A path is a combination of lines, curves, text etc. which you can store as a unit. Assuming your vertices are Points or PointFs called v1, v2 etc. you could build the path like this:
Code:
Dim gp As New Drawing2D.GraphicsPath
gp.AddLines(v1, v2, v3, v4)
gp.AddLines(v6, v5, v4)
gp.AddLine(v7, v4)
Note that AddLines with an s adds a "polyline", a series of joined lines. AddLine without the s adds a single straight line with specified end points. You can also add rectangles, ellipses, polygons, Bezier or spline curves, text etc. to a path.

Once you have a graphics path you can handle it as a unit to do things like:
- draw the path with Graphics.DrawPath
- fill closed areas of the path with Graphics.FillPath
- transform the whole path with Translate, Scale and Rotate transforms
- do hit testing on the path with GraphicsPath.IsOutlineVisible
- do hit testing on enclosed areas of the path with GraphicsPath.IsVisible
- save the path to a file or database by serialization.

Does this sound like the kind of thing you are looking for?

BB
Reply With Quote
  #3  
Old 01-04-2014, 04:11 AM
Pointy Pointy is offline
Newcomer
 
Join Date: Dec 2013
Posts: 10
Default

Quote:
Originally Posted by boops boops View Post
Hi pointy,
It's not clear what you mean by a "single line" but I suspect that what you need is a GraphicsPath. A path is a combination of lines, curves, text etc. which you can store as a unit. Assuming your vertices are Points or PointFs called v1, v2 etc. you could build the path like this:
Code:
Dim gp As New Drawing2D.GraphicsPath
gp.AddLines(v1, v2, v3, v4)
gp.AddLines(v6, v5, v4)
gp.AddLine(v7, v4)
Note that AddLines with an s adds a "polyline", a series of joined lines. AddLine without the s adds a single straight line with specified end points. You can also add rectangles, ellipses, polygons, Bezier or spline curves, text etc. to a path.

Once you have a graphics path you can handle it as a unit to do things like:
- draw the path with Graphics.DrawPath
- fill closed areas of the path with Graphics.FillPath
- transform the whole path with Translate, Scale and Rotate transforms
- do hit testing on the path with GraphicsPath.IsOutlineVisible
- do hit testing on enclosed areas of the path with GraphicsPath.IsVisible
- save the path to a file or database by serialization.

Does this sound like the kind of thing you are looking for?

BB
Thanks for taking the time to reply. I will try and make it a little clearer.

I am reading the information from a XML file, here is some sample code...
Code:
<wire x1="6.35" y1="2.54" x2="6.35" y2="8.89" width="0.4064" layer="16"/>
<wire x1="2.54" y1="7.62" x2="2.54" y2="3.81" width="0.4064" layer="16"/>
<wire x1="2.54" y1="3.81" x2="3.81" y2="2.54" width="0.4064" layer="16"/>
<wire x1="3.81" y1="2.54" x2="6.35" y2="2.54" width="0.4064" layer="16"/>
<wire x1="11.43" y1="5.08" x2="8.89" y2="2.54" width="0.4064" layer="16"/>
<wire x1="8.89" y1="2.54" x2="6.35" y2="2.54" width="0.4064" layer="16"/>
The sample above is the data for the blue dotted line in the picture attached to the first post. You can see it consists of line segments that have a start & end point, width & layer. There are other properties as well but for now I am just trying with the simplest case, straight lines of the same width, even the layer part can be ignored for now.

So firstly I just need to draw this info on screen and I am using OpenGL not GDI+. The drawing part itself is no problem. In fact I already have something that draws the files pretty accurately, but it's a real fudge. Lots of overdraw and is probably drawing twice as much as it needs to. Obviously because of this performance is bad.

Secondly, I need to expand a path outwards from the drawn line by a set distance. Think of something like Photoshop Select>Modify>Expand on the original line.

So I suppose what I am after is a list of vertex/points/coords that represent the black outline in the first picture.

This is my thinking so far...
  1. Pick the left hand end point.
  2. Put the points in drawing order, and select point 1. eg. Our sample would be 1,2,3,4,5,6,5,4,7,4,3,2,1
  3. Move out half the width of the line, from the selected point, in a perpendicular angle from the line segment (segment being selected point to selected point+1).
  4. Check for branches and handle them?
  5. Check for end point, draw semi circle & negate offset angle.
  6. Select next point and go to step 3 checking if we are at point 1.

I have seen this referred to as 'path tracing', but searching for it just throws up 3d rendering stuff.

Hope this makes sense.

Regards,

Les
Reply With Quote
  #4  
Old 01-04-2014, 09:12 AM
boops boops's Avatar
boops boops boops boops is offline
Centurion
 
Join Date: Dec 2006
Location: Holland and France
Posts: 146
Default

The GraphicsPath class includes a Widen method to do exactly the kind of drawing you want. Please see the attached image. To produce the image, I built the path from points P1 to P10 like this:
Code:
'at form level:
Private gp As New Drawing2D.GraphicsPath
'in the Load sub:
gp.AddLines({P1, P2, P3, P4, P5, P6}) 'Curly braces needed to make an array argument.
gp.StartFigure 'Start a new branch of the path.
gp.AddCurve({P4, P7, P8, P9, p10}) 'Just showing off :)!
Ignoring OpenGL for the moment, I rendered the path in the Paint event handler of a form like this:
Code:
		e.Graphics.SmoothingMode = Drawing2D.SmoothingMode.HighQuality
               'create a copy of the path for widening:
		Using gp2 As New Drawing2D.GraphicsPath(gp.PathPoints, gp.PathTypes)
                       'Define a pen for widening the the path.
                       'Color is irrelevant but width, end caps and line joins matter.
			Using pn As New Pen(Color.Empty, 30) With _
			 {.StartCap = Drawing2D.LineCap.Round, .EndCap = Drawing2D.LineCap.Round, .LineJoin = Drawing2D.LineJoin.Round}
				gp2.Widen(pn)
                                'Draw and fill the widened path:
				e.Graphics.DrawPath(Pens.Red, gp2)
				e.Graphics.FillPath(Brushes.LightCyan, gp2)
			End Using
		End Using
                'Draw the original path:
		Using pn As New Pen(Color.Blue) With {.DashStyle = Drawing2D.DashStyle.Custom, .DashPattern = {8.0F, 8.0F}}
			e.Graphics.DrawPath(pn, gp)
		End Using
                'Code for rendering points and labels omitted.
If you want the widened path as an array of points for use in OpenGL, that's easy. Create the widened path gp2 as above, then use the array gp2.PathPoints.

One method you might find useful in this connection is the GraphicsPath.Flatten method, which you can use to increase or decrease the density of points along the path, for example:
Code:
gp2.Flatten(Nothing, 0.01)
The first argument (a transform matrix) isn't needed. The smaller the value of the second argument, the closer the points. Then you can treat the whole path as a polygon, which may be faster to render than curves.

BB
Attached Images
File Type: jpg branchingPath.jpg (16.3 KB, 13 views)

Last edited by boops boops; 01-04-2014 at 09:20 AM.
Reply With Quote
  #5  
Old 01-04-2014, 09:36 AM
Pointy Pointy is offline
Newcomer
 
Join Date: Dec 2013
Posts: 10
Default

Quote:
Originally Posted by boops boops View Post
The GraphicsPath class includes a Widen method to do exactly the kind of drawing you want. Please see the attached image. To produce the image, I built the path from points P1 to P10 like this:
Code:
'at form level:
Private gp As New Drawing2D.GraphicsPath
'in the Load sub:
gp.AddLines({P1, P2, P3, P4, P5, P6}) 'Curly braces needed to make an array argument.
gp.StartFigure 'Start a new branch of the path.
gp.AddCurve({P4, P7, P8, P9, p10}) 'Just showing off :)!
Ignoring OpenGL for the moment, I rendered the path in the Paint event handler of a form like this:
Code:
		e.Graphics.SmoothingMode = Drawing2D.SmoothingMode.HighQuality
               'create a copy of the path for widening:
		Using gp2 As New Drawing2D.GraphicsPath(gp.PathPoints, gp.PathTypes)
                       'Define a pen for widening the the path.
                       'Color is irrelevant but width, end caps and line joins matter.
			Using pn As New Pen(Color.Empty, 30) With _
			 {.StartCap = Drawing2D.LineCap.Round, .EndCap = Drawing2D.LineCap.Round, .LineJoin = Drawing2D.LineJoin.Round}
				gp2.Widen(pn)
                                'Draw and fill the widened path:
				e.Graphics.DrawPath(Pens.Red, gp2)
				e.Graphics.FillPath(Brushes.LightCyan, gp2)
			End Using
		End Using
                'Draw the original path:
		Using pn As New Pen(Color.Blue) With {.DashStyle = Drawing2D.DashStyle.Custom, .DashPattern = {8.0F, 8.0F}}
			e.Graphics.DrawPath(pn, gp)
		End Using
                'Code for rendering points and labels omitted.
If you want the widened path as an array of points for use in OpenGL, that's easy. Create the widened path gp2 as above, then use the array gp2.PathPoints.

One method you might find useful in this connection is the GraphicsPath.Flatten method, which you can use to increase or decrease the density of points along the path, for example:
Code:
gp2.Flatten(Nothing, 0.01)
The first argument (a transform matrix) isn't needed. The smaller the value of the second argument, the closer the points. Then you can treat the whole path as a polygon, which may be faster to render than curves.

BB
Great stuff BB!

I never thought of using the system drawing methods to do all the dirty work and then sending the results to OpenGL. I think I need to go play with this.

Regards,

Les
Reply With Quote
  #6  
Old 01-04-2014, 12:20 PM
Pointy Pointy is offline
Newcomer
 
Join Date: Dec 2013
Posts: 10
Default

A quick test has thrown up a hurdle. I don't seem to be able to widen any less than 1.0F. I have a pen width set to 0.01F and it produces the same points from graphicspath.PathPoints as when I have the pen set to 1.0F width.

Maybe I am doing something wrong.

Regards,

Les
Reply With Quote
  #7  
Old 01-05-2014, 04:19 AM
Pointy Pointy is offline
Newcomer
 
Join Date: Dec 2013
Posts: 10
Default

Here's my test code...

Code:
        Dim gpTest As New GraphicsPath
        gpTest.AddLine(25.4, 76.2, 25.4, 38.1) 'Start of path
        gpTest.AddLine(25.4, 38.1, 38.1, 25.4)
        gpTest.AddLine(38.1, 25.4, 63.5, 25.4)
        gpTest.AddLine(63.5, 25.4, 88.9, 25.4)
        gpTest.AddLine(88.9, 25.4, 114.3, 50.8)
        gpTest.StartFigure()
        gpTest.AddLine(63.5, 25.4, 63.5, 88.9) ' branch

        Dim mBmp As Bitmap = New Bitmap(picTest.Width, picTest.Height)
        Dim mPen As New Pen(Color.Empty, 10.0F), mPen2 As New Pen(Color.Red, 0.1F)
        Dim gp2 As New GraphicsPath(gpTest.PathPoints, gpTest.PathTypes)
        mPen.StartCap = LineCap.Round
        mPen.EndCap = LineCap.Round
        mPen.LineJoin = LineJoin.Round
        Using gr As System.Drawing.Graphics = Drawing.Graphics.FromImage(mBmp)
            gr.SmoothingMode = Drawing2D.SmoothingMode.HighQuality
            gp2.Widen(mPen)
            gr.DrawPath(mPen2, gp2)
        End Using
        picTest.Image = mBmp
Firstly I have scaled the real points by 10, otherwise the widen doesn't work.

In the attached picture you can see that it nearly works, but doesn't do the branch properly and also does weird things with the inner angles. The main picture is the OpenGL output and the small part top right is the pictest output from the code above. (As shown by the picture, using the PathPoints property is a great way of doing all the work with System.Drawing and then passing the output to OpenGL)

The not so round end caps in the OpenGL output can be fixed with the flatten method.

Regards,

Les
Attached Images
File Type: png test.png (13.2 KB, 10 views)

Last edited by Pointy; 01-05-2014 at 04:30 AM. Reason: Typos
Reply With Quote
  #8  
Old 02-12-2014, 10:06 PM
boops boops's Avatar
boops boops boops boops is offline
Centurion
 
Join Date: Dec 2006
Location: Holland and France
Posts: 146
Default

Sorry I didn't get round to replying earlier. I don't get notifications of new posts nowadays. Probably I should look into why.

I have since learned that GraphicsPath.Widen doesn't always produce clean results. It looks like I fooled myself in the image I posted by covering up the interior joins and corners with the fill color. At least the colour fill worked well. I have meanwhile tried culling the interior points but that disrupts the order of the path and scrambles it.

One alternative would be to go back to bulding the path geometrically with lines and arcs. It would take some work to generalize it for any set of coordinates, but it should be doable. Another would be to fill the path as in my image, then rebuild a path by "walking" around the outer boundary using the Marching Squares algorithm. I have some code for that tucked away somewhere, so let me know if you are still interested.

BB
Reply With Quote
  #9  
Old 02-13-2014, 01:22 AM
Pointy Pointy is offline
Newcomer
 
Join Date: Dec 2013
Posts: 10
Default

Thanks for replying again.

I did write my own line drawing functions in the end and that part is working really well. I have put this on the back burner for now as I am working on other stuff but from memory I got stuck on how to handle multiple line segment selections.

Regards,

Les
Reply With Quote
  #10  
Old 02-15-2014, 04:02 PM
boops boops's Avatar
boops boops boops boops is offline
Centurion
 
Join Date: Dec 2006
Location: Holland and France
Posts: 146
Default

As a footnote to this thread, I've been looking at WPF and I noticed that the PathGeometry class has a GetOutlinedPathGeometry method to get the outline of a path. I used it to cook up an extension method to get the outline of a Drawing2D GraphicsPath. You can use it in a Winforms project by adding the following references to the dotnet assemblies WindowsBase, PresentationCore and PresentationFramework. Here's the code:
Code:
Imports System.Runtime.CompilerServices
Imports System.Windows.Media

Module GraphicsPathExtensions

	<Extension()> _
	Public Function PathOutline _
  (path As Drawing2D.GraphicsPath, _
  nPoints As Integer) As Drawing2D.GraphicsPath

		If nPoints < 1 Then Throw New ArgumentException _
		("The number of points must be more than 0.")

		'Convert the input path to a collection of System.Windows.Points:
		Dim WPFPoints As New List(Of System.Windows.Point)
		path.Flatten()
		For Each p As System.Drawing.PointF In path.PathPoints
			WPFPoints.Add(New System.Windows.Point(p.X, p.Y))
		Next

		'Create a Geometry and get its outline:
		Dim geom As New PathGeometry
		geom.FillRule = FillRule.Nonzero
		Dim seg As New PolyLineSegment(WPFPoints, False)
		Dim fig As New PathFigure(WPFPoints(0), {seg}, True)
		geom.Figures.Add(fig)
		Dim outline As PathGeometry = geom.GetOutlinedPathGeometry

		'Divide the outline into evenly spaced points:
		Dim DrwngPoints As New List(Of System.Drawing.PointF)
		For i As Integer = 0 To nPoints - 1
			Dim p As System.Windows.Point
			outline.GetPointAtFractionLength(i / nPoints, p, Nothing)
			DrwngPoints.Add(New PointF(CSng(p.X), CSng(p.Y)))
		Next

		'Return the result as a GraphicsPath:
		Dim gp As New Drawing2D.GraphicsPath
		gp.AddPolygon(DrwngPoints.ToArray)
		Return gp

	End Function
End Module
I called the method in your code like this: gp2 = gp2.PathOutline(100). The results were as follows (before above, after below with a slightly thicker pen).

BB
Attached Images
File Type: png path outline.png (4.3 KB, 13 views)
Reply With Quote
Reply


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is Off
HTML code is Off

Forum Jump

Advertisement:





Free Publications
The ASP.NET 2.0 Anthology
101 Essential Tips, Tricks & Hacks - Free 156 Page Preview. Learn the most practical features and best approaches for ASP.NET.
subscribe
Programmers Heaven C# School Book -Free 338 Page eBook
The Programmers Heaven C# School book covers the .NET framework and the C# language.
subscribe
Build Your Own ASP.NET 3.5 Web Site Using C# & VB, 3rd Edition - Free 219 Page Preview!
This comprehensive step-by-step guide will help get your database-driven ASP.NET web site up and running in no time..
subscribe
Merge line segments into a single line
Merge line segments into a single line
Merge line segments into a single line Merge line segments into a single line
Merge line segments into a single line
Merge line segments into a single line
Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line Merge line segments into a single line
Merge line segments into a single line
Merge line segments into a single line
 
Merge line segments into a single line
Merge line segments into a single line
 
-->