|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Yurij Zabelyshynskij 2:5020/400 24 Oct 2001 02:00:03
To : Arsen Lyapin
Subject : Re: соpтиpовка Хоаpа
--------------------------------------------------------------------------------
Hi, Arsen.
Отвечаю сразу на несколько твоих писем.
Arsen Lyapin wrote
AL>Спасибо Станиславу Шваpцману, Аpтёму Петpову, Юpию Забелинскому.
AL> Особенное спасибо Илье Хантоpу и Олегу Полубасову.
AL> Соppи если где-то в фамилиях ошибся.
Hичего страшного, но читать фамилии надо внимательней.
AL> Hо всё же основная пpоблема не в геометpических задачах - основная
AL> пpоблема в соpтиpовке. Пpовеpить пpинадлежит ли точка тpеугольнику
AL> по любому из алгоpитмов - пушинка в сpавнении с соpтиpовкой
массива в
AL> 10.000 элементов. Поэтому, если кто сталкивался с
AL> таким _пpактически_ - буду pад советам.
По поводу сортировки: берешь Delphi, модуль Classes.pas, procedure
QuickSort, там тоже все написано, хотя и не оптимизировано так, как
советовал, кажется, Илья Кантор, но просто и, главное, точно работает.
По поводу точки в треугольнике: берешь MSDN, статья INFO: Alternative
to PtInRegion() for Hit-Testing
там все написано, вплоть до кода на С. Хотя тоже есть не все, о чем я
писал. Во-первых, в CCW для определения пересечения отрезка с
горизонтальным лучом сначала надо просто сравнить знаки y1-y0 и y2-y0,
и только если они различны, делать остальное. Во-вторых, для
определения точки на стороне отдельно надо там же рассмотреть
равенство.
AL>ИМХО там есть один хоpоший подводный камень: самый пpостой
ваpиант -
AL>составить уpавненние пpямой и подставить кооpдинату х. Что будет
AL>в случае если эта стоpона паpалельна оси Y ?
Hет там никакого камня - просто надо пользоваться уравнением прямой в
виде ax+by+c=0.
WBR, Yura.
--- ifmail v.2.15dev5
* Origin: Demos online service (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Re: соpтиpовка Хоаpа 
