Минимальный прямоугольник, содержащий все пересечения линий

Я пытаюсь найти алгоритм, который найдет все пересечения набора линий и вычислит минимальный прямоугольник, который содержит все пересечения за O (n log n) времени. До сих пор я предполагаю, что это связано с двойственностью и выпуклыми оболочками, но я как бы застрял на том, как это на самом деле поможет мне решить эту проблему.

Если у кого-то есть идеи по этому поводу, пожалуйста, дайте мне знать. Спасибо :)

 xvatar09 июн. 2012 г., 02:13
Итак, я предполагаю, что ваша проблема в том, как найти все пересечения?
 touvlo200009 июн. 2012 г., 02:19
ну вот и главная проблема
 xvatar09 июн. 2012 г., 02:40
это отрезки или просто линии?

Ответы на вопрос(2)

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

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

All lines are parallel. All intersections are along one line. This could happen if all lines but one are parallel. All lines intersect at a single point.

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

Фаза 1 - Увеличьте прямоугольник, чтобы включить одно пересечение от каждой линии:

Tag the three lines forming the initial triangle. Choose one untagged line, and find an intersection P with a tagged line. This is always possible since there are at least three tagged lines that aren't mutually parallel. Grow the box to include P. Repeat from 2 until all the lines are tagged, i.e. they all have at least one intersection in the box.

Назовите получившееся поле B [0].

Этап 2 - Определить, если линии имеют пересечение за пределами поля:

Вот ключевое наблюдение: для двух линий A и B, которые пересекаются внутри коробки, проходя вокруг коробки по часовой стрелке, мы сталкиваемся с чередующимися линиями: например, A B A B. Для двух линий, которые пересекают ВНЕ коробки, ход по часовой стрелке НЕ чередуется: например, A B B A. Конечно, существует вероятность того, что линии пересекаются на границе бокса или являются параллельными, но это будет рассматриваться как деталь после описания основного алгоритма.

Choose an orientation of the lines: Let the lines be directed toward the +y direction if the lines aren't horizontal, and let horizontal lines be oriented in the +x direct. One things of the lines as arrows, then the arrows are all chosen to point up as much as they can, or to the right if they're horizontal. With this orientation, each line has a point of entry into the box (where the oriented line points into the box, and a point of exit. These may be the same point. Create an "exit sequence" of the lines by walking the EXITING intersections clockwise around the boundary, starting at, say, the upper right corner. Create an "enter sequence" of the lines by walking the ENTERING intersections clockwise starting at the upper right corner of the box as well. If all intersections are interior to the box, the enter and exit sequences will be cyclic with each other, and B[i] is the minimum bounding box of the intersections. Otherwise, align the two sequences to an arbitrary element (by cyclic rotation). Find the elements in the sequences where they first differ. Those two lines must have an intersection P outside of the box, so form B[i+1] by growing B[i] to include P. Repeat from 2.

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

Обратите внимание, что этот алгоритм не генерирует все пересечения, но он гарантирует (я надеюсь), что поле содержит их все.

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

Идея: начните с сортировки линий по азимуту или наклону. При прочих равных условиях почти параллельные линии могут пересекаться в отдаленных точках; и, конечно, вас интересуют отдаленные моменты.

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

Ваш ответ на вопрос