/*
javac LandPolygon.java Polygon.java Tag.java

第１ステップ
osmconvert  d:/downloads/antarctica-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -way antarctica
osmconvert  d:/downloads/central-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -way central-america
osmconvert  d:/downloads/australia-oceania-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -way australia-oceania
osmconvert  d:/downloads/south-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -way south-america
osmconvert  d:/downloads/north-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -way north-america
osmconvert  d:/downloads/africa-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -way africa
osmconvert  d:/downloads/asia-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -way asia
osmconvert  d:/downloads/europe-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -way europe

第２ステップ
osmconvert  d:/downloads/antarctica-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node antarctica
osmconvert  d:/downloads/australia-oceania-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node australia-oceania
osmconvert  d:/downloads/africa-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node africa
osmconvert  d:/downloads/central-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node central-america
osmconvert  d:/downloads/south-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node south-america
osmconvert  d:/downloads/europe-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node europe
osmconvert  d:/downloads/asia-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node asia
osmconvert  d:/downloads/north-america-latest.osm.pbf | java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -node north-america

第３ステップ
java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon
java -Dfile.encoding=UTF-8 -Xmx5000m LandPolygon -shrink
*/

import java.io.*;
import java.nio.*;
import java.util.*;
import java.time.*;

public class LandPolygon {
    static boolean fShrink = false;

    static String pathLands() {  return "c:/osm/lands" + (fShrink ? "_low.dat" : ".dat"); }
    static double E7  = 10000000;
    static double B30 = 1024*1024*1024;   // (2 の 30乗)

    static int MAXSIZE = 130000000;
    static long[] nodes = new long[MAXSIZE];    // node id
    static int num_nodes;
    static int ixNode;
    static int[] lons;
    static int[] lats;
    static String[] areas = { "antarctica", "africa", "europe", "asia", "north-america", 
                              "central-america", "south-america", "australia-oceania" };

    static class Node {
        int x;      // 0 〜 2^30
        int y;      // 0 〜 2^30

        public Node(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }


    static double Lon2X(double lon, int zoom) {
        return (lon + 180.0) / 360.0 * (1<<zoom);
    }

    static double Lat2Y(double lat, int zoom) {
        return (1 - Math.log(Math.tan(lat*Math.PI/180.0) +
                1 / Math.cos(lat*Math.PI/180.0)) / Math.PI)/2.0 * (1<<zoom);
    }

    // String sId = getAttr(" id=", line);
    static String getAttr(String name, String line) {
        int ixBgn = line.indexOf(name);
        if (ixBgn < 0) return null;
        ixBgn += name.length() + 1; // '"' の分
        int ixEnd = ixBgn;
        while (ixEnd < line.length() && 
                    line.charAt(ixEnd) != '"' && line.charAt(ixEnd) != '\'') {
            ixEnd++;
        }
        return line.substring(ixBgn, ixEnd);
    }

    //
    static void parseNode(String name) {
        lons = new int[MAXSIZE];
        lats = new int[MAXSIZE];
        String file = "c:/osm/" + name + "_coastline.csv";
        try (BufferedReader br = new BufferedReader(new FileReader(file))) {
            String line;
            while ((line = br.readLine()) != null) {
                String[] nids = line.split(",");
                for (int n = 1; n < nids.length; n++) {
                    put(Long.parseLong(nids[n]), 0, 0);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
            return;
        }

        char quote = '"';
        int cntFound = 0;
        String pathOut = "c:/osm/" + name + "_idlonlat.dat";

        // 標準入力
        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
             DataOutputStream dos = new DataOutputStream(new FileOutputStream(pathOut))) {
            String line;
            while ((line = br.readLine()) != null) {
                int ix = line.indexOf('<');
                if (ix < 0) continue;
                String s = line.substring(ix);  // 行先頭のスペースを削除する
                if (s.startsWith("<node ")) {   // nodeオブジェクト
                    String sId = getAttr(" id=", line);
                    long idNode = Long.parseLong(sId);
                    if (get(idNode) > 0) {  // 海岸線ノード
                        cntFound++;
                        String sLon = getAttr(" lon=", line);
                        String sLat = getAttr(" lat=", line);
                        int lon = (int)(Double.parseDouble(sLon)*E7);
                        int lat = (int)(Double.parseDouble(sLat)*E7);
                        dos.writeLong(idNode);
                        dos.writeInt(lon);
                        dos.writeInt(lat);
                    }
                } else if (s.startsWith("<way ")) {   // wayオブジェクト
                    break;
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    static int hash(long id) {
        return (int)(Math.abs(id * 137) % MAXSIZE);
    }

    static int put(long id, int lon, int lat) {
        int n, h = hash(id);
        for (n = 0; n < MAXSIZE; n++) {
            int ix = (h + n) % MAXSIZE;
            if (nodes[ix] == 0) {
                nodes[ix] = id;
                lons[ix] = lon;
                lats[ix] = lat;        
                num_nodes++;
                if (num_nodes % 1000000 == 0) {
                    System.out.printf("%d万\r", num_nodes / 10000);
                }
                return ix;                // 新規登録
            } else if (nodes[ix] == id) {
                return ix;                // 登録済み
            }
        }
        System.out.println("Error: Hash Table Full");
        return -1;
    }

    static int get(long id) {
        int n, h = hash(id);
        for (n = 0; n < MAXSIZE; n++) {
            int ix = (h + n) % MAXSIZE;
            if (nodes[ix] == 0) {
                return -1;                // 登録なし
            } else if (nodes[ix] == id) {
                return ix;                // 登録済み
            }
        }
        return -1;  // 存在しない
    }

    static void loadIdLonLat() {
        num_nodes = 0;
        lons = new int[MAXSIZE];
        lats = new int[MAXSIZE];
        for (String area : areas) {
            loadIdLonLat(area);
        }
    }

    static void loadIdLonLat(String name) {
        try (DataInputStream dis = new DataInputStream(new BufferedInputStream(
                    new FileInputStream("c:/osm/" + name + "_idlonlat.dat")))) {
            while (true) {
                long nid = dis.readLong();
                int lon = dis.readInt();
                int lat = dis.readInt();
                put(nid, lon, lat);
            }
        } catch (EOFException e) {
            System.out.println(""); // ファイル読み込み完了
        } catch (Exception e) {
            e.printStackTrace();
        }
    }

    static int cntPolygon = 0;

    // xmlファイルは標準入力（パイプ）から 
    static void parseWay(String name) {
        String pathout = "c:/osm/" + name + "_coastline.csv";
        List<Long> listNodes = new ArrayList<>();
        long idWay = 0;

        try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter fw = new BufferedWriter(new FileWriter(pathout)) ) {
               // FileWriter fw = new FileWriter(new File(pathout)) ) {
            String line;
            boolean fCoastline = false;
            boolean fWaySection = false;

            while ((line = br.readLine()) != null) {
                int ix = line.indexOf('<');
                if (ix < 0) continue;
                String s = line.substring(ix);  // 行先頭のスペースを削除する
                if (fWaySection && s.charAt(2)=='d' && s.startsWith("<nd ")) {
                    String ref = getAttr(" ref=", line);                
                    long idRef = Long.parseLong(ref);
                    listNodes.add(idRef);
                } else if (fWaySection && s.charAt(1)=='t' && s.startsWith("<tag ")) {
                    String key = getAttr(" k=", line);              
                    String val = getAttr(" v=", line);
                    if (key.equals("natural") && val.equals("coastline")) {
                        fCoastline = true;
                    }
                } else if (s.charAt(1)=='w' && s.startsWith("<way ")) { // wayオブジェクト始まり
                    if (!fWaySection) fWaySection = true;
                    listNodes.clear();
                    fCoastline = false;
                    String strId = getAttr(" id=", line);
                    idWay = Long.parseLong(strId);
                } else if (fWaySection && s.charAt(2)=='w' && s.startsWith("</way")) {  // wayオブジェクト終わり
                    if (fCoastline) {
                        fw.write("" + idWay);
                        for (int i = 0; i < listNodes.size(); i++) {
                            fw.write("," + listNodes.get(i));
                        }
                        fw.write("\n");
                    }
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    static HashMap<Long, long[]> mapCoastlines = new HashMap<>();
    static List<Long> listErrorNodes = new ArrayList<>();
    static HashSet<Long> setWayIds = new HashSet<>();

    static DataOutputStream dos;

    // 最終処理
    static void generateLandPolygon() throws Exception {
        dos = new DataOutputStream(new BufferedOutputStream(new FileOutputStream(pathLands())));

        num_nodes = 0;
        lons = new int[MAXSIZE];
        lats = new int[MAXSIZE];

        // ノード座標値データを nodes, lons, lats にセット
        for (String area : areas) {
            loadIdLonLat(area);
        }
        System.out.printf("ノード座標値読み込み完了 num_node=%d\n", num_nodes);

        for (String area : areas) {
            procCoastline(area);
        }

        unclosedCoastlines();
    }

    static void procCoastline(String name) {
        String file = "c:/osm/" + name + "_coastline.csv";
        System.out.printf("procCoastLine %s\n", name);
        try (BufferedReader br = new BufferedReader(new FileReader(file))) {
            String line;
            while ((line = br.readLine()) != null) {
                String[] nids = line.split(",");

                long idWay = Long.parseLong(nids[0]);
                if (setWayIds.contains(idWay)) {
                    continue;   // 処理済み
                }
                setWayIds.add(idWay);

                List<Long> listNodes = new ArrayList<>();
                for (int n = 1; n < nids.length; n++) {
                    long nid = Long.parseLong(nids[n]);
                    int ix = get(nid);
                    if (ix < 0) {
                        System.out.println("Error 座標値が得られない Id＝" + nid);
                        continue;
                    }
                    int lon = lons[ix];
                    int lat = lats[ix];
                    listNodes.add(nid);
                }

                long[] nodes = new long[listNodes.size()];
                for (int n = 0; n < nodes.length; n++) {
                    nodes[n] = listNodes.get(n);
                }
                procCoastline(nodes);
            }
        } catch (Exception e) {
            e.printStackTrace();
            return;
        }
        System.out.printf("mapCoastLines エントリ数＝%d\n", mapCoastlines.size());
    }

    static void procCoastline(long[] nodes) throws Exception {
        long head = nodes[0];
        long tail = nodes[nodes.length-1];

        if (head == tail) {
            //System.out.printf("閉ループ %d\n", head);
            writePolygon(nodes);
            return;
        }
        if (!mapCoastlines.containsKey(head) && !mapCoastlines.containsKey(tail)) {
            mapCoastlines.put(head, nodes);     // 先頭ノードをキー
            mapCoastlines.put(tail, nodes);     // 末尾ノードをキー
            return;
        }

        while ((mapCoastlines.containsKey(head) || mapCoastlines.containsKey(tail))) {
            long[] src = mapCoastlines.get(head);
            if (src == null) src = mapCoastlines.get(tail);
            mapCoastlines.remove(src[0]);
            mapCoastlines.remove(src[src.length-1]);    // 上と同じ配列

            if (src[0] == head || src[src.length-1] == tail) {
                reverse(nodes);
                head = nodes[0];
                tail = nodes[nodes.length-1];
            }   // 反転する

            if (src[src.length-1] == head && src[0] == tail) {
                long[] dst = new long[src.length + nodes.length - 2];
                System.arraycopy(src, 0, dst, 0, src.length);
                System.arraycopy(nodes, 1, dst, src.length, nodes.length-2);
                writePolygon(dst);
                //System.out.printf( "閉ループ完成 nodes=%d mapCoastlines数=%d Polygons数=%d\n",
                //                     dst.length, mapCoastlines.size(), cntPolygon);
                return;     // 閉ループになる
            } 

            long[] dst = new long[src.length + nodes.length - 1];
            if (src[src.length-1] == head) {
                System.arraycopy(src, 0, dst, 0, src.length);
                System.arraycopy(nodes, 1, dst, src.length, nodes.length-1);
                // head は src配列の末尾と同じため、コピーしない
            } else if (src[0] == tail) {
                System.arraycopy(nodes, 0, dst, 0, nodes.length-1);
                System.arraycopy(src, 0, dst, nodes.length-1, src.length);
                // tail は src配列の先頭と同じため、コピーしない
            }

            if (dst[0] == dst[dst.length-1]) {  // 閉ループになった
                writePolygon(dst);
                //System.out.printf( "閉ループ完成 nodes=%d mapCoastlines数=%d Polygons数=%d\n",
                //                     dst.length, mapCoastlines.size(), cntPolygon);
                return;
            }

            nodes = Arrays.copyOf(dst, dst.length);
            head = nodes[0];
            tail = nodes[nodes.length-1];
        }
        mapCoastlines.put(head, nodes);     // HashMapに再登録
        mapCoastlines.put(tail, nodes);
        //System.out.printf( "再登録 dst=%d 登録数=%d\n", nodes.length, mapCoastlines.size() );
    }

    // 元の配列を並び替える
    static void reverse(long[] array) {
        for (int left=0, right=array.length-1; left < right; ) {
            long temp = array[left];
            array[left++] = array[right];
            array[right--] = temp;
        }
    }

    static void reverse(int[] array) {
        for (int left=0, right=array.length-1; left < right; ) {
            int temp = array[left];
            array[left++] = array[right];
            array[right--] = temp;
        }
    }

    static int cntErrPoly = 0;
    static byte[] ba = new byte[128*1024*1024];

    static List<Node> listNodes = new ArrayList<>();

    
    // ids: node id配列.  最後のノードは無視する
    static void writePolygon(long[] ids) throws Exception {
        writePolygon(ids, true);
    }

    // ids: node id配列.  最後のノードは無視する
    static void writePolygon(long[] ids, boolean fClosed) throws Exception {
        int length = fClosed ? ids.length-1 : ids.length;
        int[] xs = new int[length];
        int[] ys = new int[length];
        for (int i = 0; i < length; i++) {
            int ix = get(ids[i]);
			double lat = lats[ix]/E7;
			if (lat < -85.05112877980659) {		// これは無くてもよかった
				lat = -85.05112877980659;
			}
            xs[i] = (int)(Lon2X(lons[ix]/E7, 0) * B30);
            ys[i] = (int)(Lat2Y(lat, 0) * B30);
if (xs[i] < 0 || ys[0] < 0)System.out.printf("%d %d\n", xs[i], ys[i]);
        }
        Polygon poly = new Polygon(xs, ys);
        double wayarea = poly.calcWayArea();
        if (wayarea == 0) System.out.println("WayArea == 0, ノード数＝" + ids.length);
        if (wayarea > 0) {
            reverse(xs);
            reverse(ys);
            poly = new Polygon(xs, ys);
        }

        int span = 1 << 21; // 3度弱

        if (fShrink) {
            poly.shrink(10000);  // 100m
            poly.writePolygon(dos);
        } else if ((poly.ymax - poly.ymin) >= span) {
            List<Polygon> listPoly = poly.splitPolygon(span);
            System.out.printf("%d分割 ", listPoly.size());
            for (Polygon p : listPoly) {
                p.writePolygon(dos);
            }
        } else {
            poly.writePolygon(dos);
        }
    }

    // 閉ループにならない海岸線データ
    static void unclosedCoastlines() throws Exception {
        HashSet<Long> setDone = new HashSet<>();
        for (long[] nids : mapCoastlines.values()) {
            if (setDone.contains(nids[0]) || setDone.contains(nids[nids.length-1])) continue;
            setDone.add(nids[0]);
            int ixHead = get(nids[0]);
            int ixTail = get(nids[nids.length-1]);
            if (lons[ixHead]==lons[ixTail] && (lons[ixHead]== 1800000000 || lons[ixHead]== -1800000000)) {
                writePolygon(nids, false);
            } else {
                System.out.printf("閉じていない海岸線：ノード数＝%d  (%d %d)〜(%d %d)\n", 
                     nids.length, lons[ixHead], lats[ixHead], lons[ixTail], lats[ixTail]);
            }
        }
        System.out.println();
    }

    static double toRadian(double deg) {
        return deg*Math.PI/180.0;   // ラジアンに変換
    }

    static double calcWayArea(int[] xs, int[] ys) {
        double Radius = 6378137 + 100;      // 長半径 + 楕円高（仮）
        double wayarea = 0;
        double x1 = xs[xs.length-2]/E7;
        double y1 = ys[ys.length-2]/E7;
        for (int n = 0; n < xs.length-1; n++) {
            double x2 = xs[n]/E7;
            double y2 = ys[n]/E7;
            wayarea += toRadian(x2-x1)*(2+Math.sin(toRadian(y1))+Math.sin(toRadian(y2)));
            x1 = x2;
            y1 = y2;
        }
        return wayarea * Radius * Radius / 2.0;
    }   // 反時計回りが正、時計回りは負となる


    public static void main(String[] args) throws Exception {
        long start = System.currentTimeMillis();

        Instant instant = Instant.ofEpochSecond(start/1000);
        System.out.println(ZonedDateTime.ofInstant(instant, ZoneId.systemDefault()));

        if (args.length == 2) {
            if (args[0].equals("-way")) {
                parseWay(args[1]);
            } else if (args[1].equals("-way")) {
                parseWay(args[0]);
            } else if (args[0].equals("-node")) {
                parseNode(args[1]);
            } else if (args[1].equals("-node")) {
                parseNode(args[0]);
            }
        } else {
            fShrink = (args.length == 1 && args[0].equals("-shrink"));
            generateLandPolygon();
            System.out.println("ポリゴン数＝" + cntPolygon);
        }

        System.out.printf("実行時間＝%.2f分\n",
            (System.currentTimeMillis() - start)/60000.0 );
    }


    static void SimplifySection(int[] xs, int[] ys, int i, int j, double epsilon) {
        if ((i + 1) == j) return;
        double maxDistance = -1.0;
        int maxIndex = i;
        for (int k = i + 1; k < j; k++) {
            double distance = PerpendicularDistance(xs[k], ys[k], xs[i], ys[i], xs[j], ys[j]);
            if (distance > maxDistance) {
                maxDistance = distance;
                maxIndex = k;
            }
        }
        if (maxDistance <= epsilon) {
            for (int k = i + 1; k < j; k++) {
                xs[k] = Integer.MIN_VALUE;   // 間引く
                ys[k] = Integer.MIN_VALUE;   // 間引く
            }
        } else {
            SimplifySection(xs, ys, i, maxIndex, epsilon);
            SimplifySection(xs, ys, maxIndex, j, epsilon);
        }
    }

    // １度＝約100km ⇒ 1m＝約0.00001度
    static double PerpendicularDistance(double px, double py, double p1x, double p1y, double p2x, double p2y) {
        double dx = p2x - p1x;
        double dy = p2y - p1y;
        double d = Math.sqrt(dx*dx + dy*dy);
        return Math.abs(px*dy - py*dx + p2x*p1y - p2y*p1x)/d;
    }
}