Jump to content

File:Closest pair of points.svg

Page contents not supported in other languages.
This is a file from the Wikimedia Commons
From Wikipedia, the free encyclopedia

Original file (SVG file, nominally 256 × 256 pixels, file size: 1 KB)

Summary

Description
English: Closest pair of points shown in red.
Date
Source Own work
Author Qef
Other versions Bitmap version: file:ClosestPair.png

Licensing

Creative Commons CC-Zero This file is made available under the Creative Commons CC0 1.0 Universal Public Domain Dedication.
The person who associated a work with this deed has dedicated the work to the public domain by waiving all of their rights to the work worldwide under copyright law, including all related and neighboring rights, to the extent allowed by law. You can copy, modify, distribute and perform the work, even for commercial purposes, all without asking permission.

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')

Captions

Add a one-line explanation of what this file represents

Items portrayed in this file

depicts

22 June 2009

image/svg+xml

120742ed70c3028e512f55d9b9e19453b4a7df2f

1,365 byte

256 pixel

256 pixel

File history

Click on a date/time to view the file as it appeared at that time.

Date/TimeThumbnailDimensionsUserComment
current04:03, 22 June 2009Thumbnail for version as of 04:03, 22 June 2009256 × 256 (1 KB)Qef{{Information |Description={{en|1=Closest pair of points shown in red.}} |Source=Own work by uploader |Author=Qef |Date=2009-06-22 |Permission= |other_versions=Bitmap version: file:ClosestPair.png }} <!--{{ImageUpload|full}}--> [[Catego

The following page uses this file:

Global file usage

The following other wikis use this file: