История изменений
Исправление slovazap, (текущая версия) :
У тебя тут два критерия - близость соседей и минимальность площади треугольника (потому что выпуклый N-угольник минимальной площади это треугольник), очевидно для начала тебе их надо как-то совместить, например перемножить.
При этом замечу что треугольник минимальной площади на случайном наборе точек с большой вероятностью получится с длинным основанием и минимальной высотой (три точки, «почти» лежащие на одной прямой), расположен он будет черт те как, и при этом будет ближайшим для большого количества точек, не смотря на то что расстояние до его вершин будет большим. Поэтому, с одной стороны, поиск его вершин не получится ограничить какой-то окрестностью, и честно это решается за N³logN (N базовых точек, для каждой 2 вершины ищутся перебором, 3-я ищется максимально близко к получившейся из первых двух прямой, можно за логарифм, с другой можно просто найти K треугольников минимальной площади за N²logN и выбрать для каждой вершины наиболее удовлетворяющий условию (ближайший * минимальной площади).
Это то что можно придумать по твоему условию, ты точно его правильно составил? Есть вероятность что ты написал чушь и тебе просто нужна диаграмма Вороного. Их диаграммы Вороного, если что, можно получить что-то другое, например из каждой ячейки выбрать тот же треугольник по каким-то там критериями.
Исходная версия slovazap, :
У тебя тут два критерия - близость соседей и минимальность площади треугольника (потому что выпуклый N-угольник минимальной площади это треугольник), очевидно для начала тебе их надо как-то совместить, например перемножить.
При этом замечу что треугольник минимальной площади на случайном наборе точек с большой вероятностью получится с длинным основанием и минимальной высотой (три точки, «почти» лежащие на одной прямой), расположен он будет черт те как, и при этом будет ближайшим для большого количества точек, не смотря на то что расстояние до его вершин будет большим. Поэтому, с одной стороны, поиск его вершин не получится ограничить какой-то окрестностью, и честно это решается за N³logN (N базовых точек, для каждой 2 вершины ищутся перебором, 3-я ищется максимально близко к получившейся из первых двух прямой, можно за логарифм, с другой можно просто найти K треугольников минимальной площади за N²logN и выбрать для каждой вершины наиболее удовлетворяющий условию (ближайший * минимальной площади).
Это то что можно придумать по твоему условию, ты точно его правильно составил? Есть вероятность что ты написал чушь и тебе просто нужна диаграмма Вороного.