Code:
/ DotNET / DotNET / 8.0 / untmp / WIN_WINDOWS / lh_tools_devdiv_wpf / Windows / wcp / Print / Reach / AlphaFlattener / SegmentTree.cs / 1 / SegmentTree.cs
//------------------------------------------------------------------------------ // Microsoft Printing // Copyright (c) Microsoft Corporation, 2005 // // File: SegmentTree.cs // // History: // [....]: 01/13/2005 Created //----------------------------------------------------------------------------- using System; using System.Collections; // for ArrayList using System.Diagnostics; using System.Collections.Generic; using System.Windows; // for Rect WindowsBase.dll namespace Microsoft.Internal.AlphaFlattener { internal class Coordinate { public double value; public int index; public bool active; public Coordinate top; public Coordinate bottom; public Coordinate(double v, int i) { value = v; index = i; } } internal class CoordinateComparer : IComparer { int IComparer.Compare(Object x, Object y) { double vx = ((Coordinate)x).value; double vy = ((Coordinate)y).value; return vx.CompareTo(vy); } } internal class CoordinateSearcher : IComparer { int IComparer.Compare(Object x, Object y) { double vx = ((Coordinate)x).value; double vy = (double)y; return vx.CompareTo(vy); } } internal class SegmentTree { double _min; double _max; SegmentTree _left; SegmentTree _right; List_sList; /// /// Build a balanced Segment Tree from a sorted intersection list /// /// /// /// public SegmentTree(Coordinate[] coord, int from, int count) { Debug.Assert(count >= 2); _min = coord[from].value; _max = coord[from + count - 1].value; if (count > 2) { int half = count / 2 + 1; _left = new SegmentTree(coord, from, half); _right = new SegmentTree(coord, from + half - 1, count - half + 1); } } public void Remove(int index, double x0, double x1) { if ((_min >= x0) && (_max <= x1)) // [_min.._max] is within [x0..x1] { if (_sList != null) { _sList.Remove(index); } } else { if ((_left != null) && (x0 <= _left._max) && (x1 >= _left._min)) // overlap with left { _left.Remove(index, x0, x1); } if ((_right != null) && (x0 <= _right._max) && (x1 >= _right._min)) // overlap with right { _right.Remove(index, x0, x1); } } } public void Insert(int index, double x0, double x1) { if ((_min >= x0) && (_max <= x1)) // [_min.._max] is within [x0..x1] { if (_sList == null) { _sList = new List(); } _sList.Add(index); } else { if ((_left != null) && (x0 <= _left._max) && (x1 >= _left._min)) // overlap with left { _left.Insert(index, x0, x1); } if ((_right != null) && (x0 <= _right._max) && (x1 >= _right._min)) // overlap with right { _right.Insert(index, x0, x1); } } } public void ReportIntersection(DisplayList dl, int index, double x) { if (_sList != null) { foreach (int i in _sList) { if (index != i) { dl.ReportOverlapping(index, i); } } } if ((_left != null) && (x >= _left._min) && (x <= _left._max)) { _left.ReportIntersection(dl, index, x); } if ((_right != null) && (x >= _right._min) && (x <= _right._max)) { _right.ReportIntersection(dl, index, x); } } } internal class RectangleIntersection { protected Coordinate[] _xCoord; // = null; protected int _xCount; // = 0; protected Coordinate[] _yCoord; // = null; protected int _yCount; // = 0; static Coordinate[] RemoveDuplication(Coordinate[] values) { int last = 0; int len = values.Length; double val = values[last].value; for (int i = 1; i < len; i++) { if (! Double.Equals(values[i].value, val)) { last++; val = values[i].value; } } if (len != (last + 1)) { Coordinate[] newvalues = new Coordinate[last + 1]; last = 0; newvalues[0] = values[0]; for (int i = 1; i < len; i++) { if (! Double.Equals(values[i].value, newvalues[last].value)) { last++; newvalues[last] = values[i]; } } return newvalues; } else { return values; } } private void AddPoint(int i, int index, double x, double y) { Coordinate cx = new Coordinate(x, index); Coordinate cy = new Coordinate(y, index); _xCoord[i] = cx; _yCoord[i] = cy; } private void SortEndPoints(DisplayList dl, int count) { _xCoord = new Coordinate[2 * count + 2]; _yCoord = new Coordinate[2 * count + 2]; AddPoint(0, -1, Double.MinValue, Double.MinValue); int p = 1; for (int i = 0; i < count; i++) { Rect r = dl[i]; AddPoint(p, i, r.Left, r.Top); AddPoint(p + 1, i, r.Right, r.Bottom); _xCoord[p].top = _yCoord[p]; _xCoord[p].bottom = _yCoord[p + 1]; _xCoord[p + 1].top = _yCoord[p]; _xCoord[p + 1].bottom = _yCoord[p + 1]; p += 2; } AddPoint(p, count + 1, Double.MaxValue, Double.MaxValue); Array.Sort(_xCoord, new CoordinateComparer()); _xCount = _xCoord.Length; Array.Sort(_yCoord, new CoordinateComparer()); _yCount = _yCoord.Length; } // Input N rectangles -> 2N vertical line segment, 2N horizontal line segments // Output all true intersections rectangles private void OrthogonalLineSegmentIntersection(DisplayList dl) { // Sweep through sorted x coordiates from left to right, skipping MinValue/MaxValue for (int i = 1; i < _xCount - 1; i++) { Coordinate c = _xCoord[i]; bool left = Double.Equals(c.value, dl[c.index].Left); // Left endpoint => insertion into range tree // Right endpoint => delection from range tree c.top.active = left; c.bottom.active = left; // Vertical segment [y0..y1] => report [y0..y1] AND range tree double y0 = c.top.value; double y1 = c.bottom.value; int p = Array.BinarySearch(_yCoord, y0, new CoordinateSearcher()); if (p >= 0) { do { if ((_yCoord[p].active) && (c.index != _yCoord[p].index)) { dl.ReportOverlapping(c.index, _yCoord[p].index); // Console.WriteLine("{0} {1} intersects ({2},{3})", c.index, _yCoord[p].index, c.value, _yCoord[p].value); } p++; } while (_yCoord[p].value <= y1); } } } // Input N rectangles and points (top-left corner of rectangle) // Output all R(r, p) where point p is within rectangle r private void BatchedRangeSearch(DisplayList dl) { // 1) Sort all points and left/right rectangle sides w.r.t. x-coordinate // 2) Sweep left-to-right while storing y-intervals of rectangles intersecting // the sweepline in a segment tree T // 2.1) Left side => insert interval into T // 2.2) Right side => delete interval from T // 2.3) Point (x, y) stabbing query report all [y1,y2] where y is in [y1..y2] Coordinate[] uniqueY = RemoveDuplication(_yCoord); SegmentTree st = new SegmentTree(uniqueY, 0, uniqueY.Length); // Sweep through sorted x coordiates from left to right, skipping MinValue/MaxValue for (int i = 1; i < _xCount - 1; i++) { Coordinate c = _xCoord[i]; double y0 = c.top.value; double y1 = c.bottom.value; if (Double.Equals(c.value, dl[c.index].Left)) { st.Insert(c.index, y0, y1); st.ReportIntersection(dl, c.index, y0); } else { st.Remove(c.index, y0, y1); } } } public void CalculateIntersections(DisplayList dl, int count) { SortEndPoints(dl, count); OrthogonalLineSegmentIntersection(dl); BatchedRangeSearch(dl); } #if UNIT_TEST internal static void UnitTest() { Console.WriteLine("RectangleIntersection unit test"); DisplayList dl = new DisplayList(8.5 * 96, 11 * 96); dl.Add( 3, 8, 6, 36); dl.Add(25, 34, 34, 38); dl.Add(33, 37, 21, 36); dl.Add(21, 38, 23, 27); dl.Add( 6, 26, 3, 8); dl.Add(31, 35, 15, 19); dl.Add(23, 38, 11, 14); dl.Add(16, 22, 3.5, 7.5); RectangleIntersection ri = new RectangleIntersection(); ri.CalculateIntersections(dl); } #endif } } // File provided for Reference Use Only by Microsoft Corporation (c) 2007. // Copyright (c) Microsoft Corporation. All rights reserved.
Link Menu
This book is available now!
Buy at Amazon US or
Buy at Amazon UK
- WebServiceMethodData.cs
- IncrementalReadDecoders.cs
- SqlUserDefinedAggregateAttribute.cs
- EnumDataContract.cs
- PersonalizableTypeEntry.cs
- UnsignedPublishLicense.cs
- TypeUtil.cs
- Rect3D.cs
- SyndicationSerializer.cs
- Point3DCollectionValueSerializer.cs
- ImageDrawing.cs
- FloatMinMaxAggregationOperator.cs
- ASCIIEncoding.cs
- COM2ComponentEditor.cs
- ToolBarButtonClickEvent.cs
- BasicHttpSecurityElement.cs
- BaseAutoFormat.cs
- FileCodeGroup.cs
- DynamicPropertyHolder.cs
- RuntimeCompatibilityAttribute.cs
- SpellCheck.cs
- QueryAccessibilityHelpEvent.cs
- StreamingContext.cs
- XmlSerializationWriter.cs
- TabletDevice.cs
- Popup.cs
- CanonicalXml.cs
- FlowDocumentView.cs
- DrawingDrawingContext.cs
- XmlElementAttribute.cs
- Table.cs
- HostingPreferredMapPath.cs
- HttpConfigurationContext.cs
- FixedDSBuilder.cs
- HtmlElementCollection.cs
- AlternateView.cs
- figurelengthconverter.cs
- ToolStripLabel.cs
- WindowsComboBox.cs
- FloatUtil.cs
- ApplicationFileCodeDomTreeGenerator.cs
- PresentationTraceSources.cs
- ImageMapEventArgs.cs
- XmlSchemaObjectCollection.cs
- DataBoundControl.cs
- XmlChildEnumerator.cs
- DataServicePagingProviderWrapper.cs
- ReadOnlyMetadataCollection.cs
- PerformanceCounterPermission.cs
- KnownTypes.cs
- HtmlCommandAdapter.cs
- PopupEventArgs.cs
- TransformPattern.cs
- ClrPerspective.cs
- VBCodeProvider.cs
- XmlMtomReader.cs
- PartialCachingAttribute.cs
- ApplicationDirectory.cs
- PolicyLevel.cs
- RectKeyFrameCollection.cs
- ValueUtilsSmi.cs
- SqlConnectionString.cs
- CapabilitiesRule.cs
- X509CertificateInitiatorServiceCredential.cs
- WebPartTransformer.cs
- ExternalException.cs
- AttachInfo.cs
- PersonalizationProvider.cs
- TableStyle.cs
- FormsAuthentication.cs
- SqlLiftIndependentRowExpressions.cs
- XmlIgnoreAttribute.cs
- FontInfo.cs
- DataSetUtil.cs
- LicenseContext.cs
- DesignerActionVerbList.cs
- BaseCodePageEncoding.cs
- FormViewPagerRow.cs
- TemplateKey.cs
- ListBindingConverter.cs
- HtmlMeta.cs
- HwndHostAutomationPeer.cs
- Switch.cs
- XmlSchemaExternal.cs
- WebPartDescription.cs
- MediaContextNotificationWindow.cs
- DataGridViewCellErrorTextNeededEventArgs.cs
- DependentList.cs
- ValidationRule.cs
- MultiTrigger.cs
- TextFormatterHost.cs
- followingsibling.cs
- PartitionerStatic.cs
- safesecurityhelperavalon.cs
- Codec.cs
- QueryReaderSettings.cs
- MenuRendererStandards.cs
- RegexTree.cs
- ServerReliableChannelBinder.cs
- MessageDecoder.cs