Плоскоть и точки

Множество, как я понимаю, конечное?

>>Множество, как я понимаю, конечное?

Да

А к треугольнику какие-нить требования есть (минимальная площадь или периметр)?

я бы делал перебор по всем возможным треугольникам. Единственно -- оптимизировал бы действия которые нужно делать для каждого треугольника -- нужно уметь быстро определять сколько точек внутри -- ну или сколько точек по одну сторону от прямой -- для этого хранить точки в какой-нибудь структуре типа k-d-tree

Я уверен, что только перебором. Предварительно упорядочив набор точек, например по произвольной координате, чтобы предотвратить повторения.

Если нужно просто обрисовать треугольником все точки, то наверное, можно найти самые верхнюю, нижнюю, правую и левую точки, и что-то мне из геометрии вспоминается про вписанный прямоугольник...

что значит треугольник содержал количетво точек? Считаются точки внутри треугольника или только тольки на ребрах?

>>что значит треугольник содержал количетво точек? Считаются точки внутри треугольника или только тольки на ребрах?

В треугольнике внутри него, содержится наибольшее количество точек

>>Если нужно просто обрисовать треугольником все точки, то наверное, можно найти самые верхнюю, нижнюю, правую и левую точки,

Не факт, что треугольник из этих точек будет содержать - > наибольшее количество точек

Ну если на плостости то по моему факт, надо найти самую левую/правую вернюю, самую левую/правую нижню получаем прямоуголькик который захватывает все точки. Теперь собтвенно задача из из 4-х треугольников выбрать правильный. По моему это будет работать с хорошей вероятностью.

> Ну если на плостости то по моему факт, надо найти самую левую/правую вернюю, самую левую/правую нижню получаем прямоуголькик который захватывает все точки. Теперь собтвенно задача из из 4-х треугольников выбрать правильный. По моему это будет работать с хорошей вероятностью.

кто-то не понял условие задачи. По моему условие звучит так: есть конечный набор точек. Среди всех треугольников с вершинами в этих точках нужно выбрать такой который содержит (внутри себя и возможно на ребрах) максимальное число точек из набора. Здесь нельзя ограничить перебор треугольников четырьмя. Нельзя даже ограничиться треугольниками вершины которых лежат на границе выпуклой оболочки набора. Реально нужно перебирать все треугольники, но за счет организации точек в подходящую структруру данных можно ускорить вычисление кол-ва точек из набора лежащих внутри треугольника.

Для on-line 2D simplex range search есть простые структуры с O(n^2) preprocessing и O(log n) query time. Итого выйдет O(n^3 log n).

>>Для on-line 2D simplex range search есть простые структуры с O(n^2) preprocessing и O(log n) query time. Итого выйдет O(n^3 log n).

Так объясните мне, что мне читать, а то я о чем речь идёт НЕ ПО - НИ - МА - Ю.

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

Будь добр, поясни как можно оптимизировать. Для точек делал структуру с участниками x, y и потом массив структур.

гугли по словам triangle range search

ну и вообще почитай книжки по вычислительной геометрии. Есть русский перевод Препараты, Шамоса

>>гугли по словам triangle range search

>>ну и вообще почитай книжки по вычислительной геометрии. Есть русский перевод Препараты, Шамоса

О, Спасибо. Погуглю. Книжку эта есть, читаю, спасибо ;-)

Однозначно задача решается перебором.

если напрячь мозги то будет очевидно что не стоит перебирать вообще все возможные комбинации на всём множестве точек а достаточно только некоторые на ограниченом множестве точек

> точек а достаточно только некоторые на ограниченом множестве точек

ИМХО вообще стоит перебрать только крайние точки.

> кто-то не понял условие задачи. По моему условие звучит так: есть конечный набор точек. Среди всех треугольников с вершинами в этих точках нужно выбрать такой который содержит (внутри себя и возможно на ребрах) максимальное число точек из набора. Здесь нельзя ограничить перебор треугольников четырьмя. Нельзя даже ограничиться треугольниками вершины которых лежат на границе выпуклой оболочки набора. Реально нужно перебирать все треугольники, но за счет организации точек в подходящую структруру данных можно ускорить вычисление кол-ва точек из набора лежащих внутри треугольника.

Я бы начинал с точек, лежащих на границах "внешнего многоуголькика", и каждый раз удалял из рассмотрения треугольники, лежащие внутри рассматриваемого.

Должно довольно быстро вычистить список.