Interpolation of lines in polygon system

[cyborg]

http://www.vbforums.com/showthread.p...hreadid=203840

[krtxmrtz]

When, in your drawing, you say "clicking the polygon", do you really mean "clicking the polygon's vertex"?

[krtxmrtz]

Well, I suppose the answer to my previous post is yes.

Referring to the attached drawing (I have only worked out the coordinates for one of the blue points, the other one is calculated in an analogous fashion):

alpha=0.5*(phi1+phi2)

phi1=arctan[(y(i)-y(i-1))/(x(i)-x(i-1))]
phi2=arctan[(y(i+1)-y(i))/(x(i+1)-x(i))]

beta=0.5*(theta1+theta2)

theta1=arctan[(y(i+2)-y(i+1))/(x(i+2)-x(i+1))]
theta2=-phi2

Equation of straight line BP(i): can be calculated knowing that the slope must be tan(alpha) and that it must pass through point
P(i). The result is:

y1=(x-x(i))tan(phi1)+y(i)

By a similar calculation, line AP(i+1) is:

y2=(x-x(i+1))tan(phi2)+y(i+1)

The blue point (O in the drawing) lies at the intersection of these 2 lines. To determine its coordinates, set y1=y2 and solve for x:

(x-x(i))tan(phi1)+y(i)=(x-x(i+1))*tan(phi2)+y(i+1)

so that

xo=(y(i+1)-y(i)+x(i)tan(phi1)-x(i+1)tan(phi2))/(tan(phi1)-tan(phi2))

and substituting xo into one of the above straight line equations,

yo=(xo-x(i))tan(phi1)+y(i)

[cyborg]

well actually i meant that the user was clicking the polygon itself to make one new dot at each side of it, but clicking the vertex would also do fine!

the problem is that im not fully educated in maths so i would be very grateful if you could show me some actual VB code, because it would be easier for me to understand!

Thanks for your time!

[cyborg]

i forgot to mention...
is there a way to make the new polygon(s) to shape the vertex more like a circle?
that would be much better!

[DiGiTaIErRoR]

You could get the points of a circle to n points.

[cyborg]

I mean a more smooth shape....not really circle shaped, but it doesnt have to be exactly half the angle, if there is a better way to do it...

as i said: im not fully educated in math so its easier for me to understand VB code...

If you could do some of the code i could maybe do some other...

[DiGiTaIErRoR]

So then you should make each section 2.

Points along a curve.

[cyborg]

but how do i know the curve?

ive made (and attached) a little illustration...

compare the two different lines, then you'll see what i want

i want the program to create new polygons to smoothen the curves.

[krtxmrtz]

Have you tried "spline" interpolation? In some instances it produces a very smooth nice-looking curve.
I don't have vb code for it but maybe you can make do with a Fortran subroutine. It's similar enough that you could easily "translate". Are you interested?

[krtxmrtz]

You know, after all I've found the vb version of the spline routines. I'm not sure it can solve your problem as it is perhaps more suited to some less-smooth type of data, I mean, maybe it will show some sine/cosine-like nasty waves. If you want to give it a try, use the Spline sub to calculate your coefficients and then SplineEval to calculate the polynomial fit for a single point each time it is called.

Sub Spline(n, x, y, b, c, d)
    Dim t As Single
    Dim ib As Integer, nmi As Integer
'-----------------------------------------------------------------------------------
'This subroutine calculates the corfficients b(i),c(i),d(i)
'with i=1,...,n of the n cubic spline polynomes for the n
'points x(i),y(i), (i=1,...,n)
'In the calling program, add these 2 lines:
'dim x(1 to n) as single,y(1 to n) as single
'dim b(1 to n) as single,c(1 to n) as single,d(1 to n) as single
'-----------------------------------------------------------------------------------
    If n < 2 Then
    'Too few points
    'Add some error code here
        Exit Sub
    End If
    If n < 3 Then
        b(1) = (y(2) - y(1)) / (x(2) - x(1))
        c(1) = 0
        d(1) = 0
        b(2) = b(1)
        c(2) = 0
        d(2) = 0
        Exit Sub
    End If
    nmi = n - 1
    d(1) = x(2) - x(1)
    c(2) = (x(2) - x(1)) / d(1)
    For i = 2 To nmi
        d(i) = x(i + 1) - x(i)
        b(i) = 2 * (d(i - 1) + d(i))
        c(i + 1) = (y(i + 1) - y(i)) / d(i)
        c(i) = c(i + 1) - c(i)
    Next
    b(1) = -d(1)
    b(n) = -d(n - 1)
    c(1) = 0
    c(n) = 0
    If n <> 3 Then
        c(1) = c(3) / (x(4) - x(2)) - c(2) / (x(3) - x(1))
        c(n) = c(n - 1) / (x(n) - x(n - 2)) - c(n - 2) / (x(n - 1) - x(n - 3))
        c(1) = c(1) * d(1) ^ 2 / (x(4) - x(1))
        c(n) = -c(n) * d(n - 1) ^ 2 / (x(n) - x(n - 3))
    End If
    For i = 2 To n
        t = d(i - 1) / b(i - 1)
        b(i) = b(i) - t * d(i - 1)
        c(i) = c(i) - t * c(i - 1)
    Next
    c(n) = c(n) / b(n)
    For ib = 1 To nmi
        i = n - ib
        c(i) = (c(i) - d(i) * c(i + 1)) / b(i)
    Next
    b(n) = (y(n) - y(nmi)) / d(nmi) + d(nmi) * (c(nmi) + 2 * c(n))
    For i = 1 To nmi
        b(i) = (y(i + 1) - y(i)) / d(i) - d(i) * (c(i + 1) + 2 * c(i))
        d(i) = (c(i + 1) - c(i)) / d(i)
        c(i) = 3 * c(i)
    Next
    c(n) = 3 * c(n)
    d(n) = d(n - 1)
End Sub
'-----------------------------------------------------------------------------------
Function SplineEval(n, u, x, y, b, c, d)
    Dim s As Single
    Dim j As Integer, k As Integer
'Given points x(i),y(i),(i=1,...,n), the coefficients b(i),c(i) and d(i),
'(i=1,...,n) of the corresponding cubic spline polynomes and a
'value x=u, this function determines the interval [x(i),x(i+1)] in
'which u is contained and calculates P(u), P being the polynome
'corresponding to that interval
    i = 1
    If i >= n Then i = 1
    If u < x(i) Then GoTo First
    If u <= x(i + 1) Then GoTo Third
First:
'Binary search
    i = 1
    j = n + 1
Second:
    k = (i + j) \ 2
    If u < x(k) Then j = k
    If u >= x(k) Then i = k
    If j > i + 1 Then GoTo Second
Third:
'Evaluate spline
    s = u - x(i)
    SplineEval = y(i) + s * (b(i) + s * (c(i) + s * d(i)))
End Function

[krtxmrtz]

Yet another suggestion: I seem to recall that for polygon data smoothing a good tool is the so-called Bezier's polynomes, but I have never worked with them.

I think you should try a google or altavista search for "Bezier lines" or "Bezier curves", or go directly to this site: http://www.moshplant.com/direct-or/bezier/index.html

Good luck!

[cyborg]

ok...
i'll try those things!
thanks for all your help!

[cyborg]

hey!
i found out a way to do it the first way i suggested, but somethings a bit wrong...

ill attach the source for you to see whats wrong...
pretty bad writted code, but you'll probably understand it.

[cyborg]

btw. i tried the bezier curve and it was awesome!

[cyborg]

check out this nice app i made with bezier curves!

[cyborg]

newer version!

[Sastraxi]

Good work

[cyborg]

Thanks!

but i've done some changes :P

its now possible to save as project file and image file
and loading is also possible, importing BG pics, deleting lines
coloring lines etc...

check this out

[cyborg]

it would be really cool to AA the lines!
does anyone here know how to do that?

i can attach the source if you want...

[cyborg]

i'll post this as a new thread!

[krtxmrtz]

I see you are really speeding your way along the Bezier road!

In your original post below, I assume you referred to the behaviour of the points when you use the 'smooth' tool. I may take a deeper look at it as soon as I have some time... in case you're still interested.

Originally posted by cyborg
hey!
i found out a way to do it the first way i suggested, but somethings a bit wrong...

ill attach the source for you to see whats wrong...
pretty bad writted code, but you'll probably understand it.

[cyborg]

yes im still interested!

[krtxmrtz]

Hmmm... I think I'll take a look at it over the week end.

[cyborg]

ok, thanks alot!