есть следующая задачка. найти все возможные пересечения в списке, которые содержит в себе "дороги", то есть объекты, состоящие из координат. нарисовал координатную сетку 8х8 и на ней 4 горизонтальные и 3 вертикальные линии. в коде это выглядит как то так
let rh1 =
road "rh1" [ // дорога содержит имя и список точек
point (1., 7., 0.) [BEGIN; COORDINATE]; // точка point (x,y,z) - координата, [] - содержит массив типов точки (не имеет значения в данном случае)
point (3., 7., 0.) [COORDINATE];
point (5., 7., 0.) [COORDINATE];
point (7., 7., 0.) [COORDINATE];
point (8., 7., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rh2 =
road "rh2" [
point (1., 5., 0.) [BEGIN; COORDINATE];
point (3., 5., 0.) [COORDINATE];
point (5., 5., 0.) [COORDINATE];
point (7., 5., 0.) [COORDINATE];
point (8., 5., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rh3 =
road "rh3" [
point (1., 3., 0.) [BEGIN; COORDINATE];
point (3., 3., 0.) [COORDINATE];
point (5., 3., 0.) [COORDINATE];
point (7., 3., 0.) [COORDINATE];
point (8., 3., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rh4 =
road "rh4" [
point (1., 1., 0.) [BEGIN; COORDINATE];
point (3., 1., 0.) [COORDINATE];
point (5., 1., 0.) [COORDINATE];
point (7., 1., 0.) [COORDINATE];
point (8., 1., 0.) [COORDINATE; TRAFFICLIGHT; END];
]
let rv1 =
road "rv1" [
point (3., 8., 0.) [BEGIN; COORDINATE];
point (3., 7., 0.) [COORDINATE];
point (3., 5., 0.) [COORDINATE];
point (3., 3., 0.) [COORDINATE];
point (3., 1., 0.) [COORDINATE];
point (3., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
]
let rv2 =
road "rv2" [
point (5., 8., 0.) [BEGIN; COORDINATE];
point (5., 7., 0.) [COORDINATE];
point (5., 5., 0.) [COORDINATE];
point (5., 3., 0.) [COORDINATE];
point (5., 1., 0.) [COORDINATE];
point (5., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
]
let rv3 =
road "rv3" [
point (7., 8., 0.) [BEGIN; COORDINATE];
point (7., 7., 0.) [COORDINATE];
point (7., 5., 0.) [COORDINATE];
point (7., 3., 0.) [COORDINATE];
point (7., 1., 0.) [COORDINATE];
point (7., 0., 0.) [END; COORDINATE; TRAFFICLIGHT];
]
далее вызываю соответствующий метод для получения множества всех возможных пересечений (должно быть 12) пересечений
let crossrods = Road.CrossRoads [rh1; rh2; rh3; rh4; rv1; rv2; rv3]
crossrods
|> Seq.iter (fun x -> printfn "position x: %f, y: %f" x.p.x x.p.y)
код алгоритма привожу ниже (весь тип не привожу, только то, что нужно)
let (|Includes|DoesntIncludes|) (point, list) =
let tryPoint = List.tryFind (fun c2 ->
if point == c2.p then
true
else
false) list
match tryPoint with
| Some(x) -> Includes x
| _ -> DoesntIncludes
static member CrossRoads2 r1 r2 =
r1.pl
|> List.filter (fun c1 -> match (c1.p, r2.pl) with
| Includes(_) -> true
| _ -> false
)
static member CrossRoads (roads: Road list) =
let rec inCross r roads res =
match roads with
| h::t when h.n <> r.n ->
let nextRes = Seq.append res (Road.CrossRoads2 r h)
inCross r t nextRes
| _::t ->
inCross r t res
| [] -> res
roads
|> Seq.map (fun x -> inCross x roads Seq.empty)
|> Seq.collect (fun r -> r)
|> Seq.distinct // это фиксит проблему двойного результата
код работает корректно, но результаты удваиваются, то есть итоговый список содержал дважды правильные ответы. проблема фиксится путем добавления
|> Seq.distinct
поскрипев мозгами, прихожу к выводу, что двойные результаты обусловлены тем, что алгоритм дважды проходит один и тот же путь (сначала он горизонтальную линии пересекает с вертикальной, а потом вертикальную с горизонтальной). думаю, что по идее проблему также можно пофиксить и мемоизацией, но:
1. оттого сложность алгоритма все равно не уменьшится. все равно сначала нужно получить результат, а потом смотреть мемоизацию
2. опять таки не совсем понятно, как эту мемоизацию в данном случае использовать и будет ли она работать лучше или быстрее дистинкта.
отсюда возникает вопрос, как можно все таки избежать мемоизации и одновременно не просчитывать один и тот же путь дважды?
ну и в принципе? как можно сделать алгоритм менее сложным.
спасибо
