File:Megiddo's minimum enclosing circle algorithm prune stage.png

From Wikimedia Commons, the free media repository
Jump to navigation Jump to search

Original file ‎(1,085 × 812 pixels, file size: 226 KB, MIME type: image/png)

Captions

Captions

Run of Megiddo's algorithm phase, discarding from point set A,B,...,U needless points D,M.

Summary

[edit]
Description
Čeština: Z os dvojic (A,B), (C,D), ... , (S,T) orientovaných dle rostoucího x byl určen mediánový směr odpovídající červeně zobrazené ose dvojice (C,D).

Osy byly spárovány tak, aby červený směr byl mezi směry os v dvojici a nalezeny průsečíky W,Z,A1,B1,C1. Modrá rovnoběžka s červenou osou procházející bodem B1 rozděluje tyto průsečíky tak, že v každé polorovině jsou 3. Výsledek hledání nejmenší kružnice se středem na této přímce, obsahující body A,...,U určí, že střed nejmenší kružnice bez omezení leží v "dolní" polorovině. Proto je zvolena modrá kolmice procházející bodem A1 (rozděluje průsečíky A1,B1,C1 horní poloroviny tak, že v každé polorovině jsou 2. Výsledek hledání nejmenší kružnice se středem na této přímce, obsahující body A,...,U určí, že střed nejmenší kružnice bez omezení leží v "levé" polorovině. Proto z os určujících body A1 ((C,D),(O,P)) a C1 ((M,N),(G,H)) můžeme vybrat po jedné a z nich, (C,D), (M,N) garantující který bod z bodů určujících osu je blíž středu hledané kružnice, ať je v příslušné čtvrtrovině kdekoli.

Hmm, toto osa (M,N) svírá s červenou přímkou špatný úhel, takže odstranění bodu M není korektně zdůvodněno.
Date
Source Own work
Author Hippo.69

Licensing

[edit]
I, the copyright holder of this work, hereby publish it under the following license:
w:en:Creative Commons
attribution share alike
This file is licensed under the Creative Commons Attribution-Share Alike 4.0 International license.
You are free:
  • to share – to copy, distribute and transmit the work
  • to remix – to adapt the work
Under the following conditions:
  • attribution – You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
  • share alike – If you remix, transform, or build upon the material, you must distribute your contributions under the same or compatible license as the original.

File history

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

Date/TimeThumbnailDimensionsUserComment
current08:55, 4 March 2019Thumbnail for version as of 08:55, 4 March 20191,085 × 812 (226 KB)Hippo.69 (talk | contribs)User created page with UploadWizard

You cannot overwrite this file.

There are no pages that use this file.

Metadata

This file contains additional information such as Exif metadata which may have been added by the digital camera, scanner, or software program used to create or digitize it. If the file has been modified from its original state, some details such as the timestamp may not fully reflect those of the original file. The timestamp is only as accurate as the clock in the camera, and it may be completely wrong.

Retrieved from "https://commons.wikimedia.org/w/index.php?title=File:Megiddo%27s_minimum_enclosing_circle_algorithm_prune_stage.png&oldid=915000164"