Algorithm to Add new link to a Line

BlitzMax Forums/BlitzMax Programming/Algorithm to Add new link to a Line

Armitage 1982

(Posted 2009) [#1]

Hello

I'm wondering what would be the best solution to add a corner point into a line.
A bit like a vectorial application editing with the add vertex tool.

I only have a set of 2D vector so there isn't really a line object.
The 2D vectors are store into a TList object.

I would probably be able to add new link between 2 points based on a certain "active" area around the line.

Currently I'm using the nearest link to the mouse position and add my new point after this link in the list.

Do you know any existing solution ?
Thanks

Warpy

(Posted 2009) [#2]

Ok, so I'm assuming you've got a chain of these line segments joined up together, like a spline in a vector app.

You want to find the perpendicular distance between the mouse and each segment. The one that's closest is the one you want, and then you can use the calculations you've already done to find the point on the line segment closest to the mouse, where you will add the new vertex.

I've got to go to work now, but here's a function to work out the perpendicular distance between a point and a line. It's not the fastest, but it's good enough for this use.

Function pointlinedistance#(px#,py#,ax#,ay#,bx#,by#)
	dx#=bx-ax
	dy#=by-ay
	an#=ATan2(dy,dx)
	nx#=Cos(an+90)
	ny#=Sin(an+90)
	lambda#=(py-ay+(ax-px)*dy/dx)/(nx*dy/dx-ny)
	Return lambda#
End Function

Armitage 1982

(Posted 2009) [#3]

Thanks !
You show me the right solution :)

I finally use this 2D Math function from Jasu find inside the Code Archive :

rem
bbdoc:This function calculates the distance between a line segment and a point.
endrem
Function DistanceToLineSegment:Float (x1:Float, y1:Float, x2:Float, y2:Float, Px:Float, Py:Float)
	
	Local Dx:Float, Dy:Float, Ratio:Float
	
	If (x1 = x2) And (y1 = y2) Then
		Return Sqr( (Px-x1)*(Px-x1)+(Py-y1)*(Py-y1) )
	Else
		
		Dx = x2 - x1
		Dy = y2 - y1
		Ratio = ((Px - x1) * Dx + (Py - y1) * Dy) / (Dx * Dx + Dy * Dy)
		
		If Ratio < 0 Then
			Return Sqr( (Px-x1)*(Px-x1)+(Py-y1)*(Py-y1) )
		ElseIf Ratio > 1 Then
			Return Sqr( (Px-x2)*(Px-x2)+(Py-y2)*(Py-y2) )
		Else
			Return Sqr ((Px - ((1 - Ratio) * x1 + Ratio * x2))*(Px - ((1 - Ratio) * x1 + Ratio * x2))+(Py - ((1 - Ratio) * y1 + Ratio * y2))*(Py - ((1 - Ratio) * y1 + Ratio * y2)))
		EndIf
		
	EndIf
	
End Function

Work perfectly !