0

I have a List L with some terms like range(2,3), where the first element is the term with the lowest Y, now I need to sort the other elements of the list L (the first element will remain unchanged), I need to sort them by polar angle in counterclockwise order. If polar angle of two points is same, then I need to put the nearest term first. I defined the predicate angle2d/2:

angle2d(A, B, R) :-
   A =.. [_,Ax,Ay],
   B =.. [_,Bx,By],
   R is atan2((Ay-By),(Ax-Bx)).

that give me the counter clockwise angle between 2 points, but i didn't get how to create the predicate sort_list/2 that will sort my n-1 points (the first one element of the list will remain unchanged) by their counter clockwise angle with the first element (point) of the list.

false
  • 10,264
  • 13
  • 101
  • 209
Moksud Ahmed
  • 131
  • 2
  • 11

2 Answers2

1

As a general method for sorting by some weird custom criterion, first define you compare_custom/3 predicate, and then use it with a known sorting algorithm. In SWI you can use the predsort/3 predicate that is defined as following:

predsort(+Pred, +List, -Sorted)
Sorts similar to sort/2, but determines the order of two terms by calling Pred(-Delta, +E1, +E2) . This call must unify Delta with one of <, > or =. If the built-in predicate compare/3 is used, the result is the same as sort/2. See also keysort/2.

You should also take a look at the predefined compare/3:

compare(?Order, @Term1, @Term2)
Determine or test the Order between two terms in the standard order of terms. Order is one of <, > or =, with the obvious meaning.

Eugene Sh.
  • 17,802
  • 8
  • 40
  • 61
  • 3
    The common approach is to map the list accordingly and use `keysort/2` or even just `sort/2`. For most cases, `predsort/3` is just slow. – false Jul 22 '15 at 18:54
  • @false There are two criterions with different priority, so it won't be straightforward (yet not impossible, of course) to combine them into a single key. – Eugene Sh. Jul 22 '15 at 18:57
  • @WillNess Could you clarify your comment? – Eugene Sh. Jul 22 '15 at 19:00
  • 1
    lexicographic order works. `?- keysort( [(1-3)-2, (2-1)-3, (1-2)-1], L).` => `L = [1-2-1, 1-3-2, 2-1-3].` – Will Ness Jul 22 '15 at 19:01
  • 2
    https://en.wikipedia.org/wiki/Schwartzian_transform#Comparison_to_other_languages ... – Will Ness Jul 22 '15 at 19:09
  • @EugeneSh.: in this particular case, two criteria are not a problem, but maybe there are cases where they are a problem? Mhmhm, looks like a question. – false Jul 22 '15 at 19:14
  • @false You mean when the lexicographic order won't work? I am trying to think of any, but the Gödel numbering is making it difficult.... – Eugene Sh. Jul 22 '15 at 19:19
  • @EugeneSh.: When mapping onto some other term that is sorted either by `keysort/2` or `sort/2`. – false Jul 22 '15 at 19:20
  • @false Uncountable sets? But I can't see how to apply it here :) – Eugene Sh. Jul 22 '15 at 19:28
  • @false Anyway, assuming there IS such a set (which can be sorted by `predsort`, but not having the `key` mapping), we always can make the `key` function which will assign the key with the value of the index obtained using the other sorting method. So no, I guess there is no such a (finite) sets. – Eugene Sh. Jul 22 '15 at 19:34
  • decorate-sort-undecorate generally doesn't apply when we can't invent a value mapping giving the same order as the comparison sort for a given predicate, so we must actually compare the two given elements. a concrete example eludes me at the moment. something to do with the secondary test being dependent on the result of the first. – Will Ness Jul 22 '15 at 19:34
  • @WillNess I think it will be only in case the comparison result is depending not only on the two compared elements, but some other parameters as well (for example the result of previous comparisons). But still, you can always use the "working" sort method, and just map the values to the indices obtained from that sort. – Eugene Sh. Jul 22 '15 at 19:44
  • @WillNess Some weird results will come up if we define our "less-than" predicate as a none transitive way. For example a – Eugene Sh. Jul 22 '15 at 19:51
  • 1
    @WillNess & Eugene: Please [see my question](http://stackoverflow.com/questions/31573197/sort-2-keysort-2-vs-predsort-3). – false Jul 22 '15 at 20:19
  • There is anyone who have time and can help me privately with this project please? mail me at moksud_xp@hotmail.it please. – Moksud Ahmed Jul 22 '15 at 21:54
  • @WillNess I don't understand how to use the predicate predsort to sort my n-1 elements by Counter Clockwise Order, can you help me writing it for my excercise please? – Moksud Ahmed Jul 23 '15 at 13:02
  • @EugeneSh. "you can always use the "working" sort method, and just map the values to the indices obtained from that sort." the point is to be able to *precalculate* the values, only once for each element, _before_ the sorting. – Will Ness Jul 23 '15 at 21:19
  • @WillNess I understand that. But it "disproves" the claim that there is no such a mapping function. Of course we can restrict this function to one argument only, then it won't be valid. – Eugene Sh. Jul 23 '15 at 21:22
  • @EugeneSh. even if we know that something exists, we still need to know how to construct it. that's two separate tasks. SWI's `sort/4` looks relevant. – Will Ness Jul 23 '15 at 21:26
1

I did this:

sort_angle([], _).
sort_angle([_|[]], _).
sort_angle([_,_|[]], _).
sort_angle(List, SortedList) :-
   predsort(sort_me,[_|List], SortedList).

sort_me(<, A, B) :- angle2d(H,A,X), angle2d(H,B,Y), X<Y.
sort_me(>, A, B) :- angle2d(H,A,X), angle2d(H,B,Y), X>Y.
sort_me(=, A, B) :- angle2d(H,A,X), angle2d(H,B, Y), X=Y.

But I don't know, in the sort_me predicate how to tell that H is the first element of my list... how can I tell it ?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Moksud Ahmed
  • 131
  • 2
  • 11
  • this should work in SWI: `sorted_by_angle([H|List], [H|SortedList]):- predsort(compare_me(H), List, SortedList).`, `compare_me(H,<,A,B):- angle..., angle..., (X – Will Ness Jul 23 '15 at 13:58
  • @WillNess what do you mean with "angle..." ? – Moksud Ahmed Jul 23 '15 at 14:45
  • @WillNess what is "N" and "K" ? – Moksud Ahmed Jul 23 '15 at 14:53
  • @WillNess I don't understand what is the predicate distance and what it does – Moksud Ahmed Jul 23 '15 at 14:55
  • like angle calculates angle from point A to point B, distance is supposed to calculate the dstance. you said, when two angles are the same, the *nearest* point should go first. I assumed, nearest to the first list's element. `N` and `K` both are placed as the third argument to `distance/3`, presumably the result of this calculation. you need to write this predicate, just like you had `angle2d/3`. – Will Ness Jul 23 '15 at 21:14
  • Not knowing what angle2d/3 does, but I guess sort_me(D, A, B) :- angle2d(H,A,X), angle2d(H,B,Y), compare(D,X,Y). is more efficient. –  Jul 24 '15 at 11:10