Вычислительная геометрия: пересечение отрезков, точка в многоугольнике, выпуклая оболочка — авторское изложение

ru · official · sha256:d8496718126615548884a9886f17e0dd7490abb36a4df5ddbd1ddd0431e33a9a

§1. Ориентация тройки, вырожденные случаи и точная арифметика Псевдоскалярное произведение векторов (b − a) и (c − a) есть число, знак которого задаёт ОРИЕНТАЦИЮ тройки точек: положительный — обход против часовой стрелки, отрицательный — по часовой, нуль — точки лежат на одной прямой. Ориентация — единственный предикат, на котором стоят все четыре описания. Это не совпадение: почти вся плоская вычислительная геометрия сводится к знаку этого выражения, и точность его вычисления определяет правильность целиком. Вычисление ориентации при арифметике с ОКРУГЛЕНИЕМ ненадёжно: у почти вырожденных троек знак может быть определён неверно, и алгоритм получает противоречивые ответы — например, что точка одновременно левее и правее прямой. Следствие не «небольшая неточность результата», а нарушение инвариантов и отказ либо бессмысленный ответ. Поэтому изложение всюду предполагает ТОЧНУЮ арифметику над рациональными числами и говорит об этом. Вырожденные случаи в плоской геометрии — не редкость, а норма: совпадающие точки, коллинеарные тройки, отрезки, лежащие на одной прямой, точка на границе многоугольника, вершина многоугольника на луче. Описание, не называющее их, неполно; каждое описание ниже называет свои. Отрезок — множество точек между двумя данными концами включительно. Пересечение отрезков есть непустое пересечение этих множеств; оно может быть точкой либо отрезком, и второе бывает при коллинеарности. Многоугольник задаётся последовательностью вершин; стороны соединяют соседние вершины и последнюю с первой. Простой многоугольник — тот, у которого несоседние стороны не пересекаются; описания ниже предполагают простоту и говорят об этом. Выпуклая оболочка множества точек — наименьшее выпуклое множество, их содержащее. Для конечного множества это многоугольник, вершинами которого служат некоторые из точек. Соглашение о точках, лежащих НА стороне оболочки, — включать их в ответ либо нет — есть выбор изложения, и он обязан называться: два изложения, различающиеся только им, дают разные ответы на одном входе.

Ссылаются нормы: AnswersHere, f-04d552f27a1e6285f6fed2b2, f-06dbb15e80a35e27fecb79fe, f-09040e7db624ac98e6210f09, f-0a173221e90729ab3000b8d7, f-0bb3d4a263d364eba7dc37d3, f-0f756dc2233f563936e58898, f-1418ba460b8369c613d3ab82, f-28e333da76b32cd5e861e4af, f-323d184429358d0744f19bfe, f-331d103ec360ee5d7ea6edad, f-49314a7212efd3ec4bd6e475, f-4a0243ddc7f87c4d5dd56a27, f-51c68afd6fa3d3affc7016b7, f-57aa14b7df9bb45aa6e575d5, f-5c91042bdb28c3934bdfdef7, f-5d7a1307c97c6cc4cd3bf50e, f-5deeb3a6481c80a4201bb3aa, f-5ea2e6a74e00646d9ce2bbeb, f-6491fb6d35cad0b549d3888b, f-69f86138460b704821842bd8, f-6fb97d55d0f184c2e5ac0da2, f-8508865c236fac45dfdac746, f-9596db056bfb8e371ae4c24a, f-acdcd4a715fc38c52d4c148c, f-aec23da68eae7bb4b1426c37, f-c3f62b03794399f9e8ea52fa, f-c8563cd6d506b1e6f3f66537, f-e52c557942b060aea732e336, f-eba9aa02ffcafb3a13eb8266, f-f0973cfcc66a7ca769afbc0c, f-f3a5fe571f830776a730bed0, f-f9ee0f14b7b3f97cf4d625bc

ru · official · sha256:63002fa5236d7b013b93c947f18d54eb292becfd152091e403c9eb0a141026e2

§2. Пересечение отрезков Задача: по двум отрезкам определить, пересекаются ли они. Вариант — по знакам четырёх ориентаций с отдельным разбором коллинеарного случая. Вычисляются четыре ориентации: концов первого отрезка относительно второго и наоборот. Если ориентации в каждой паре различны и обе пары ненулевые, отрезки пересекаются в единственной внутренней точке. Если какая-то ориентация нулевая, соответствующая тройка коллинеарна, и требуется проверка принадлежности точки отрезку по координатам. Общий случай и вырожденный разбираются РАЗДЕЛЬНО, и это не усложнение: знаковый критерий сам по себе не отвечает на вопрос о коллинеарных отрезках, а проверка принадлежности сама по себе не отвечает на вопрос о пересекающихся крест-накрест. Основание общего случая: отрезки пересекаются, когда концы каждого лежат по разные стороны от прямой, содержащей другой. Утверждение принадлежит источнику. Крайние случаи: касание концом — ориентация нулевая, и ответ положителен; отрезки на одной прямой без общих точек — все четыре ориентации нулевые, и ответ отрицателен; вырожденный отрезок из одной точки — сводится к проверке принадлежности точки отрезку. Повторения в описании нет: число шагов постоянно. Отсюда и постоянная стоимость.

Ссылаются нормы: f-0102a49636c283bf0ae1ebbd, f-019336b89a9078d65bc1ae29, f-0260b40d9ba30c18d8208641, f-03d261e0feb17bc1de7b8262, f-04bce60f228ebb9041aea116, f-07e018c01b8f25c611356b1e, f-082cb91f88571815ed8f44ef, f-0a885558f9cd36234fe4c265, f-13610e29a06f4a845f692aa6, f-13da61414a7f83b2d35aeb02, f-14a54585404a608356ae629c, f-15c1ee9aca547313d3e7ac56, f-1a3a90d8d32c477b0de44b59, f-1d718effaf5124f552d60217, f-1d9c6c2ed90814f2c6a23fdb, f-206d6fb79ddea2baaa069712, f-224c7469c3b1f3d7939937e4, f-229221912da0f94915d26b01, f-24a416b5c456174d0d435e6e, f-2d68e3ce4f0468eb473dfcb0, f-2ed7a007e4e2e2dd9dd0cd9f, f-34121b5706a7f97694ece9df, f-39a1ff4f5467b87254f73c89, f-413c1bb927344492c259748a, f-44b479fc1352d76aae026189, f-44cb08e155d0b2130ae3b3c2, f-473f80d7f9a4641d3465e128, f-49d7b4b7aadb659e099fcb6c, f-4c1c7f2ab7677da336d0e429, f-5036e6034632c41f5f2cc0c7, f-539c08395beaf82e9e412ffd, f-5b5d83571f4dbfa691f52c6f, f-60c20b28da6129d598744581, f-66dc41b86c3acdce7da6470e, f-67f8d7119eee4b9984142797, f-68a3c67c134b774b6e75094b, f-6969c18c4d4201b3abb617f9, f-6ab3c1a0139eb0f9af21066a, f-7376ed7e7d5596f59ac6bc3f, f-77377e99315f3c6e3f959119, f-7c49039de473638fd2f72501, f-7c8e3a09fb907a10ed321bad, f-7e67d4cfe8e8932a97d0e0e9, f-7fa49aeb0a881846a850a415, f-83c6916a1144611a2f3e11ff, f-84c9f505c86d07e4d1a3dc80, f-86422fa7cc0e4159286f86aa, f-88c4d69f2398dd3c1ac24fa8, f-8e9b88ee2423a39f24931a82, f-8efaa033b1b2030868c42f2e, f-9039591655d5c0c7b9ae86d0, f-90fc2f5c76e2cc18f268323d, f-93db0ebd39c60877364b66d6, f-94ce501b5b00077ef61c7da5, f-95c64c9db989a316825f6abf, f-976887bb9ba99d1aa2fc29a6, f-9ee6c54aa7b60910f375d294, f-a49dd84d7b4e84f4d014f8cb, f-a711b89a57fa9c829613c678, f-aa3e076fe6204d215b26505c, f-b32edd276861f51097490121, f-b81b7f6f031eb303f6e7afc7, f-b91930a14b6627f9f911c06a, f-ba32aad1eea474ae58ddae98, f-c1e983cce5a8e8a1a46b7863, f-c52b92515e710c2ad1b7ee8a, f-d4e35d16ba660fe25f78ccc7, f-d5a568b52e41ee31cc7b4faa, f-d702c489747fb371cbf15ccb, f-d92c5f4b6ddf296049361181, f-d9a9cfb27e2edfe5a1396afe, f-dc9c3c1075a78b4c7ddd320a, f-de886359e24bb2f52b2858c2, f-e2ef9d94d6c708be7dedc874, f-edcb903add41f5e0435db87a, f-ef8e6ac91140edbb771b44f9, f-f34442edf358b92232e94c6e, f-f6193fe936106de9352fd692, f-f98cb92257851cfa9a432dff, f-fecb08112b034b0d03f85d6b

ru · official · sha256:de248805e64d2e8aa082f9ae7bf780a96a382f24375fe5df7242313a65a527f8

§3. Принадлежность точки многоугольнику методом луча Задача: по простому многоугольнику и точке определить, лежит ли точка внутри. Вариант — луч, выпущенный из точки в одну сторону, и подсчёт ЧЁТНОСТИ числа пересечений со сторонами. Из точки мысленно выпускается горизонтальный луч. Перебираются стороны многоугольника; для каждой проверяется, пересекает ли её луч. Точка лежит внутри тогда и только тогда, когда число пересечений нечётно. Основание — теорема Жордана о кривой: простая замкнутая кривая делит плоскость на внутреннюю и внешнюю области, и всякий луч из внутренней точки пересекает кривую нечётное число раз. Доказательство остаётся в источнике. Главная трудность метода не в идее, а в ВЫРОЖДЕННЫХ случаях, и они обязаны называться. Вершина, лежащая на луче, засчитывается один раз, а не дважды и не ноль раз; для этого условие пересечения делают несимметричным по концам стороны — один конец включают, другой нет. Горизонтальная сторона, лежащая на луче, не засчитывается вовсе. Без этих двух правил метод даёт неверные ответы на обычных данных, а не на редких. Точка НА границе — отдельный случай: метод луча не отвечает на этот вопрос, и его надо проверять до основного цикла. Возврат «внутри» либо «снаружи» для граничной точки есть выбор изложения, а не свойство метода. Оценка: одно прохождение по сторонам, то есть время порядка числа вершин, память постоянна. Выпуклости от многоугольника не требуется — этим метод и ценен.

Ссылаются нормы: f-0705149e11a3ae3028361632, f-08027864dc709bc28f61508a, f-0a0d5d590d3689fac40913ad, f-0d6a3d6afa7df7a87f2f61fa, f-0e8e5146c74aff7b8f3c5c73, f-0f003261280e28cbdd3cf9fb, f-0fe714e2a8d353ad1dd428e8, f-15c296a63fb398dac85ad296, f-185e05cd736b4e7bdd26a824, f-19d4d6a5a069262822b1ad34, f-1ac066927cf6908e88ff746f, f-20674b737d40ba3007ef74ff, f-20ac75f4767ca018777604e0, f-23dd42ef6f4ce7027cd28929, f-2556d1c9ac19c8ab42174abe, f-25ae09538893e128ca8f0736, f-25f068f4a774467de1dadc52, f-2cf859ab2e5d0e4669cdff4b, f-2f53a93e8ce604724899e563, f-3313c95aeb49dc0fe1bd4aad, f-3748f71147d0d2a6bd6b2e0f, f-37f0486649a13d3c2df8fed4, f-38504059b8087382e2b6f148, f-3c8a23ee0d7c64da3d6f61c6, f-3d043e695add134c67188161, f-44d241ab1050f1fc624c72a2, f-48b64acc0402e627a5503d35, f-4d45199b187cf246dfeece44, f-4e51c5471e4b19c0b0c2a8e8, f-50bfe8971ac3f75cb27eda54, f-54bf7b0c8932d92cf41dbd5c, f-54d3898d93ebff00b019de34, f-565be88725cc1fec3dc688a6, f-5af486bdc34ae460c495a338, f-5e2a0a16897fd7b370c1f7ec, f-62117f759332cbf2e4e44cee, f-682817c5c875396fde9050cc, f-6b804f731bc466e15ee7e297, f-6c264d87640df569aff5b122, f-6dffcc8ef816e10ae39747df, f-759f3d823df1b02fb552518f, f-78b3340364fd66e8a08cde06, f-7a9ba53676b9187c42690c00, f-7e5e8307b03641a1a91a0aa7, f-7ff183baad284958bd408aca, f-8995c46178d63e5951a92b57, f-8d6a54abef16283436c2c855, f-8e44ff3dc3e5f9df75b85be0, f-8f132bdbc6b28dab03e04ff0, f-90a115a8bfbf41e820fa761b, f-950496d4c7babdeef2995cc5, f-95a5c4d1aed8c2666e85f6c2, f-9a3a27c2283d118ec009bd6a, f-9a8c48ad03d7ab826f3c0f44, f-9acb25d41fda93880ee47225, f-9c999e5039db1a10a164a1f6, f-9d234c0a073fe25601b1c471, f-a2604b0cb585346009d0aaef, f-a491ea91712bf5384afd457b, f-a6d8352b568c714654f281f2, f-ac4a4b43f961a895d01b494a, f-ad1f26b14d213b949bea3b0a, f-b06fa05d44a4e8875c73d1f5, f-b2351af6c8cc0a7452d8fbcd, f-b31fadade9a5a172469755fe, f-b7828742a41d08eec41972a5, f-bbfc0191bb17252c29de240f, f-bdfc66116dbc2b8a973a8b46, f-be17f84818ca0bfdb9a3408d, f-c08b1baebac53600158d7f65, f-c0f9b846c29695dbe6b3d55c, f-c26b1fffa52796b1580fa629, f-c33294128240b08fb93baa63, f-c397303d7d6f7c67c6856a55, f-c4ca103dd0e7e31da6e77f2d, f-c770b4d9b8f5e70ca03a5a5a, f-c9c31bf29abf2ef5c77f8140, f-ca8180dd1e96361631a305ff, f-cc513c89b71519b30c28e009, f-cc730f86cbe775bbedb80e60, f-cc784fd94665c06dd731c1ed, f-cea2ca1ae623c7c84e73ae24, f-cf20e1daeabfb8ca3081afe3, f-d0c7eeb181be7d61a13c4fbc, f-d1ab2197e8d081ee68dd0eca, f-d914aac7b3be7751d621695d, f-d96349ee41fcffbafeeff628, f-dc47bebaef1cf7b471245efb, f-ddaa8f6d3fdbab493616b427, f-de87b9c72737aeeef5726acf, f-def1ddb4df2b4fae13374063, f-dfe1773e25d30807a50f9b12, f-e7a41f8dc15f12eca16d7794, f-e8b2ff99e54d48b6148b5c36, f-e8cab427fbcc0262e08e356e, f-ef32cd1c8f3a8074d225ab82, f-efd399bfb88609521e50928b, f-f1a3caeec819449605672caa, f-f466b0716c4f9e2bc12d1f54, f-f48316812fa57da16a5f6274, f-f62dce4c62a91e3d70d70133, f-fabfd1f579c1f2cae6dd931c, f-fbcc7a2ba61601f3b55bdd42

ru · official · sha256:df650487058f510c43d995c71a2fcf38a6195a6a91b95887d9532ce83ea41837

§4. Выпуклая оболочка обходом Грэхема Задача: по конечному множеству точек построить его выпуклую оболочку. Вариант — сортировка по полярному углу относительно самой нижней точки и однократный обход со стеком. Выбирается самая нижняя из самых левых точка; она заведомо принадлежит оболочке. Остальные точки сортируются по полярному углу относительно неё, а при равных углах — по расстоянию. Затем точки просматриваются по порядку: пока две последние точки стека вместе с очередной образуют НЕлевый поворот, вершина стека снимается; очередная точка кладётся на стек. Основание снятия: точка, при которой обход поворачивает не влево, лежит внутри треугольника, образованного соседями, либо на его стороне, и вершиной выпуклой оболочки быть не может. Инвариант: содержимое стека есть выпуклая цепь, идущая против часовой стрелки. Совпадающие точки и коллинеарные тройки — вырожденные случаи, и оба обязаны называться. Точки, совпадающие с начальной, удаляются заранее. Точки, лежащие на одной прямой с начальной, обязаны быть упорядочены по расстоянию, причём для САМОГО ДАЛЬНЕГО угла — в обратном порядке, иначе обход срезает часть оболочки. Мера убывания: число непросмотренных точек убывает при каждом помещении на стек, а число снятий со стека суммарно не превосходит числа помещений. Отсюда линейность обхода после сортировки. Оценка: сортировка порядка n·log n определяет стоимость; сам обход линеен.

Ссылаются нормы: f-00d659fc39ebb43a012f455e, f-06daad9c43cc240ffbca9a3e, f-07553005277ace63e5e22d09, f-07ef475b5d5b2581535c179b, f-0f6b799cebe15ddaa438cfd2, f-1227b3f24dd6b6635f615b8c, f-1b53cb9232785c866ddcef27, f-1b9870142b076a5d6fb2caef, f-1c774bb252c108d90d00b24a, f-1db8c8c5596d8be0ac6766ca, f-1e83403000baed8de7cadd3c, f-1ef64fa6db3f33b5c62fc073, f-22add44b2d438c23f53176d1, f-289c3d52c3e5056952cdc473, f-2b009d326e05b11bddce45b4, f-2b6fe322119aee594374edf1, f-2dab47d8cc56e306238e4438, f-3064d7427a44f3729e204969, f-3469bbbcdfa3a2baf04d8e1f, f-34c88f84dfbab5ea1a3e33c7, f-381fadc81637618dd4b130ad, f-384390ac96ed200959b88b6e, f-3b133f8d3985ff09399c1088, f-3c7378d22975f0ec817f45db, f-3ca2238d8450dc532765d706, f-3e52082153e2669eb6e234bc, f-3eda2a12e330e1b81ae3ef5c, f-3f026fddf229b260c8350266, f-44d4c942c2a2af5237319f3e, f-47775045da36d7c9c77205d1, f-47995fcf77a598ca5e8f85d5, f-4e5971a557a3f4d9b096a952, f-4f35b463f02387e45d541a2e, f-51e4859e620ffc3db4898767, f-58ab83d9ae315bd039b0487b, f-5f15bdbf2b6efa6a2f4c5755, f-619b39a6b666f2c66d988d41, f-61a133acacdce164e02bf448, f-66081fa544a939da6037990a, f-672affdef639666a22dff402, f-677c4fb5388328568e73a3ba, f-691dab41b89113a97150bbd4, f-6ad4b3a0201728573cfae793, f-6e060dfbd7f770ac92e3d943, f-7d134bac6e057676519b0348, f-7ea1a55338b7897ffd34af72, f-7ea47e8d355b583a8da1cf7e, f-81a3f6fb68cf55f7118a6ff2, f-81faaa6c75fae6b701b1dd83, f-8279beb7a00bf3089c31ff76, f-837e8fe0088067f5a90e1bc5, f-858898939f39239fb0d45fb3, f-8a28439ca839added4a62518, f-8b888bcb13f2519c05d450ec, f-8cd3823486d2b803b9c96640, f-90bc95e2e0c1d5d57031c5c8, f-93adeab6ff45a5fc95d1d0e8, f-9644f69e7cc8feaa7bde2da6, f-982a97b1501ec6274c251854, f-a156703bf871a3d0daea1901, f-a4782d0609f14eafad484230, f-a4f19862330bcc17b3893e4d, f-a660a845ce358708afe9a629, f-a98d45f846c5f9da852c4a95, f-a9f2f14f904a45b95e494709, f-ac4f17649df90c69ae2cc3d3, f-ac68dc53e96b581251adda6c, f-b0f97174a2f48a0c07fe6986, f-b2a41e48b4eb950a601dabb2, f-b42dfdf719dcc017aaaf0c5b, f-b4ce0cf099977d0c09c4e799, f-b7682560ded45140824c227e, f-b83a46053ecbdea6d1803f88, f-be85d75fb4e1284256ee6e0d, f-c14643c616731f1691f77f36, f-c8388f05d36cfd8743871d18, f-c8b03b082249899cfd234e11, f-cab791850225fecd61c9ee29, f-cae6c5ce451b0dbaab5fc18c, f-cf03f90ab89951db6502fb0d, f-d093943ff92f7dc499deca1c, f-d139839a0a2bdf5960ebb5ec, f-d18124b027f3eb24e53493ea, f-d1e720aa689d3e4c2d075855, f-d9e7e05ea5edd8cd6256d870, f-dab7ea6c94a1e2214ad09cbd, f-db3d5af80ad4e3107d0bfa86, f-df060b7155de41735e4b25e2, f-df9dfe65749e5630d9fd897f, f-dfc335a466b546c803409488, f-e1b6821e3ce5c7c5b96446e2, f-e3a040169eafe98ce7706390, f-e96fcca68aed70dc78fbd8b6, f-eb9e90334c1ea2590ed417e1, f-ecbcc35e8d302d6570ca5b0a, f-ed4b9781ff9694463693b6df, f-edb1b4cbe8c991b7686b24ba, f-f3f54db33405543b66f3a9bb, f-f3fa46005a22f95314ede95a, f-f49d5ced3f99b3fe45b48980, f-f6f23e2c22fd78e319b67a10, f-fc36efd590cef06dae49ab46, f-fde598d53b508770b8249138

ru · official · sha256:0402cd294206b75d4f5444548f4c4b575c425ffdfdf5ccdfab3ac37eff4bc2cf

§5. Выпуклая оболочка монотонной цепью Эндрю Задача та же. Вариант — сортировка по координатам и построение нижней и верхней цепей двумя одинаковыми проходами. Точки сортируются по абсциссе, при равных — по ординате. Затем строится нижняя цепь проходом слева направо с тем же правилом снятия, что в §4, и верхняя цепь проходом справа налево. Оболочка есть их соединение с удалением двух повторяющихся концевых точек. Отличие от §4 состоит в сортировке: по координатам вместо полярного угла. Это существенно на двух основаниях. Первое: сравнение по координатам не требует ни деления, ни тригонометрии, и потому точная арифметика проще. Второе: вырожденный случай «много точек на одном луче из начальной» исчезает вместе с самим понятием начальной точки. Инвариант каждого прохода тот же, что в §4: строимая цепь выпукла. Крайние случаи: менее трёх точек — оболочка вырождена, и это надо предъявлять отдельно; все точки на одной прямой — обе цепи совпадают, и результат есть отрезок; совпадающие точки — удаляются при сортировке. Оценка та же, что у §4: сортировка порядка n·log n, два линейных прохода. Различие вариантов — не в стоимости, а в устойчивости к вырожденным случаям и в простоте точной арифметики; это и есть основание выбора между ними.

Ссылаются нормы: f-022486c6445d5118d83fa869, f-04ea1bd586746804213cf19f, f-05ffd00db2adf3cff1623647, f-123343634d3edeaa07b0d293, f-1442f996b836696d17246d52, f-16c259f87c8590b2830fa1e6, f-1b34e71fbed387a0d7333f2b, f-1b3592798435217048e4dc28, f-1e711f08403f7663a357ab68, f-2e952e3b47cd2fde21eabd51, f-38733e18048dfe395dc54c87, f-39260378b644f33a98170d1f, f-3a9714e3e1baf6a6b28d48eb, f-3fc450165185247630f04dbe, f-3fd9eceaea6e1b348111241b, f-432edb3133376391454cbba8, f-43f756212a4c87601f1a8e56, f-440a788f0248d16c9b3b9290, f-454bf64ca35f9d448b82780b, f-46eafd3ddf32787b45080a4c, f-48196498f0b1a31febba0f95, f-4a8c167411ffc50bf4c50d61, f-4a9e70500127cd993b4d3ebb, f-4fae2302673fe632e71998e8, f-54aa0344b609a32afd47040b, f-58b040e4d7b117481f18d347, f-58f5966c439c2a97133cea6d, f-5d46a2f23c585d74c8c5f7a3, f-5dee979a9e7ccb87c14a8aa3, f-6b54fa4d06bda72d300c6fc9, f-6d210e4c67988ac0eb6ace3a, f-6f5eec04758e37584758e3d8, f-799764f005d5e244de7024d1, f-7af81142aeb8ce2c94e67321, f-813dccc7c8b537da3adf1872, f-867ff21e6084058cd195b842, f-8695d49673713413f5790ff6, f-88818e888bc6687054970538, f-8a25ec2110e44e21a20686ef, f-8aa1da3637f2f142af339f88, f-8b7a3ab26e9ed5a96ed35343, f-919856cbded44f2d32ec3f2c, f-97e0d6436020a70e30645eb3, f-99022ca99f61e9ebc85623db, f-9b271168bfc9eb995dec390b, f-9d090100f7009ebe54bc22a6, f-9db1a52017a876eb36f489df, f-9db2e89bab469f8a1e4219db, f-a2c05e3f2f89ef0626746989, f-a2c1a28344372c846365c43c, f-a50527dde69ff60636d39e5c, f-ac0f9b896278da5b9cf497e4, f-b51d1216947e79ddc28c2973, f-b7ec01632d4c58a31e386aa7, f-b85b0bb8a42b6f6265643d71, f-c3fc90a7329069022c252df2, f-c7b515e4407c2e210f08667b, f-c9a0e6c51bf091b5e6efb93e, f-c9b6a841ad028458d81b06d7, f-ca5600f71c7c09121df924e7, f-ce6916a0acc94d439ff5d901, f-cf629e2d886f237f9c151d93, f-d6ba8c1dd4fb4b9aeb3188b8, f-d955db2c41334eb1aa0e7603, f-d9a773bb76eaa6da3b701dda, f-dc83432e68f861f3bfab60c3, f-e2c3ff7bfbe80156e1c3f5b1, f-e847a5c2e7dffd58a3d7dddc, f-ed152a48b8bb9a2de0f3a14a, f-f5b38c7b3c38474de7a517a9, f-fcd5dc48f099b442f5c8ed06, f-fdf1ea98cf2ac5caa3207a04, f-fe0a9182d5ca690601dfb2a0, f-feea9d1f5e7b264a3ad5758d

ru · official · sha256:2370a02440f022403f08b7e8d14b688049603fbc33ee52eebc640dacc9c0ac83

ВЫЧИСЛИТЕЛЬНАЯ ГЕОМЕТРИЯ: ПЕРЕСЕЧЕНИЕ ОТРЕЗКОВ, ТОЧКА В МНОГОУГОЛЬНИКЕ И ВЫПУКЛАЯ ОБОЛОЧКА Настоящий документ является АВТОРСКИМ ИЗЛОЖЕНИЕМ, составленным для целей формализации. Он описывает устройство четырёх алгоритмов: проверки пересечения двух отрезков, проверки принадлежности точки многоугольнику методом луча и двух построений выпуклой оболочки — обходом Грэхема и монотонной цепью Эндрю. Изложение не воспроизводит ни один учебник; происхождение каждого алгоритма названо при его описании локатором. Описание отвечает на вопрос об устройстве алгоритма и не выполняет его: ни одна точка здесь не обрабатывается.