Search code examples
prologclpfd

Prolog - Calculating coordinates of Koch-curve

I'm learning about constraint programming and recursive programming in Prolog. I have to programm a koch-curve of Level N which should start at (Sx,Sy) and end at (Ex,Ey).The line-segments, which are being calculated, will be stored in Ls.
When I try to execute generatelines(1,(60,0),(-60,0),Ls), I get the right 4 coordinates of the koch-curve of level 1: 

[[ (60, 0), (20, 0)],
[ (20, 0), (0.0, -34.64)],
[ (0.0, -34.64), (-20, 0)], 
[ (-20, 0), (-60, 0)]]

When I try to execute generatelines(2,(60,0),(-60,0),Ls), then I get all the coordinates between the next start (60,0) and end point (20,0). But I even need all coordinates between following start and endpoints:

(20, 0), (0.0, -34.64),
(0.0, -34.64), (-20, 0),
(-20, 0), (-60, 0)

too.

My problem is, I don't know how to implement it, to get the coordinates of a higher level.
Actually I think the following should happen:

generatelines(N1,(60,0),(20,0),Ls1)
generatelines(N1,(20,0),(0,-34.64),Ls1)
generatelines(N1,(0,-34.64),(-20,0),Ls1)
generatelines(N1,(-20,0),(-60,0),Ls1).

Maybe there is somebody here to help me solving this problem.
thanks

This is the code I have until now:

- consult(library(clpfd)).
generatelines(0,_,_,Ls):- !.
generatelines(N, (Sx,Sy),(Ex,Ey),[Ls|Ls1]):-
N1 is N-1,

X2 is Sx+(Ex-Sx)/3,
Y2 is Sy+(Ey-Sy)/3,
R1 is sqrt((X2-Sx)*(X2-Sx)+(Y2-Ey)*(Y2-Ey)),
Phi1 is atan((Y2-Sy)/(X2-Sx)),
X3 is X2 +R1*cos((Phi1-240)*pi/180),
Y3 is Y2 +R1*sin((Phi1+240)*pi/180),
X4 is X2+(X2-Sx),
Y4 is Y2+(Y2-Sy),
Ls = [
      [(Sx,Sy),(X2,Y2)],
      [(X2,Y2),(X3,Y3)],
      [(X3,Y3),(X4,Y4)],
      [(X4,Y4),(Ex,Ey)]
     ],   
generatelines(N1,(Sx,Sy),(X2,Y2),Ls1).
Solution

  • You are trying to do too much at once, in one predicate. In many other programming languages it is easy to get carried away and put too much into one function or method; that is a style issue, but it can work. In Prolog, many things simply cannot be expressed without auxiliary predicates, essentially because we have no loops like other languages.

    The key here is to decompose your program into several distinct predicates each with its own responsibilities, something like this:

    • segments(S, E, Ls) for computing the list Ls of the four "first-level" line segments between start and end points S and E
    • next_level_segments(Segments, RefinedSegments) which takes a list of line segments Segments, each of the form [P, Q], and generates the "next-level" list of segments between each such pair of end points P and Q
    • iterate_level(N, InitialSegments, FinalSegments) which iterates the next_level_segments operation N times

    Your final predicate is then simply:

    generatelines(N, S, E, Segments) :-
    segments(S, E, InitialSegments),
    iterate_level(N, InitialSegments, Segments).

    Of course you have to define these auxiliary predicates, but that is your homework.

    Note also that you are not actually using the clpfd library.