Solution to Polygon-Concavity-Index by codility

18 Oct

October 18, 2015 Sheng 5

Question: https://codility.com/demo/take-sample-test/polygon_concavity_index/

Question Name: Polygon-Concavity-Index or PolygonConcavityIndex

Thanks to Robert Sedgewick, the Youtube video (Algorithms, Part I – Convex Hull) tells everything about this problem.

def _IsClockwise(point_A, point_B, point_C):

''' Return the direction from points A -> B -> C.

'''

result = (point_B.x - point_A.x) * (point_C.y - point_A.y) -

(point_B.y - point_A.y) * (point_C.x - point_A.x)

# The direction of a->b->c is:

if result > 0: return 1 # counter-clockwise

elif result < 0: return -1 # clockwise

else: return 0 # a staight line

def solution(A):

''' The solution refers to:

https://www.youtube.com/watch?v=0HZaRu5IupM

'''

# Find the lowest point(s) in y-axis.

lowest_y = A[0].y

lowest_y_index = []

for i in xrange(len(A)):

if A[i].y < lowest_y:

lowest_y = A[i].y

lowest_y_index = [i]

elif A[i].y == lowest_y:

lowest_y_index.append(i)

else:

continue

# Find a point, which is not the lowest in y-axis and immediately

# after a lowest-in-y-axis point.

start_point = lowest_y_index[0]

lowest_y_array = [False] * len(A)

for i in lowest_y_index: lowest_y_array[i] = True

while lowest_y_array[start_point] == True:

start_point = (start_point + 1) % len(A)

start_point = (start_point - 1 + len(A)) % len(A)

# Re-organize the points so that, it is easier to check every three

# consecutive points in one loop (without module operation %).

rotated_A = A[start_point : ] + A[ : start_point]

# We find the start point such that, the direction is non-zero.

direction = _IsClockwise(rotated_A[-1], rotated_A[0], rotated_A[1])

extened_A = rotated_A + rotated_A[:2]

for i in xrange(len(A)):

temp = _IsClockwise(extened_A[i], extened_A[i+1], extened_A[i+2])

if temp * direction < 0:

# Compute the original index and return

return (i + 1 + start_point)%len(A)

# Every point is on the convex hull.

return -1

5 Replies to “Solution to Polygon-Concavity-Index by codility”

Levi says:
July 17, 2017 at 11:25 am
Hi! I do not understand how exactly to do it in languages that can have arithmetic overflow in functions like _IsClockwise. Levi
Reply
- Sheng says:
  July 18, 2017 at 10:25 pm
  hmm~ Good catch! Python does not have the overflow issue. And Java has BigInteger/BigDecimal. For C/C++, you can have a similar big number class or use more if-else in overflow detection.
  Reply

Is following code really required in above solution?

lowest_y_array = [False] * len(A)

for i in lowest_y_index: lowest_y_array[i] = True

while lowest_y_array[start_point] == True:

start_point = (start_point + 1) % len(A)

start_point = (start_point - 1 + len(A)) % len(A)

Sheng says:
September 3, 2020 at 6:23 pm
It seems the reference video is unavailable now. You can check the algorithm here: https://www.coursera.org/learn/algorithms-part1. The course is free and the best.
Reply

This is my C++ solution:
https://app.codility.com/demo/results/trainingFPR47Z-YXZ/

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

#include <iostream>

#include <vector>

using namespace std;

struct Point2D {

int x;

int y;

};

int dir(const Point2D & point, const Point2D & previous, const Point2D & next) {

double v_x = point.x - previous.x;

double v_y = point.y - previous.y;

double w_x = next.x - previous.x;

double w_y = next.y - previous.y;

double determinant = v_x * w_y - v_y * w_x;

int result = 0;

if (determinant < 0) {

result = -1;

} else if (determinant > 0) {

result = 1;

}

return result;

}

int solution(vector<Point2D> &A) {

int N = A.size();

if (N < 4) return -1;

// step 1 - finding a point in the border of the the convex hull

int start_index = 0;

int lowest = A[0].x;

for (int i = 1; i < N; ++i) {

if (A[i].x < lowest) {

lowest = A[i].x;

start_index = i;

}

// step 2 - checking for direction changing

// discarding direction == 0

// if previous direction != current direction then it is not convex!

int last_dir = 0;

for (int i = start_index, counter = 0; counter < N; ++counter) {

int previous = (i + N - 1) % N;

int next = (i + 1) % N;

int direction = dir(A[i], A[previous], A[next]);

if (direction != 0) {

if (last_dir != 0) {

if (last_dir != direction) {

return i;

}

} else {

last_dir = direction;

}

i = (i + 1) % N;

}

// no direction changing found. Indicate convex hull by returning -1

return -1;

}

void check(int number, vector<Point2D> &A, int expected) {

int actual = solution(A);

cout << number << ") " << actual << " should be " << expected;

if (actual != expected) {

cout << " (WRONG) ";

}

cout << "\n";

}

void check1(int number) {

vector<Point2D> A(5);

A[0].x = -1; A[0].y = 3;

A[1].x = 1; A[1].y = 2;

A[2].x = 3; A[2].y = 1;

A[3].x = 0; A[3].y = -1;

A[4].x = -2; A[4].y = 1;

check(number, A, -1);

}

void check2(int number) {

vector<Point2D> A(7);

A[0].x = -1; A[0].y = 3;

A[1].x = 1; A[1].y = 2;

A[2].x = 1; A[2].y = 1;

A[3].x = 3; A[3].y = 1;

A[4].x = 0; A[4].y = -1;

A[5].x = -2; A[5].y = 1;

A[6].x = -1; A[6].y = 2;

check(number, A, 2);

}

void check3(int number) {

vector<Point2D> A(5);

A[0].x = -1; A[0].y = 3;

A[1].x = 1; A[1].y = 2;

A[2].x = 3; A[2].y = 1;

A[3].x = 0; A[3].y = -1;

A[4].x = 0; A[4].y = 1;

check(number, A, 4);

}

void check4(int number) {

//triangle

vector<Point2D> A(3);

A[0].x = 0; A[0].y = 0;

A[1].x = 1; A[1].y = 0;

A[2].x = 1; A[2].y = 1;

check(number, A, -1);

}

void check5(int number) {

// square

vector<Point2D> A(4);

A[0].x = 0; A[0].y = 1;

A[1].x = 1; A[1].y = 1;

A[2].x = 1; A[2].y = 0;

A[3].x = 0; A[3].y = 0;

check(number, A, -1);

}

void check6(int number) {

// boomerang

vector<Point2D> A(4);

A[0].x = 0; A[0].y = 10;

A[1].x = 1; A[1].y = 1;

A[2].x = 2; A[2].y = 10;

A[3].x = 1; A[3].y = 0;

check(number, A, 1);

}

void check7(int number) {

// losangle

vector<Point2D> A(4);

A[0].x = 0; A[0].y = 0;

A[1].x = 1; A[1].y = 10;

A[2].x = 2; A[2].y = 0;

A[3].x = 1; A[3].y = -1;

check(number, A, -1);

}

void check8(int number) {

// boomerang

vector<Point2D> A(4);

A[0].x = 0; A[0].y = 0;

A[1].x = 1; A[1].y = 10;

A[2].x = 2; A[2].y = 0;

A[3].x = 1; A[3].y = 1;

check(number, A, 3);

}

void check9(int number) {

// square counter clockwise

vector<Point2D> A(4);

A[0].x = 0; A[0].y = 0;

A[1].x = 1; A[1].y = 0;

A[2].x = 1; A[2].y = 1;

A[3].x = 0; A[3].y = 1;

check(number, A, -1);

}

void check10(int number) {

// straight-line

vector<Point2D> A(4);

A[0].x = 0; A[0].y = 0;

A[1].x = 1; A[1].y = 2;

A[2].x = 3; A[2].y = 6;

A[3].x = 5; A[3].y = 8;

check(number, A, -1);

}

int main() {

int caseNumber = 1;

check1(caseNumber++);

check2(caseNumber++);

check3(caseNumber++);

check4(caseNumber++);

check5(caseNumber++);

check6(caseNumber++);

check7(caseNumber++);

check8(caseNumber++);

check9(caseNumber++);

return 0;

}

5 Replies to “Solution to Polygon-Concavity-Index by codility”

Leave a Reply Cancel reply