package mapMaker; import MDUtils.MGeomUtils; import MDUtils.MInfiniteLine; import MDColor.ColorUtils; import mapGenerator.MapReaderFactory; import java.awt.Polygon; import java.awt.Shape; import java.awt.Color; import java.awt.geom.Line2D; import java.awt.geom.Point2D; import java.util.Collections; import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Iterator; import java.util.HashMap; import java.util.StringTokenizer; import java.util.Set; import java.util.NoSuchElementException; import java.lang.UnsupportedOperationException; import java.io.BufferedReader; import java.io.IOException; /** Model a map. * Typically the map is read in from a text stream. * * @author MD * date 10/2002 * For CSE143 Project 3 * * The map is modelled as several lists, extracted from an input stream. */ public class MapModel { /** A list of polygons, built from the segments in the map file. */ final List polyList = new ArrayList(); /** All the segments from the file, turned into Line2D's. */ List segments = new ArrayList(); //this one is destroyed final List originalSegments = new ArrayList(); //shallow copy of above /**Contains each unique line segment, and # of occurrences */ //HashMap allLinesAndCounts = new HashMap(); /**Contains all and only the boundary segments */ List boundaryList = new ArrayList(); /** Lines from the file with COUNTY information, unparsed */ final List countyInfoList = new ArrayList(); /** Lines from the file with COUNTY information, parsed. * Once we locate a county, we place a pointer to its polygon here, too. */ final List parsedCountyInfo = new LinkedList(); /** County information as a list of nice printable strings. */ List countyInfoPrintList = new LinkedList(); /** Lines from the file with // comments */ final List commentList = new LinkedList(); /**Build a map from a randomly generated Reader. */ public MapModel() { /**build a default*/ this(MapReaderFactory.createMapReader()); } /**Build a map from a given buffered Reader. * If unrecoverable errors are found, they will be announced, and possibly * will terminate the program. * The information is stored mainly in a bunch of instance variable lists. */ public MapModel(BufferedReader mapReader) { assert mapReader != null; readCompleteMap(mapReader); //read all lines, save in lists /* segments contains all the segment info, as Line2D's */ //Find intersecting segments and dissect them. int changesMade = -1; changesMade = dissectIntersectingSegments(segments); assert changesMade >= 0; System.out.println(segments.size() + " segments, " + changesMade + " changes this time."); this.segments = MGeomUtils.roundAll(this.segments); changesMade = dissectIntersectingSegments(segments); assert changesMade >= 0; System.out.println(segments.size() + " segments, " + changesMade + " changes this time."); //Now that dissections are done, any seg. that occurs only once // must be on the boundary this.boundaryList = buildBoundaryList(this.segments); /* Find the county polygons. Segments are removed and processed as we go. * By the end of the loop, the segment list should be empty. */ int origSegListSize = segments.size(); while (segments.size() > 0) { Polygon currPoly = extractNextPolygon(segments); //modifies "segments" if (currPoly == null) { System.out.println("Can't extract polygon from segments. " + "\nError on or before segment number " + (origSegListSize - segments.size()) + "\nAttempting to continue processing"); } else { polyList.add(currPoly); } } //All segments have been processed: grouped into polygons. // Make a parsed version of the COUNTY lines Iterator iter = countyInfoList.iterator(); while (iter.hasNext()) { //parse the line and save the information parsedCountyInfo.add(new CountyInfoUnit((String) iter.next())); } assert parsedCountyInfo.size() == countyInfoList.size(); //Following is for old-style states with no counties assert countyInfoList.size() > 0 || polyList.size() == 1; //following is == unless there was an error parsing polygons //or unless it is an old-style map with no counties if (polyList.size() > 1 && (parsedCountyInfo.size() < polyList.size())) { System.out.println("Error: " + polyList.size() + " polygons" + " but COUNTY information for only " + parsedCountyInfo.size() + "\nAttempting to continue."); } //Now the fun part: try to match the COUNTY information with the polygons //"Unidentified flying polygons" go there, too, as "unknown" locateAllCounties(parsedCountyInfo, polyList); // Now make a strings version of the parsed COUNTY lines countyInfoPrintList = this.makeCountyInfoPrintList(parsedCountyInfo); } //mapModel constructor /** Return an iterator to the list of polygons * */ public KnownPolyIterator polyIterator() { return new KnownPolyIterator(); } //end polyIterator public Iterator allPolyIterator() { return polyList.iterator(); } /** Return an iterator to the parsed county information */ public Iterator parsedCountyIterator() { List safeCountyList = Collections.unmodifiableList(parsedCountyInfo); //return parsedCountyInfo.iterator(); return safeCountyList.iterator(); } /** Make strings with just the printable part of the county information. */ private List makeCountyInfoPrintList(List parsedCounties) { List printList = new LinkedList(); Iterator cIter = parsedCounties.iterator(); while (cIter.hasNext()) { //CountyInfoUnit thisInfo = new CountyInfoUnit((String)cIter.next()); CountyInfoUnit thisInfo = (CountyInfoUnit)cIter.next(); String outLine = thisInfo.countyName + " " + thisInfo.population + " " + thisInfo.cityName + " "; printList.add(outLine); } return printList; } public Iterator getCountyInfoIter() { return countyInfoPrintList.iterator(); } /** Find the next polygon in the list of segments. * @param segments a list of the segments not yet grouped into polygons. * @return a Polygon, or null if no polygon could be formed. */ public Polygon extractNextPolygon(List segments) { //start with the first (remaining) segment, and trace the connected points //each point is placed in sequence in a Polygon //When one polygon is closed, we stop //As each segment is processed, it is removed from the segment list //Null is returned if no polygon can be extracted int originalSegListSize = segments.size(); if (originalSegListSize < 3) { System.out.println("Current segment list has only " + originalSegListSize + " remaining; not enough to form a polygon"); return null; //signal error to caller } Line2D currLine = (Line2D) segments.remove(0); //get 1st line and remove it Point2D firstPoint = currLine.getP1(); //starting point Point2D currStart = firstPoint; Point2D currEnd = currLine.getP2(); Polygon currPolygon = new Polygon(); //Points are rounded as they are placed in the polygon. //This loss of precision will probably come back to haunt me someday... currPolygon.addPoint((int) Math.round(firstPoint.getX()), (int) Math.round(firstPoint.getY())); while (!currEnd.equals(firstPoint)) { //we have not wrapped back the beginning of the poly yet assert !currEnd.equals(currStart); currPolygon.addPoint((int)Math.round(currEnd.getX()), (int) Math.round(currEnd.getY())); currStart = currEnd; currEnd = null; //flag to say we don't know the value yet //find a (different) segment that joins the current one at currStart // (currStart was the previous currEnd) currEnd = findOtherSegmentEndpoint(segments, currStart, currEnd); //The segment found has been removed from the list. //Note that it might NOT have been the first in the list! if (currEnd == null) { System.out.println("Error reading segments -- no match for the point " + MGeomUtils.printPoint(currStart) + "\nwill asume there is an unclosed polygon " + " and attempt to continue." + "\nProgram may abort later if continuation is unsuccessful"); currEnd = firstPoint; //dummy up the termination condition } //OK, got a valid segment //current point will be added at the top of the loop iteration //if current point is first point, then the loop will end -- // which is right, since the first point is already in the shape, // and Polygon wraps automatically (unlike the map file!) } // outer while //done building a polygon //following won't be == unless there is only one polygon assert currPolygon.npoints <= originalSegListSize; return currPolygon; } //end extract next polygon /**search the segment list Remember that used segments have already been removed. This method will remove the segment it finds (at most one). Note that skipped segments are NOT removed! //we are looking for ANOTHER segment that starts or ends with currStart //If there isn't one -- something is amiss. * It would be more transparent NOT to do the remove here -- * let the caller do it. */ private Point2D findOtherSegmentEndpoint(List segments, Point2D currStart, Point2D currEnd) { Iterator innerSegIter = segments.iterator(); while (innerSegIter.hasNext()) { Line2D innerLine = (Line2D) innerSegIter.next(); if (currStart.equals(innerLine.getP1())) { currEnd = innerLine.getP2(); innerSegIter.remove(); break; } if (currStart.equals(innerLine.getP2())) { currEnd = innerLine.getP1(); innerSegIter.remove(); break; } /*getting here means we haven't found a link to the *previous segment yet. *Either we've reached around to the starting point again, or *the segment list had better not be empty!. **/ //we're still looking assert currEnd == null; } // inner while //we SHOULD have found currEnd somewhere by now. return currEnd; } // find other segment endpoint /** Read all the map lines and save them all in instance variable lists. The Reader is assumed to be open and ready to go. * The Reader is closed at the end. * Comment, segment, and COUNTY lines can be intermixed. * The output lists preserve the original file order within each type of line. */ private void readCompleteMap(BufferedReader mapReader) { int lineCount = 0; //number of lines on the file try { String nextLine = mapReader.readLine(); //the first line while (nextLine != null) { lineCount++; if (nextLine.startsWith("//")) { //it's a comment line this.commentList.add(nextLine); } else { //it's not a comment if (nextLine.startsWith("COUNTY")) { //it's a county information line this.countyInfoList.add(nextLine); } else { //it's not a comment or a COUNTY line //It had better be a segment line Line2D thisLine = parseLineLine(nextLine); if (thisLine.getP1().equals(thisLine.getP2())) { //trivial segment -- don't store it } else { this.segments.add(thisLine); //remember this segment this.originalSegments.add(thisLine); } } //done with a segment line } //done with a non-comment line nextLine = mapReader.readLine(); } //end while //All the lines have been read in mapReader.close(); } catch (Exception e) { throw new RuntimeException("Unable to create or load a map " + e + "\n" + lineCount + " have been examined."); } } //end readCompleteMap /** Try to find out where the counties really are. * That is, see which polygon contains which county seat. * This is done after all lines of the file have been parsed. */ private void locateAllCounties(List parsedList, List polygonList) { Iterator infoIter = parsedList.iterator(); while (infoIter.hasNext()) { //get info for one county, try to find its polygon MapModel.CountyInfoUnit currCounty = (MapModel.CountyInfoUnit) infoIter.next(); Polygon containingShape = (Polygon) MGeomUtils.findPoint(currCounty.location, polygonList); if (containingShape == null) { String emsg = currCounty.cityName + " at " + MGeomUtils.printPoint(currCounty.location) + " is not within the state!"; this.countyInfoPrintList.add(emsg); } else { if (currCounty.countyPoly != null) { String emsg = currCounty.countyName + " county " + " seems to have another county seat!"; this.countyInfoPrintList.add(emsg); } currCounty.countyPoly = containingShape; } } //Make another pass to put any unidentified polygons in the counties list. if (parsedCountyInfo.size() > 0) { //skip state-only maps Iterator pIter = polyList.iterator(); while (pIter.hasNext()) { Shape poly = (Shape) pIter.next(); if (isKnownPolygon(poly, parsedCountyInfo)) { continue; } //Insert an "unknown" county line CountyInfoUnit cinfo = new CountyInfoUnit(); cinfo.countyPoly = poly; parsedCountyInfo.add(cinfo); } } //end locateAllCounties } /** see if the poly is in the known list of counties. * We assume that references are shared -- the list doesn't contain * deep copies. */ boolean isKnownPolygon (Shape poly, List infoList) { Iterator infoIter = infoList.iterator(); while (infoIter.hasNext()) { CountyInfoUnit unit = (CountyInfoUnit) infoIter.next(); if (poly == unit.countyPoly) { return true; } } return false; //end isKnownPolygon } /** return a list containing all and only the (outside) boundary segments. */ private List buildBoundaryList(List lines) { ArrayList bList = new ArrayList(); Iterator linesIter = lines.iterator(); while (linesIter.hasNext()) { Line2D outerLine = (Line2D) linesIter.next(); Iterator innerIter = lines.iterator(); int repeatCount = 0; while (innerIter.hasNext()) { //see how many matches there are //line will at least match itself Line2D innerLine = (Line2D) innerIter.next(); if (MGeomUtils.equals(outerLine, innerLine)) { repeatCount++; if (repeatCount > 1) { break; //not a boundary } } } //end inner if (repeatCount > 1) { continue; } assert repeatCount == 1; bList.add(outerLine); } //end iteration assert bList.size() > 0; //can do better, if we know # counties assert this.countyInfoList == null || (countyInfoList.size() <= 1 && bList.size() >=3) || (countyInfoList.size() > 1 && bList.size() < lines.size()); return bList; } //end buildBoundaryList public Iterator boundaryIterator() { assert boundaryList != null; assert boundaryList.size() >0; List safeBoundaryList = Collections.unmodifiableList(boundaryList); return safeBoundaryList.iterator(); } /** Find segments which intersect (or almost do). * Mostly these will be cases where an endpoint of one segment * touches the interior of another segment. * The segment(s) divided by such an intersection will be replaced * by its two consecutive subsegments. * Array position is maintained. */ private static int dissectIntersectingSegments(List segments) { //Here's a good case for using a loop index instead of iterators. //Since we may be adding and deleting elements, // nested iterators are awkward. //Quadratic algorithm, no smarts at all. //For each endpoint of each line, see if it is on some // Split that other segment if appropriate. // @return the number of changes made to the list (remove, add, etc.) int changeCount = 0; for (int outerIndex = 0; outerIndex < segments.size(); outerIndex++) { Line2D currLine = (Line2D) segments.get(outerIndex); assert currLine != null; if (currLine.getP1().equals(currLine.getP2())) { segments.remove(outerIndex); //useless segment changeCount++; continue; } double minSplittableLength = 0.2; changeCount += findAndFixIntersectingSegments(currLine, segments, outerIndex, minSplittableLength); //might add/delete //the list size might now be larger, but we will still have seen // all of the postions up to outerIndex and maybe beyond. // if adds were made before outerIndex, we will reprocess those // points (unecessesarily, but harmlessly, we hope). } return changeCount; //end dissectIntersectingSegments } /** Find segments that touch or intersect the given ("outer") segment. * Segments which are divided are replaced by their two subsegments. * @param minSplitDistance epsilon; below this length don't split. * * Reminder: Line2D.equals is shallow, Point2D equals is based on value */ private static int findAndFixIntersectingSegments(Line2D outerLine, List segments, int outerIndex, double minSplitDistance) { int changeCount = 0; //CAUTION! loop index may be modified inside the loop body! for (int innerIndex = outerIndex+1; innerIndex < segments.size(); innerIndex++) { assert innerIndex >= 0; //tiny safety check Line2D nextLine = (Line2D) segments.get(innerIndex); assert nextLine != null; if (MGeomUtils.isEmptyLine(nextLine)) { //useless line segments.remove(innerIndex); changeCount++; innerIndex--; //force position to be reprocessed continue; } if (MGeomUtils.lineLength(nextLine) < minSplitDistance) { //don't delete, but don't split, either //sort of a presumption that this point will be rounded eventually continue; } if (1 <= MGeomUtils.countMatchingEndpoints(nextLine, outerLine)) { //Sharing an endpoint is no cause for splitting continue; } boolean intersecting = outerLine.intersectsLine(nextLine); assert intersecting == nextLine.intersectsLine(outerLine); if (!intersecting) { //no splitting to do continue; } //intersection. split one or both lines Point2D intersectionPoint = MInfiniteLine.intersection(outerLine, nextLine); assert intersectionPoint != null; //split both lines at the intersection point Line2D nextLine_1 = new Line2D.Double( nextLine.getP1(), intersectionPoint); Line2D nextLine_2 = new Line2D.Double( intersectionPoint, nextLine.getP2()); Line2D outerLine_1 = new Line2D.Double( outerLine.getP1(), intersectionPoint); Line2D outerLine_2 = new Line2D.Double( intersectionPoint, outerLine.getP2()); //Order of these remove/adds is important. //replace outerLine DOES affect nextLine index, but not vice versa //first, see if nextLine should be split. if (MGeomUtils.lineLength(nextLine_1) > minSplitDistance && MGeomUtils.lineLength(nextLine_2) > minSplitDistance) { //nextLine is splitable //make sure index is intact assert MGeomUtils.equals(nextLine, (Line2D) segments.get(innerIndex)); segments.remove(innerIndex); segments.add(innerIndex, nextLine_2); //too bad there's no return value segments.add(innerIndex, nextLine_1); changeCount++; } //now, see if outer line is splittable if (MGeomUtils.lineLength(outerLine_1) > minSplitDistance && MGeomUtils.lineLength(outerLine_2) > minSplitDistance) { //outer line is splittable //make sure index is intact assert MGeomUtils.equals(outerLine, (Line2D) segments.get(outerIndex)); segments.remove(outerLine); segments.add(outerIndex, outerLine_2); segments.add(outerIndex, outerLine_1); changeCount++; break; //get out of this loop and go back to outer } } //end loop return changeCount; } //end method /** Parse one line of segment information. * If the line is invalid, throw an exception * Otherwise, return the line segment implied by the data. somehow it doesn't feel like this belongs in this class. * */ private static Line2D parseLineLine(String lineText) { //use default delimiters: white space StringTokenizer tokens = new StringTokenizer(lineText); if (tokens.countTokens() != 4) { throw new RuntimeException("Input line did not have 4 tokens:\n " + lineText); } try { double x1 = Double.parseDouble(tokens.nextToken()); double y1 = Double.parseDouble(tokens.nextToken()); double x2 = Double.parseDouble(tokens.nextToken()); double y2 = Double.parseDouble(tokens.nextToken()); return new Line2D.Double(x1, y1, x2, y2); } catch (NumberFormatException e) { throw new NumberFormatException("coudn't convert to 4 doubles:\n" + lineText); } } //end parse lineLine /** a class (inner) to hold parsed information about a county. * Format of the text line: *COUNTY */ class CountyInfoUnit { String countyName = "unknown"; private String cityName = "unknown"; private double seatx, seaty; // coordinates of the county seat private Point2D location = null; //point2D version of the county seat (unrounded) long population = 0; Color fillColor = Color.black; //by default /** when we know, we put the county's polygon here. * null means that no poly matches this location. */ Shape countyPoly = null ; CountyInfoUnit() { } CountyInfoUnit(String infoLine) { assert infoLine.startsWith("COUNTY"); StringTokenizer stok = new StringTokenizer(infoLine); if (stok.countTokens() != 6) { throw new RuntimeException("Oops, only " + stok.countTokens() + " on this line: " + infoLine); } String field1 = stok.nextToken(); //#1 = "CONTENTS" countyName = stok.nextToken(); //#2 = county name String popString = stok.nextToken(); //#3 population try { population = (long) Double.parseDouble(popString); } catch (Exception e) { throw new RuntimeException("Bad population string " + popString + " in line: " + infoLine + "\n" + e); } cityName = stok.nextToken(); //#4 String xStr = stok.nextToken(); //#5 String yStr = stok.nextToken(); //#6 try { seatx = Double.parseDouble(xStr); seaty = Double.parseDouble(yStr); } catch (Exception e) { throw new RuntimeException("Bad coordinates " + xStr + ", " + yStr + " in line: " + infoLine + "\n" + e); } location = new Point2D.Double(seatx, seaty); fillColor = ColorUtils.randomBlue(); } //end constructor for CInfoUnit public String getCityName() {return cityName;} public Point2D getLocation() {return location;} public Shape getPolygon() {return countyPoly;} //end CInfoUnit (inner class) } /** returns an iterator to the "known county" polygons of the map. * "known counties" are ones with polygons matched to COUNTY information. * Although this supports the methods of Iterator, if doesn't implement Iterator. * This is so it can return a more specific type from "next()". */ class KnownPolyIterator { private Iterator privateIter; public KnownPolyIterator() { privateIter = parsedCountyInfo.iterator(); } public boolean hasNext() { assert privateIter != null; return privateIter.hasNext(); } public Polygon next() { if (!privateIter.hasNext()) { throw new NoSuchElementException("Map iterator is used up!"); } CountyInfoUnit cUnit = (CountyInfoUnit) privateIter.next(); Object obj = cUnit.countyPoly; return (Polygon) obj; } public void remove() { throw new UnsupportedOperationException("MapIterator doesn't support remove"); } //end (inner) class MapIterator } } //end MapModel