RE: [gnugo-devel] Surround revisions

[Portela Fernand]

Dan wrote:

> > In order to compute distances between corners of the convex hull
> > a sorting by angle algorythm has been implemented. If the distance
> > between a pair enclosing stones is large, the surround status gets
> > decreased to WEAKLY_SURROUNDED, or even 0 for very large ones.

> Could you explain the angle sorting?

Sorry, I should have documented this more. It is indeed not obvious that
this step is beneficial. A small diagram will probably help :

.O.O.
O...O
..X..
O...O
.O.O.

The sorting algorythm will (well, should) generate this :

.4.5.
3...6
..X..
2...7
.1.8.

That is, the points are sorted by ascending order of the measure of the
angle S-G-O, where S is SOUTH, G the (approximated) gravity center of the
goal, and O the position of the considered hostile stones.

The necessity of such sorting appeared when I tried to measure distances
between enclosing stones without sorting them, just by using directly the
existing left and right corners arrays. Unfortunately, in some positions,
the results were clearly inconsistent. I recall a position (but I haven't
kept it, sorry) where for instance the points 1,2,3,4,6 and 7 were in the
left arrary, leaving only 5 and 8 in the right array. As a result, because
of the large distance between 5 and 8, my patch would have declared the
dragon weakly, or even not surrounded at all. Such cases were not very
frequent, but enough for me to decide to implement the sorting.

/nando