Алгоритм?

← →
Добрый) (2008-12-30 14:39) [0]

Добрый день, подскажите пожалуйста как решить такую задачку:
Дана пятиконечная звезда с заданными координатами ее концов. Пользователь вводит координаты точки, и нужно узнать принадлежит ли точка звезде

← →
Добрый) (2008-12-30 14:40) [1]

P.S.
Желательно все это реализовать на C++, но если вы подскажите как это сделать на Delphi, то я переведу на сишку

← →
Palladin © (2008-12-30 14:46) [2]

точка пользователя x,y
находим самую верхнюю вершину полигона (звезды в твоем случае) xt,yt
считаем количество ребер пересекающихся с отрезком x,y,x,yt
если четное - точка не принадлежит полигону, иначе - принадлежит

← →
DVM © (2008-12-30 14:48) [3]

CreatePolygonRgn() + PtInRegion()

Или так (сделано для вещественных чисел, но переделать под целые не проблема):

type

TDoublePoint = record
x: Double;
y: Double;
end;
PDoublePoint = ^TDoublePoint;

TDPointArray = array of TDoublePoint;

function PtInPolygon(const Pts: TDPointArray; P: TDoublePoint): Boolean;
var
Cnt, I, J: Integer;
begin
Result := False;

Cnt := Length(Pts);
J := Cnt-1;

for I := 0 to Cnt-1 do
begin
if ((Pts[I].y <= P.y) and (P.y < Pts[J].y)) or
((Pts[J].y <= P.y) and (P.y < Pts[I].y)) then
begin
if (P.x < (Pts[J].x - Pts[I].x) * (P.y - Pts[I].y) /
(Pts[J].y - Pts[I].y) + Pts[I].x) then
Result := not Result;
end;

J := I;
end;
end;

← →
Сергей М. © (2008-12-30 14:50) [4]

> как решить такую задачку

"Конец" у звезды - это где ?
Это вершина ее луча что ли ?
Тогда никак.
Полигон однозначно определяется координатами всех его вершин, а не только "концов".
Пятиконечная зведа - невыпуклый полигон с 10-ю вершинами, из которых, если считать "концами" лучи, определены только 5.

← →
clickmaker © (2008-12-30 14:59) [5]

> "Конец" у звезды - это где ?

а у морской звезды есть конец?

← →
charoey_mag (2008-12-30 15:01) [6]

> определены только 5.

Остальные 5 легко расчитываются, так как они находятся на пересечении соответствующих отрезков. И определять принадлежность точки можно не сразу по звезде, а по 4 треугольникам плучющимся при ее построении, что есть уже достаточно тривиальная задача...

← →
Сергей М. © (2008-12-30 15:02) [7]

> у морской звезды есть конец?

Лучи точно есть - сам видел)
А конца у м.з. может и не быть)

← →
DVM © (2008-12-30 15:05) [8]

Через 5 точек можно провести бесконечно много пятиконечных звезд

← →
Сергей М. © (2008-12-30 15:06) [9]

> они находятся на пересечении соответствующих отрезков

Вовсе не обязательно.
И по условию это, кстати, не оговаривается, так что звезда м.б. любой.

← →
charoey_mag (2008-12-30 15:11) [10]

> Через 5 точек можно провести бесконечно много пятиконечных
> звезд

Может сегодня 30 и я уже не соображаю, но подскажите как? у меня кроме одной не получается, все остальное, плоской геометрической пятиконечной звездой назвать никак нельзя

← →
Сергей М. © (2008-12-30 15:13) [11]

> charoey_mag

Пятиконечных звезд разных - как в Бразилии Педров.

http://ru.wikipedia.org/wiki/%D0%97%D0%B2%D0%B5%D0%B7%D0%B4%D0%B0_(%D0%B3%D0%B5%D0%BE%D0%BC%D0%B5%D1%82%D1%80%D0%B8%D1%8F)

Ты о какой ?

← →
charoey_mag (2008-12-30 15:15) [12]

http://ru.wikipedia.org/wiki/Звезда_(геометрия)

Звезда — плоская геометрическая фигура, составленная из треугольных лучей, исходящих из общего центра, сливающихся в точке схождения.

ВОТ об этой

← →
DVM © (2008-12-30 15:21) [13]

> charoey_mag

вот звезда

http://images.yandex.ru/yandsearch?p=31&ed=1&text=%D0%BF%D1%8F%D1%82%D0%B8%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%B0%D1%8F%20%D0%B7%D0%B2%D0%B5%D0%B7%D0%B4%D0%B0&spsite=gym6.narod.ru&img_url=tmn.fio.ru%2Fworks%2F90x%2F304%2Fimages%2F004a.jpg&rpt=simage

и вот звезда

http://images.yandex.ru/yandsearch?p=25&ed=1&text=%D0%BF%D1%8F%D1%82%D0%B8%D0%BA%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%B0%D1%8F%20%D0%B7%D0%B2%D0%B5%D0%B7%D0%B4%D0%B0&spsite=antipunk.org&img_url=daket.ru%2Falbums%2Fuserpics%2F10001%2F2522168.jpg&rpt=simage

они разные, но внешние вершины вполне можно совместить

← →
Сергей М. © (2008-12-30 15:21) [14]

А чем это не звезда ?
http://ru.wikipedia.org/wiki/%D0%A4%D0%B0%D0%B9%D0%BB:Marshal_star_rod.jpg

← →
charoey_mag (2008-12-30 15:22) [15]

Поэтому единственное что надо проверить(если надо и не указано условием) это то что 5 точек образуют выпуклый пятиугольник

← →
charoey_mag (2008-12-30 15:22) [16]

Поэтому единственное что надо проверить(если надо и не указано условием) это то что 5 точек образуют выпуклый пятиугольник, иначе звезда не получится

← →
DVM © (2008-12-30 15:22) [17]

> charoey_mag

внутренние углы могут быть разные

> charoey_mag

Выпуклый пятиугольник не обязан быть правильной равнолучевой геометрической звездой.

← →
charoey_mag (2008-12-30 15:27) [19]

Я может че не догоняю, но что особенного во всех ваших выше приведенных звездах

← →
charoey_mag (2008-12-30 15:31) [20]

Оп, все понял. вы имееие ввиду что внутренние углы могут не лежать на пересечениях отрезков.
Тогда да в задаче мало сведений, хотя видимо все таки считается что внутренние углы лежат на пересечении

> хотя видимо все таки считается что внутренние углы лежат
> на пересечении

тебе виднее

← →
имя (2008-12-30 17:14) [22]

Удалено модератором

← →
Нат (2009-01-03 03:19) [23]

Более того, лучи могут быть разной длины и "ширины"

← →
Нат (2009-01-03 03:23) [24]

Залить внутреннюю область одним цветом, наружную другим.
Брать пользовательские коор-ты и проверять цвет точки.

Алгоритм? Найти похожие ветки