263:
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, '", color, '"/>\n') end io.write('</svg>\n')
38:
203:
209:
90:
262:
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 = { x = RADIUS + (WD - 2*RADIUS) * math.random(), y = RADIUS + (HT - 2*RADIUS) * math.random() } end --
230:
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.
773:
875:
920:
930:
259:
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.
830:
940:
64:
60:
56:
52:
48:
42:
101:
606:
518:
412:
73:
448:
812:
701:
664:
627:
572:
538:
502:
396:
370:
355:
340:
599:
468:
432:
313:
296:
900:
790:{{Information |Description={{en|1=Closest pair of points shown in red.}} |Source=Own work by uploader |Author=
347:
795:
215:
109:
890:
910:
227:
850:
184:
772:
767:
218:
37:
865:
362:
96:
153:
226:
The person who associated a work with this deed has dedicated the work to the
791:
783:
173:
740:
Click on a date/time to view the file as it appeared at that time.
885:
413:
copyrighted, dedicated to the public domain by copyright holder
794:|Date=2009-06-22 |Permission= |other_versions=Bitmap version:
197:
84:
860:
234:
http://creativecommons.org/publicdomain/zero/1.0/deed.en
280:
Add a one-line explanation of what this file represents
78:(SVG file, nominally 256 × 256 pixels, file size: 1 KB)
840:
128:
108:
Commons is a freely licensed media file repository.
911:Gebruiker:Niknetniko/Kladblok/Dichtste puntenpaar
240:Creative Commons Zero, Public Domain Dedication
798:}} <!--{{ImageUpload|full}}--> [[Catego
89:
891:Recherche des deux points les plus rapprochés
8:
41:Size of this PNG preview of this SVG file:
742:
276:
219:CC0 1.0 Universal Public Domain Dedication
851:Kurs:Fachdidaktik Informatik/Problemlösen
823:The following other wikis use this file:
876:تعیین نزدیکترین زوج نقاط در فضای دو بعدی
588:120742ed70c3028e512f55d9b9e19453b4a7df2f
202:
866:Problema del par de puntos más cercanos
810:
715:
699:
678:
662:
641:
625:
586:
570:
552:
536:
516:
500:
482:
466:
446:
430:
410:
394:
327:
311:
294:
291:
272:
265:
363:https://commons.wikimedia.org/user:Qef
214:This file is made available under the
7:
144:Closest pair of points shown in red.
808:The following page uses this file:
731:
285:
279:
138:
121:
71:
284:
270:
207:
201:
88:
31:
21:
267:
208:
139:
14:
813:Closest pair of points problem
266:
26:
1:
921:Задача о паре ближайших точек
519:original creation by uploader
931:Алгоритам две најближе тачке
847:Usage on de.wikiversity.org
449:Creative Commons CC0 License
292:Items portrayed in this file
959:
937:Usage on uk.wikipedia.org
927:Usage on sr.wikipedia.org
917:Usage on ru.wikipedia.org
907:Usage on nl.wikipedia.org
897:Usage on ko.wikipedia.org
882:Usage on fr.wikipedia.org
872:Usage on fa.wikipedia.org
857:Usage on es.wikipedia.org
837:Usage on de.wikipedia.org
827:Usage on ar.wikipedia.org
134:Closest pair of points.svg
732:
200:
163:
16:
831:مسألة أقرب زوج من النقاط
269:
95:This is a file from the
789:
179:
169:
159:
152:
149:
131:
99:. Information from its
102:description page there
941:Найближча пара точок
886:Principe des tiroirs
796:file:ClosestPair.png
600:determination method
185:file:ClosestPair.png
65:2,048 × 2,048 pixels
61:1,024 × 1,024 pixels
768:04:03, 22 June 2009
47:Other resolutions:
371:author name string
341:Wikimedia username
819:Global file usage
801:
433:copyright license
278:
252:
251:
190:
189:
117:
116:
97:Wikimedia Commons
32:Global file usage
950:
780:
720:
683:
646:
609:
604:
397:copyright status
378:
375:
365:
360:
350:
345:
247:
244:
241:
238:
235:
216:Creative Commons
211:
210:
205:
204:
198:
183:Bitmap version:
165:
155:
143:
135:
129:
113:
92:
91:
85:
79:
68:
57:768 × 768 pixels
53:480 × 480 pixels
49:240 × 240 pixels
43:256 × 256 pixels
958:
957:
953:
952:
951:
949:
948:
947:
817:
802:
786:
778:
734:
733:
730:
729:
728:
727:
726:
725:
724:
723:
721:
718:
708:
707:
706:
704:
693:
692:
691:
690:
689:
688:
687:
686:
684:
681:
671:
670:
669:
667:
656:
655:
654:
653:
652:
651:
650:
649:
647:
644:
634:
633:
632:
630:
619:
618:
617:
616:
615:
614:
613:
612:
611:
610:
605:
602:
593:
592:
591:
589:
579:
578:
577:
575:
564:
563:
562:
561:
560:
559:
558:
557:
555:
545:
544:
543:
541:
530:
529:
528:
527:
526:
525:
524:
523:
521:
509:
508:
507:
505:
494:
493:
492:
491:
490:
489:
488:
487:
485:
475:
474:
473:
471:
460:
459:
458:
457:
456:
455:
454:
453:
451:
439:
438:
437:
435:
424:
423:
422:
421:
420:
419:
418:
417:
415:
403:
402:
401:
399:
388:
387:
386:
385:
384:
383:
382:
381:
380:
379:
376:
373:
367:
366:
361:
358:
352:
351:
346:
343:
334:
333:
332:
330:
320:
319:
318:
316:
305:
304:
303:
302:
301:
299:
283:
282:
281:
264:
257:
245:
242:
239:
236:
233:
196:
191:
145:
133:
126:
119:
118:
107:
106:
105:is shown below.
81:
77:
70:
69:
46:
12:
11:
5:
956:
954:
946:
945:
944:
943:
935:
934:
933:
925:
924:
923:
915:
914:
913:
905:
904:
903:
895:
894:
893:
888:
880:
879:
878:
870:
869:
868:
863:
855:
854:
853:
845:
844:
843:
835:
834:
833:
821:
820:
816:
815:
806:
805:
800:
799:
788:
784:
781:
775:
770:
765:
761:
760:
757:
754:
751:
748:
745:
738:
737:
722:
716:
714:
713:
712:
711:
710:
709:
705:
700:
698:
697:
696:
695:
694:
685:
679:
677:
676:
675:
674:
673:
672:
668:
663:
661:
660:
659:
658:
657:
648:
642:
640:
639:
638:
637:
636:
635:
631:
626:
624:
623:
622:
621:
620:
598:
597:
596:
595:
594:
590:
587:
585:
584:
583:
582:
581:
580:
576:
571:
569:
568:
567:
566:
565:
556:
553:
551:
550:
549:
548:
547:
546:
542:
537:
535:
534:
533:
532:
531:
522:
517:
515:
514:
513:
512:
511:
510:
506:
503:source of file
501:
499:
498:
497:
496:
495:
486:
483:
481:
480:
479:
478:
477:
476:
472:
467:
465:
464:
463:
462:
461:
452:
447:
445:
444:
443:
442:
441:
440:
436:
431:
429:
428:
427:
426:
425:
416:
411:
409:
408:
407:
406:
405:
404:
400:
395:
393:
392:
391:
390:
389:
369:
368:
354:
353:
339:
338:
337:
336:
335:
331:
328:
326:
325:
324:
323:
322:
321:
317:
312:
310:
309:
308:
307:
306:
300:
295:
293:
290:
289:
288:
287:
286:
275:
274:
271:
268:
261:
256:
253:
250:
249:
223:
222:
212:
195:
192:
188:
187:
181:
180:Other versions
177:
176:
171:
167:
166:
161:
157:
156:
151:
147:
146:
136:
127:
125:
122:
120:
115:
114:
93:
83:
82:
40:
36:
35:
34:
29:
24:
19:
13:
10:
9:
6:
4:
3:
2:
955:
942:
939:
938:
936:
932:
929:
928:
926:
922:
919:
918:
916:
912:
909:
908:
906:
902:
899:
898:
896:
892:
889:
887:
884:
883:
881:
877:
874:
873:
871:
867:
864:
862:
859:
858:
856:
852:
849:
848:
846:
842:
839:
838:
836:
832:
829:
828:
826:
825:
824:
818:
814:
811:
809:
803:
797:
793:
787:
782:
776:
774:
771:
769:
766:
763:
762:
758:
755:
752:
749:
746:
744:
743:
741:
735:
703:
666:
629:
608:
601:
574:
554:image/svg+xml
540:
520:
504:
470:
450:
434:
414:
398:
372:
364:
357:
349:
342:
315:
298:
260:
254:
248:
229:
228:public domain
225:
224:
220:
217:
213:
199:
193:
186:
182:
178:
175:
172:
168:
162:
158:
148:
142:
137:
130:
123:
111:
104:
103:
98:
94:
87:
86:
80:
75:
74:Original file
66:
62:
58:
54:
50:
44:
39:
33:
30:
28:
25:
23:
20:
18:
15:
861:Aleatoriedad
822:
807:
739:
736:File history
484:22 June 2009
258:
232:
154:22 June 2009
140:
110:You can help
100:
72:
22:File history
255:Source code
132:Description
804:File usage
777:256 × 256
753:Dimensions
539:media type
329:some value
27:File usage
901:최근접 점쌍 문제
750:Thumbnail
747:Date/Time
628:data size
469:inception
194:Licensing
141:English:
573:checksum
273:Captions
164:Own work
841:Abstand
764:current
759:Comment
314:creator
297:depicts
277:English
124:Summary
76:
779:(1 KB)
665:height
643:1,365
206:
170:Author
160:Source
719:pixel
702:width
682:pixel
607:SHA-1
246:false
243:false
756:User
717:256
680:256
645:byte
150:Date
17:File
792:Qef
785:Qef
377:Qef
356:URL
348:Qef
237:CC0
174:Qef
603::
374::
359::
344::
221:.
63:|
59:|
55:|
51:|
45:.
112:.
67:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.