|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Sochenko Alexander 2:4651/18.69 06 Jun 2002 06:37:00 To : Konst Arnautoff Subject : Точка вHyтpи фигypы --------------------------------------------------------------------------------
Ср Июн 05 2002 09:45, Konst Arnautoff (2:4625/44.7) писал All:
KA> Имеетcя замкHyтая фигypа Hа плоcкоcти c кооpдиHатами веpшиH
KA> array point[Count](x,y) и пpоизвольHая точка A(Xa,Ya).
KA> Hеобходимо опpеделить Hаходитcя точка вHyтpи фигypы или cHаpyжи?
Для выпуклого многоугольника обходишь по ребрам. Если проводишь прямую
через ребро то тогда вся фигура лежит по одну сторону от этой прямой.
Чтобы определить по какую сторону лежит твоя точка нужно восстановить
перпендикуляр (вектор2) к проверяемому ребру (вектор1). Вычисляем
вектор на данную точку (вектор3). Скалярное произведение
вектор2*вектор3 будет давать положительные или отрицательные
значения (смотря как обходишь фигуру по часовой или против и
как делаешь перпендикуляр) для точек лежащих в/вне полуплоскости фигуры.
Обойдя все ребра получаешь ответ: точка лежит вне фигуры, если
хотябы раз лежит вне полуплоскости фигуры (по другую сторону от
прямой проведенной через ребро).
Для невыпуклой фигуры разбиваешь ее на выпуклые фигуры и далее
по тексту. Определить невыпуклость можно тоже при помощи
скалярного произведения векторов.
С наилучшими пожеланиями,
Sochenko
--- -=-
* Origin: (Sochenko Alexsander 2:4651/18.69)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/161673cff0683.html, оценка из 5, голосов 10
|