Java/divideconquer/ClosestPair.java at master · coder2hacker/Java · GitHub

History

338 lines (304 loc) · 10.7 KB

Raw

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

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

288

289

290

291

292

293

294

295

296

297

298

299

300

301

302

303

304

305

306

307

308

309

310

311

312

313

314

315

316

317

318

319

320

321

322

323

324

325

326

327

328

329

330

331

332

333

334

335

336

337

338

package divideconquer;

/**

* For a set of points in a coordinates system (10000 maximum), ClosestPair class calculates the two

* closest points.

* @author: anonymous

* @author: Marisa Afuera

public final class ClosestPair {

/** Number of points */

int numberPoints = 0;

/** Input data, maximum 10000. */

private Location[] array;

/** Minimum point coordinate. */

Location point1 = null;

/** Minimum point coordinate. */

Location point2 = null;

/** Minimum point length. */

private static double minNum = Double.MAX_VALUE;

public static void setMinNum(double minNum) {

ClosestPair.minNum = minNum;

}

public static void setSecondCount(int secondCount) {

ClosestPair.secondCount = secondCount;

}

/** secondCount */

private static int secondCount = 0;

/** Constructor. */

ClosestPair(int points) {

numberPoints = points;

array = new Location[numberPoints];

}

/** Location class is an auxiliary type to keep points coordinates. */

public static class Location {

double x = 0;

double y = 0;

/**

* @param xpar (IN Parameter) x coordinate

* @param ypar (IN Parameter) y coordinate

Location(final double xpar, final double ypar) { // Save x, y coordinates

this.x = xpar;

this.y = ypar;

}

public Location[] createLocation(int numberValues) {

return new Location[numberValues];

}

public Location buildLocation(double x, double y) {

return new Location(x, y);

}

/**

* xPartition function: arrange x-axis.

* @param a (IN Parameter) array of points

* @param first (IN Parameter) first point

* @param last (IN Parameter) last point

* @return pivot index

public int xPartition(final Location[] a, final int first, final int last) {

Location pivot = a[last]; // pivot

int i = first - 1;

Location temp; // Temporarily store value for position transformation

for (int j = first; j <= last - 1; j++) {

if (a[j].x <= pivot.x) { // Less than or less than pivot

i++;

temp = a[i]; // array[i] <-> array[j]

a[i] = a[j];

a[j] = temp;

}

i++;

temp = a[i]; // array[pivot] <-> array[i]

a[i] = a[last];

a[last] = temp;

return i; // pivot index

}

/**

* yPartition function: arrange y-axis.

* @param a (IN Parameter) array of points

* @param first (IN Parameter) first point

* @param last (IN Parameter) last point

* @return pivot index

public int yPartition(final Location[] a, final int first, final int last) {

Location pivot = a[last]; // pivot

int i = first - 1;

Location temp; // Temporarily store value for position transformation

for (int j = first; j <= last - 1; j++) {

if (a[j].y <= pivot.y) { // Less than or less than pivot

i++;

temp = a[i]; // array[i] <-> array[j]

a[i] = a[j];

a[j] = temp;

}

i++;

temp = a[i]; // array[pivot] <-> array[i]

a[i] = a[last];

a[last] = temp;

return i; // pivot index

}

/**

* xQuickSort function: //x-axis Quick Sorting.

* @param a (IN Parameter) array of points

* @param first (IN Parameter) first point

* @param last (IN Parameter) last point

public void xQuickSort(final Location[] a, final int first, final int last) {

if (first < last) {

int q = xPartition(a, first, last); // pivot

xQuickSort(a, first, q - 1); // Left

xQuickSort(a, q + 1, last); // Right

}

/**

* yQuickSort function: //y-axis Quick Sorting.

* @param a (IN Parameter) array of points

* @param first (IN Parameter) first point

* @param last (IN Parameter) last point

public void yQuickSort(final Location[] a, final int first, final int last) {

if (first < last) {

int q = yPartition(a, first, last); // pivot

yQuickSort(a, first, q - 1); // Left

yQuickSort(a, q + 1, last); // Right

}

/**

* closestPair function: find closest pair.

* @param a (IN Parameter) array stored before divide

* @param indexNum (IN Parameter) number coordinates divideArray

* @return minimum distance

public double closestPair(final Location[] a, final int indexNum) {

Location[] divideArray = new Location[indexNum];

System.arraycopy(a, 0, divideArray, 0, indexNum); // Copy previous array

int divideX = indexNum / 2; // Intermediate value for divide

Location[] leftArray = new Location[divideX]; // divide - left array

// divide-right array

Location[] rightArray = new Location[indexNum - divideX];

if (indexNum <= 3) { // If the number of coordinates is 3 or less

return bruteForce(divideArray);

}

// divide-left array

System.arraycopy(divideArray, 0, leftArray, 0, divideX);

// divide-right array

System.arraycopy(divideArray, divideX, rightArray, 0, indexNum - divideX);

double minLeftArea = 0; // Minimum length of left array

double minRightArea = 0; // Minimum length of right array

double minValue = 0; // Minimum lengt

minLeftArea = closestPair(leftArray, divideX); // recursive closestPair

minRightArea = closestPair(rightArray, indexNum - divideX);

// window size (= minimum length)

minValue = Math.min(minLeftArea, minRightArea);

// Create window. Set the size for creating a window

// and creating a new array for the coordinates in the window

for (int i = 0; i < indexNum; i++) {

double xGap = Math.abs(divideArray[divideX].x - divideArray[i].x);

if (xGap < minValue) {

ClosestPair.setSecondCount(secondCount + 1); // size of the array

} else {

if (divideArray[i].x > divideArray[divideX].x) {

break;

}

// new array for coordinates in window

Location[] firstWindow = new Location[secondCount];

int k = 0;

for (int i = 0; i < indexNum; i++) {

double xGap = Math.abs(divideArray[divideX].x - divideArray[i].x);

if (xGap < minValue) { // if it's inside a window

firstWindow[k] = divideArray[i]; // put in an array

k++;

} else {

if (divideArray[i].x > divideArray[divideX].x) {

break;

}

yQuickSort(firstWindow, 0, secondCount - 1); // Sort by y coordinates

/* Coordinates in Window */

double length = 0;

// size comparison within window

for (int i = 0; i < secondCount - 1; i++) {

for (int j = (i + 1); j < secondCount; j++) {

double xGap = Math.abs(firstWindow[i].x - firstWindow[j].x);

double yGap = Math.abs(firstWindow[i].y - firstWindow[j].y);

if (yGap < minValue) {

length = Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));

// If measured distance is less than current min distance

if (length < minValue) {

// Change minimum distance to current distance

minValue = length;

// Conditional for registering final coordinate

if (length < minNum) {

ClosestPair.setMinNum(length);

point1 = firstWindow[i];

point2 = firstWindow[j];

}

} else {

break;

}

ClosestPair.setSecondCount(0);

return minValue;

}

/**

* bruteForce function: When the number of coordinates is less than 3.

* @param arrayParam (IN Parameter) array stored before divide

* @return

public double bruteForce(final Location[] arrayParam) {

double minValue = Double.MAX_VALUE; // minimum distance

double length = 0;

double xGap = 0; // Difference between x coordinates

double yGap = 0; // Difference between y coordinates

double result = 0;

if (arrayParam.length == 2) {

// Difference between x coordinates

xGap = (arrayParam[0].x - arrayParam[1].x);

// Difference between y coordinates

yGap = (arrayParam[0].y - arrayParam[1].y);

// distance between coordinates

length = Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));

// Conditional statement for registering final coordinate

if (length < minNum) {

ClosestPair.setMinNum(length);

}

point1 = arrayParam[0];

point2 = arrayParam[1];

result = length;

}

if (arrayParam.length == 3) {

for (int i = 0; i < arrayParam.length - 1; i++) {

for (int j = (i + 1); j < arrayParam.length; j++) {

// Difference between x coordinates

xGap = (arrayParam[i].x - arrayParam[j].x);

// Difference between y coordinates

yGap = (arrayParam[i].y - arrayParam[j].y);

// distance between coordinates

length = Math.sqrt(Math.pow(xGap, 2) + Math.pow(yGap, 2));

// If measured distance is less than current min distance

if (length < minValue) {

// Change minimum distance to current distance

minValue = length;

if (length < minNum) {

// Registering final coordinate

ClosestPair.setMinNum(length);

point1 = arrayParam[i];

point2 = arrayParam[j];

}

result = minValue;

}

return result; // If only one point returns 0.

}

/**

* main function: execute class.

* @param args (IN Parameter)

* @throws IOException If an input or output exception occurred

public static void main(final String[] args) {

// Input data consists of one x-coordinate and one y-coordinate

ClosestPair cp = new ClosestPair(12);

cp.array[0] = cp.buildLocation(2, 3);

cp.array[1] = cp.buildLocation(2, 16);

cp.array[2] = cp.buildLocation(3, 9);

cp.array[3] = cp.buildLocation(6, 3);

cp.array[4] = cp.buildLocation(7, 7);

cp.array[5] = cp.buildLocation(19, 4);

cp.array[6] = cp.buildLocation(10, 11);

cp.array[7] = cp.buildLocation(15, 2);

cp.array[8] = cp.buildLocation(15, 19);

cp.array[9] = cp.buildLocation(16, 11);

cp.array[10] = cp.buildLocation(17, 13);

cp.array[11] = cp.buildLocation(9, 12);

System.out.println("Input data");

System.out.println("Number of points: " + cp.array.length);

for (int i = 0; i < cp.array.length; i++) {

System.out.println("x: " + cp.array[i].x + ", y: " + cp.array[i].y);

}

cp.xQuickSort(cp.array, 0, cp.array.length - 1); // Sorting by x value

double result; // minimum distance

result = cp.closestPair(cp.array, cp.array.length);

// ClosestPair start

// minimum distance coordinates and distance output

System.out.println("Output Data");

System.out.println("(" + cp.point1.x + ", " + cp.point1.y + ")");

System.out.println("(" + cp.point2.x + ", " + cp.point2.y + ")");

System.out.println("Minimum Distance : " + result);

}

Java/divideconquer/ClosestPair.java at master · coder2hacker/Java · GitHub

Uh oh!

Expand file tree

Breadcrumbs

ClosestPair.java

Latest commit

History

Breadcrumbs

ClosestPair.java

File metadata and controls