1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123

/*
 * Copyright 2010 eBusinessInformation
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package com.excilys.blog.refactoring.fixed;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

import com.excilys.blog.refactoring.GeoPoint;
import com.excilys.blog.refactoring.HullHelper;

public class FixedInitialHullHelper implements HullHelper {

    public List<GeoPoint> computeConvexHull(Set<GeoPoint> points) {
        if (points == null) {
            throw new IllegalArgumentException();
        }

        if (points.size() == 1) {
            return new ArrayList<GeoPoint>(points);
        }

        // Path list
        ArrayList<GeoPoint> path = new ArrayList<GeoPoint>();

        // Pick the min longitude point as first
        GeoPoint first = null;
        for (GeoPoint point : points) {
            if (first == null || point.getLongitude() < first.getLongitude()) {
                first = point;
            }
        }

        if (first != null) {
            path.add(first);
        } else {
            throw new IllegalArgumentException("Can't retrieve the western point");
        }

        boolean right = true;
        boolean loop = true;

        while (loop) {

            GeoPoint current = path.get(path.size() - 1);

            GeoPoint next = null;
            double nextLatitudeDiff = 0;
            double nextLongitudeDiff = 0;
            boolean recordNext = false;
            for (GeoPoint point : points) {
                if (!point.equals(current)) {
                    double latitudeDiff = point.getLatitude() - current.getLatitude();
                    double longitudeDiff = point.getLongitude() - current.getLongitude();

                    if (longitudeDiff == 0 && latitudeDiff < 0 == right || longitudeDiff > 0 == right) {
                        if (next == null) {
                            recordNext = true;
                        } else {
                            // Compare the 'a' in the linear equation Y = a.X
                            // that correspond to the line slope.
                            boolean negativeSlope = latitudeDiff * nextLongitudeDiff - nextLatitudeDiff * longitudeDiff < 0;

                            if (negativeSlope) {
                                recordNext = true;
                            }
                        }

                        if (recordNext) {
                            recordNext = false;
                            next = point;
                            nextLatitudeDiff = latitudeDiff;
                            nextLongitudeDiff = longitudeDiff;
                        }

                    }
                }
            }

            if (next != null) {

                // Check abnormal case
                if (path.size() > points.size() + 1) {
                    throw new RuntimeException("Convex hull computation failed");
                }

                path.add(next);

                /*
                 * If we are not back to the first point, let's continue finding
                 * the path.
                 * 
                 * Otherwise, do nothing => going back from the stack, this is
                 * actually the end point of the recursive algorithm.
                 */

                if (path.get(0) == next) {
                    loop = false;
                }

            } else {
                // We have reach the point on the right, let's go back!
                right = !right;
            }
        }

        return path;
    }

}