треугольник указывает вокруг точки

Question

Я дал координаты 1000 треугольников на плоскости (номер треугольника (T0001-T1000) и его координаты (x1, y1) (x2, y2), (x3, y3)). Теперь для заданной точки P (x, y) мне нужно найти треугольник, который содержит точку P.

Один из вариантов - проверить все треугольники и найти треугольник, содержащий P. Но я ищу эффективное решение этой проблемы.

Answer 1

Вам нужно будет проверить каждый треугольник на некотором пункте во время выполнения вашей программы. Это очевидно, верно? Если вы хотите максимизировать эффективность этого расчета, то вы собираетесь создать некую структуру данных кэша. Детали структуры данных зависят от вашего приложения. Например: как часто меняются треугольники? Как часто вам нужно вычислять, где находится точка?

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

Тогда, когда вам нужно выяснить, в каких треугольниках находится ваша точка, вы сначала выясните, в каком квадрате она находится (это будет O (1) раз, потому что вы просто посмотрите на координаты), а затем посмотрите на треугольники в списке треугольников для этого поля.

Answer 2

Несколько разных способов поиска по вашим треугольникам. Я бы начал с устранения невозможностей.

Найдите левый нижний угол для каждого треугольника и удалите все, что находится выше и / или справа от вашей точки. продолжайте поиск с другими треугольниками, и вы должны устранить подавляющее большинство исходных треугольников.

Возьмите то, что у вас осталось, и используйте полярную систему координат, чтобы собрать остальную необходимую информацию, основанную на углах между углами и точкой (в Java есть некоторые инструменты для этого, я не знаю о других языках).

Некоторые вещи, на которые стоит обратить внимание, - это выпуклая оболочка (другая, но несколько полезная), треугольники Бернулли и некоторые методы сортировки, вероятно, будут полезны.