File:Closest pair of points.svg

From Wikimedia Commons, the free media repository

• File
• File history
• File links

[edit] Summary

Description	Closest pair of points.svg English: Closest pair of points shown in red.
Date	22 June 2009(2009-06-22)
Source	Own work
Author	Qef
Permission (Reusing this image)	See below.
Other versions	Bitmap version: file:ClosestPair.png

[edit] Licensing

This file is made available under the Creative Commons CC0 waiver. The author of this work has dedicated it to the public by waiving all of his or her rights to the work under copyright law and all related or neighboring legal rights he or she had in the work, to the extent allowable by law. Deutsch | English | Suomi | Français | Italiano | Lietuvių | Македонски | 中文 | ‪中文(简体)‬ | ‪中文(繁體)‬ | +/−

[edit] Source code

The SVG was generated by running the Lua program given below. It deliberately fails if the closest points would be overlapping in the image, because that would be confusing.

local WD, HT, NUM_POINTS = 256, 256, 16
local COLOR = { normal = '#000', closest = '#f00' }
local RADIUS = 5

math.randomseed(os.time())
local P = {}
for _ = 1, NUM_POINTS do
    P[#P+1] = { x = RADIUS + (WD - 2*RADIUS) * math.random(),
                y = RADIUS + (HT - 2*RADIUS) * math.random() }
end

-- Find closest pair, using naive algorithm.
local closest_a, closest_b
local min_dist
for i, p in ipairs(P) do
    for j, q in ipairs(P) do
        if i ~= j then
            local dist = math.sqrt((p.x - q.x)^2 + (p.y - q.y)^2)
            if not min_dist or dist < min_dist then
                min_dist = dist
                closest_a, closest_b = i, j
            end
        end
    end
end

if min_dist < RADIUS then
    error("points on top of each other, run me again")
end

io.write('<?xml version="1.0" encoding="UTF-8" standalone="no"?>\n',
         '<svg svg="http://www.w3.org/2000/svg" version="1.0"',
         ' width="', WD, '" height="', HT, '">\n')
for i, p in ipairs(P) do
    local color = COLOR.normal
    if i == closest_a or i == closest_b then color = COLOR.closest end
    io.write(' <circle cx="', RADIUS + p.x, '" cy="', RADIUS + p.y,
             '" r="', RADIUS, '" style="fill:', color, '"/>\n')
end
io.write('</svg>\n')

File history

• Edit this file using an external application (See the setup instructions for more information)

File links