relate uses the Bentley-Ottmann algorithm to classify geometry intersections using DE-9IM.
(ps, qs Paths, intersections bool)
| 2711 | |
| 2712 | // relate uses the Bentley-Ottmann algorithm to classify geometry intersections using DE-9IM. |
| 2713 | func relate(ps, qs Paths, intersections bool) (Relation, []Point) { |
| 2714 | // TODO: support arcs |
| 2715 | // TODO: support finding self-intersections |
| 2716 | // TODO: if overlapping segments can be detected earlier (in addIntersections) and combined there, |
| 2717 | // we can just process left-events and make the code simpler |
| 2718 | |
| 2719 | boInitPoolsOnce() // use pools for SweepPoint and SweepNode to amortize repeated calls to BO |
| 2720 | |
| 2721 | self := qs == nil |
| 2722 | if ps.Empty() || !self && qs.Empty() { |
| 2723 | return 0, nil |
| 2724 | } |
| 2725 | |
| 2726 | // flatten paths and initialise queue |
| 2727 | pSeg, qSeg := 0, 0 |
| 2728 | queue := &SweepEvents{} |
| 2729 | for i := range ps { |
| 2730 | ps[i] = ps[i].Flatten(Tolerance) |
| 2731 | pSeg = queue.AddPathEndpoints(ps[i], pSeg, false) |
| 2732 | } |
| 2733 | if !self { |
| 2734 | for i := range qs { |
| 2735 | qs[i] = qs[i].Flatten(Tolerance) |
| 2736 | qSeg = queue.AddPathEndpoints(qs[i], qSeg, true) |
| 2737 | } |
| 2738 | } |
| 2739 | queue.Init() // sort from left to right |
| 2740 | |
| 2741 | var rel Relation |
| 2742 | zsAll := []Point{} |
| 2743 | |
| 2744 | // Bentley-Ottmann loop |
| 2745 | var rights []*SweepPoint // right-events at position |
| 2746 | var processedRights = false |
| 2747 | status := &SweepStatus{} // contains only left events |
| 2748 | zs := make([]Point, 0, 2) // buffer for intersections |
| 2749 | for 0 < len(*queue) { |
| 2750 | // We slightly divert from the original Bentley-Ottmann and paper implementation. First |
| 2751 | // we find the top element in queue but do not pop it off yet. If it is a right-event, pop |
| 2752 | // from queue and proceed as usual, but if it's a left-event we first check (and add) all |
| 2753 | // surrounding intersections to the queue. This may change the order from which we should |
| 2754 | // pop off the queue, since intersections may create right-events, or new left-events that |
| 2755 | // are lower (by compareTangentV). If no intersections are found, pop off the queue and |
| 2756 | // proceed as usual. |
| 2757 | |
| 2758 | event := queue.Top() |
| 2759 | if 0 < len(rights) && rights[0].Point != event.Point { |
| 2760 | if !processedRights { |
| 2761 | for i, right := range rights { |
| 2762 | if i+1 == len(rights) || rights[i+1].other.Point != right.other.Point { |
| 2763 | rel, zsAll = eventRelation(rel, zsAll, right, rights[:i], self) |
| 2764 | } |
| 2765 | } |
| 2766 | } |
| 2767 | rights = rights[:0] |
| 2768 | } |
| 2769 | if !event.left { |
| 2770 | queue.Pop() |
no test coverage detected